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 Machine Learning and Computing

An Algorithm for Synthesis of Quantum Reversible Logic Circuits Based on Decomposition

Dan Li, Fanjiang Xu, Junsuo Zhao, Wenjun Zhang

Published Feb 1, 2014• 0 citations
Publisher

Abstract

Until today, we have not found a general and effective algorithm for synthesis, especially to multi-variables quantum circuit.This is an important question needed to be resolved, because it can not only reduce the cost of manufacture quantum circuit, but also optimize many quantum algorithms.For a quantum circuit which contains N quantum bits, the latitude of the matrix is 𝟐 𝒏 to realize its function.If we directly design the circuits of the matrix, the workload is huge.Want to reduce the dimensions of the matrix, but also to ensure the unitary of matrix after decomposing, so it is need to use Kronecker product.

DOI
10.7763/ijmlc.2014.v4.378

Related papers

Synthesis of Quantum Arrays from Kronecker Functional Lattice Diagrams

Martin Lukáč, Dipal Shah, Marek A. Perkowski +1 more

Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.

IEICE Transactions on Information and Systems•Jan 1, 2014•3 citations

A Novel Algorithm for Reversible Circuit Optimization

Yi-Tzu Lo, Shu–Yu Kuo, Guo-Jyun Zeng +2 more

Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2015•1 citation

Matrix-based algorithm for 4-Qubit reversible circuits synthesis

Dong Wang, Shengyao Sun, Hanwu Chen

The mathematical model of the quantum reversible circuits is unitary matrix. Matrix can better reflect the quantum state evolution and further reflect the physical properties of the quantum computation. Matrix transformation based algorithm for 4-qubit reversible logic circuits synthesis is proposed in this paper. The algorithm skillfully uses the matrix representation of the quantum circuit and the circuit of the adjacent matrix to construct 4-qubit circuit with lower cost.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 13, 2013•0 citations

An Algorithm for Synthesis of Optimal 3-qubit Reversible Circuits Based on Bit Operation

Zhiqiang Li, Hanwu Chen, Baowen Xu +2 more

We use bit operation to construct the novel and perfect Hash function and present an efficient algorithm which can construct optimal quantum reversible logic circuits with various types of gates by using the Hash table and produce quantum circuits with minimal cost in theory. Judging by the internationally recognized reversible functions of three variables, the algorithm not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm which synthesizes circuit with minimum length is 69.8 times that of currently best result [9].

International Conference on Genetic and Evolutionary Computing•Sep 1, 2008•2 citations

Synthesis of Ternary Quantum Logic Circuits by Decomposition

Khan, Faisal Shah, Perkowski, Marek

Recent research in multi-valued logic for quantum computing has shown practical advantages for scaling up a quantum computer. Multivalued quantum systems have also been used in the framework of quantum cryptography, and the concept of a qudit cluster state has been proposed by generalizing the qubit cluster state. An evolutionary algorithm based synthesizer for ternary quantum circuits has recently been presented, as well as a synthesis method based on matrix factorization.In this paper, a recursive synthesis method for ternary quantum circuits based on the Cosine-Sine unitary matrix decomposition is presented.

arXiv:quant-ph/0511041•Nov 4, 2005•20 citations

Synthesis of the Optimal 4-bit Reversible Circuits

Oleg Golubitsky, Sean M. Falconer, Maslov, Dmitri

Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16!~2^44 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

arXiv:1003.1914•Mar 9, 2010•0 citations
Until today, we have not found a general and effective algorithm for synthesis, especially to multi-variables quantum circuit.This is an important question needed to be resolved, because it can not only reduce the cost of manufacture quantum circuit, but also optimize many quantum algorithms.For a quantum circuit which contains N quantum bits, the latitude of the matrix is 𝟐 𝒏 to realize its function.If we directly design the circuits of the matrix, the workload is huge.Want to reduce the dimensions of the matrix, but also to ensure the unitary of matrix after decomposing, so it is need to use Kronecker product.
Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.
Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.
We use bit operation to construct the novel and perfect Hash function and present an efficient algorithm which can construct optimal quantum reversible logic circuits with various types of gates by using the Hash table and produce quantum circuits with minimal cost in theory. Judging by the internationally recognized reversible functions of three variables, the algorithm not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm which synthesizes circuit with minimum length is 69.8 times that of currently best result [9].
Recent research in multi-valued logic for quantum computing has shown practical advantages for scaling up a quantum computer. Multivalued quantum systems have also been used in the framework of quantum cryptography, and the concept of a qudit cluster state has been proposed by generalizing the qubit cluster state. An evolutionary algorithm based synthesizer for ternary quantum circuits has recently been presented, as well as a synthesis method based on matrix factorization.In this paper, a recursive synthesis method for ternary quantum circuits based on the Cosine-Sine unitary matrix decomposition is presented.
Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16!~2^44 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.