Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Journal of Electronics and Telecommunications

Complete synthesis of identity templates for quantum and reversible logic MCT circuits using SAT-solvers and proposal of suboptimality witness notion

Adam Jagielski

Published Jul 25, 2024• 0 citations
Publisher

Abstract

In this study, we introduce a procedural generation technique for Identity Templates applicable to quantum and reversible logic circuits. These templates are recognized for their significant role in enhancing the efficiency of quantum and reversible logic optimization. Our approach enables the exhaustive synthesis of all potential templates up to a specified size. Leveraging the power of SAT-solver technology, we have verified the comprehensiveness of our template collections by confirming the full exploration of the search space. Additionally, we propose an innovative concept of Suboptimality Witnesses, which we anticipate will be instrumental in streamlining the search process in formal methods, akin to SAT-solvers, for the synthesis of reversible logic circuits.

DOI
10.24425/ijet.2024.149602

Related papers

Optimal SAT Solver Synthesis of Quantum Circuits Representing Cryptographic Nonlinear Functions

Adam Jagielski

In this article we present a procedure that allows to synthesize optimal circuit representing any reversible function within reasonable size limits. The procedure allows to choose either the NCT or the MCT gate set and specify any number of ancillary qubits to be used in the circuit. We will explore efficacy of this procedure by synthesizing various sources of nonlinearity used in contemporary symmetric ciphers and draw conclusions about properties of those transformations in quantum setting. In particular we will try to synthesize optimal circuit representing ASCON cipher SBOX which recently won NIST competition for Lightweight Cryptography standard.

International Journal of Electronics and Telecommunications•May 31, 2023•1 citation

Algorithm of Optimizing Quantum Reversible Logic Synthesis

Zhiqiang Li, Wenqian Li, Hanwu Chen

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.

Journal of Software•Nov 13, 2009•0 citations

Quantum logic synthesis by symbolic reachability analysis

William N. N. Hung, Xiaoyu Song B, Guowu Yang +2 more

Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.

ACM/IEEE Design Automation Conference (DAC)•Jun 7, 2004•83 citations

An efficient algorithm to synthesize quantum circuits and optimization

Ömercan Susam, Mustafa Altun

Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)•Dec 1, 2014•2 citations

A fast algorithm for synthesis of quantum reversible logic circuits based on Reed-Muller

Zhiqiang Li, Hanwu Chen

Combining several kinds of ideas of synthesis of reversible logic circuits,this paper presents a novel and efficient algorithm which can automatically derive the positive polarity Reed-Muller expansion(RM).A solution space tree of creating quantum reversible logic circuits is constructed.Firstly floor traversal is used in whole,and depth-first search is used in local.Secondly according to the technique of template optimization,the bound function is created which can rapidly eliminate the branches of none result or none optimal result.Thirdly factors of RM are considered first.Therefore the algorithm can effectively construct optimal result and saves computational cost significantly.

Journal of Yangzhou University•Jan 1, 2006•0 citations

An Algorithm for Quantum Template Matching

Md. Mazder Rahman, Gerhard W. Dueck, Joseph D. Horton

Quantum circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.

ACM Journal on Emerging Technologies in Computing Systems•Dec 30, 2014•20 citations
In this study, we introduce a procedural generation technique for Identity Templates applicable to quantum and reversible logic circuits. These templates are recognized for their significant role in enhancing the efficiency of quantum and reversible logic optimization. Our approach enables the exhaustive synthesis of all potential templates up to a specified size. Leveraging the power of SAT-solver technology, we have verified the comprehensiveness of our template collections by confirming the full exploration of the search space. Additionally, we propose an innovative concept of Suboptimality Witnesses, which we anticipate will be instrumental in streamlining the search process in formal methods, akin to SAT-solvers, for the synthesis of reversible logic circuits.
In this article we present a procedure that allows to synthesize optimal circuit representing any reversible function within reasonable size limits. The procedure allows to choose either the NCT or the MCT gate set and specify any number of ancillary qubits to be used in the circuit. We will explore efficacy of this procedure by synthesizing various sources of nonlinearity used in contemporary symmetric ciphers and draw conclusions about properties of those transformations in quantum setting. In particular we will try to synthesize optimal circuit representing ASCON cipher SBOX which recently won NIST competition for Lightweight Cryptography standard.
最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.
Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.
Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.
Combining several kinds of ideas of synthesis of reversible logic circuits,this paper presents a novel and efficient algorithm which can automatically derive the positive polarity Reed-Muller expansion(RM).A solution space tree of creating quantum reversible logic circuits is constructed.Firstly floor traversal is used in whole,and depth-first search is used in local.Secondly according to the technique of template optimization,the bound function is created which can rapidly eliminate the branches of none result or none optimal result.Thirdly factors of RM are considered first.Therefore the algorithm can effectively construct optimal result and saves computational cost significantly.
Quantum circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.