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

Journal of Circuits Systems and Computers

AN ALGORITHM FOR MINIMUM SPACE QUANTUM BOOLEAN CIRCUITS CONSTRUCTION

I-Ming Tsai, Sy‐Yen Kuo

Published Oct 1, 2006• 17 citations
Publisher

Abstract

Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.

DOI
10.1142/s0218126606003349

Related papers

A Systematic Algorithm for Quantum Boolean Circuits Construction

I.-M. Tsai, Sy‐Yen Kuo

To build a general-purpose quantum computer, it is crucial for the quantum devices to implement classical boolean logic. A straightforward realization of quantum boolean logic is to use auxiliary qubits as intermediate storage. This inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, we have derived a systematic way of realizing any general m-to-n bit combinational boolean logic using elementary quantum gates. Our approach transforms the m-to-n bit classical mapping into a t-bit unitary quantum operation with minimum number of auxiliary qubits, then a variation of Toffoli gate is used as the basic building block to construct the unitary operation. Finally, each of these building blocks can be decomposed into one-bit rotation and two-bit control-U gates. The efficiency of the network is taken into consideration by formulating it as a constrained set partitioning problem.

arXiv:quant-ph/0104037•Apr 9, 2001•2 citations

Quantum Boolean circuit construction and layout under locality constraint

I.-M. Tsai, Sy‐Yen Kuo

The discovery of Shor's prime factorization and Grover's fast database search algorithm have made quantum computing the most rapidly expanding research field recently. Nanotechnology, in particular silicon-based nanoscale devices, have been proposed as one of the candidates that can be used to implement a quantum computer. In this paper, we have derived a systematic procedure to realize any general m-to-n bit combinational Boolean logic using elementary quantum gates. The quantum circuit layout under the locality constraint is then formulated, together with the gate count evaluation function, to reduce the total number of quantum gates required to implement the circuit.

IEEE Conference on Nanotechnology (IEEE NANO)•Nov 13, 2002•17 citations

Quantum boolean circuits construction using tabulation method

Chin-Yung Lu, Shiou-An Wang, Sy‐Yen Kuo

The tabulation method can be used with a computer to simplify Boolean logic functions with up to 6 or more variables, especially with a large number of variables. For the various applications, their circuits usually are complex and we must simplify the circuit design to the best of our ability. In this paper, we present an algorithm that can efficiently simplify a quantum Boolean circuit with an arbitrary number of input variables by using the tabulation method. In terms of the space consumption, we use only one auxiliary qubit as the output qubit, and keep all the input qubits unchanged.

IEEE Conference on Nanotechnology (IEEE NANO)•Apr 1, 2005•2 citations

A novel quantum Boolean circuit synthesis method using matrix elementary transformations

Guangjun Xie

Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.

Chinese Journal of Quantum Electronics•Jan 1, 2011•0 citations

Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians

Ammar Daskin, Sabre Kais

Constructing appropriate unitary matrix operators for new quantum algorithms and finding the minimum cost gate sequences for the implementation of these unitary operators is of fundamental importance in the field of quantum information and quantum computation. Evolution of quantum circuits faces two major challenges: complex and huge search space and the high costs of simulating quantum circuits on classical computers. Here, we use the group leaders optimization algorithm to decompose a given unitary matrix into a proper-minimum cost quantum gate sequence. We test the method on the known decompositions of Toffoli gate, the amplification step of the Grover search algorithm, the quantum Fourier transform, and the sender part of the quantum teleportation. Using this procedure, we present the circuit designs for the simulation of the unitary propagators of the Hamiltonians for the hydrogen and the water molecules. The approach is general and can be applied to generate the sequence of quantum gates for larger molecular systems.

arXiv:1009.5625•The Journal of Chemical Physics•Apr 14, 2011•60 citations

2011, “Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians

Anmer Daskin, Sabre Kais

Constructing appropriate unitary matrix operators for new quantum algorithms and finding the minimum cost gate sequences for the implementation of these unitary operators is of fundamental importance in the field of quantum information and quantum computation. Evolution of quantum circuits faces two major challenges: complex and huge search space and the high costs of simulating quantum circuits on classical computers. Here, we use the group leaders optimization algorithm to decompose a given unitary matrix into a proper-minimum cost quantum gate sequence. We test the method on the known decompositions of Toffoli gate, the amplification step of the Grover search algorithm, the quantum Fourier transform, and the sender part of the quantum teleportation. Using this procedure, we present the circuit designs for the simulation of the unitary propagators of the Hamiltonians for the hydrogen and the water molecules. The approach is general and can be applied to generate the sequence of quantum gates for larger molecular systems.

•Aug 17, 2016•41 citations
Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.
To build a general-purpose quantum computer, it is crucial for the quantum devices to implement classical boolean logic. A straightforward realization of quantum boolean logic is to use auxiliary qubits as intermediate storage. This inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, we have derived a systematic way of realizing any general m-to-n bit combinational boolean logic using elementary quantum gates. Our approach transforms the m-to-n bit classical mapping into a t-bit unitary quantum operation with minimum number of auxiliary qubits, then a variation of Toffoli gate is used as the basic building block to construct the unitary operation. Finally, each of these building blocks can be decomposed into one-bit rotation and two-bit control-U gates. The efficiency of the network is taken into consideration by formulating it as a constrained set partitioning problem.
The discovery of Shor's prime factorization and Grover's fast database search algorithm have made quantum computing the most rapidly expanding research field recently. Nanotechnology, in particular silicon-based nanoscale devices, have been proposed as one of the candidates that can be used to implement a quantum computer. In this paper, we have derived a systematic procedure to realize any general m-to-n bit combinational Boolean logic using elementary quantum gates. The quantum circuit layout under the locality constraint is then formulated, together with the gate count evaluation function, to reduce the total number of quantum gates required to implement the circuit.
The tabulation method can be used with a computer to simplify Boolean logic functions with up to 6 or more variables, especially with a large number of variables. For the various applications, their circuits usually are complex and we must simplify the circuit design to the best of our ability. In this paper, we present an algorithm that can efficiently simplify a quantum Boolean circuit with an arbitrary number of input variables by using the tabulation method. In terms of the space consumption, we use only one auxiliary qubit as the output qubit, and keep all the input qubits unchanged.
Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.
Constructing appropriate unitary matrix operators for new quantum algorithms and finding the minimum cost gate sequences for the implementation of these unitary operators is of fundamental importance in the field of quantum information and quantum computation. Evolution of quantum circuits faces two major challenges: complex and huge search space and the high costs of simulating quantum circuits on classical computers. Here, we use the group leaders optimization algorithm to decompose a given unitary matrix into a proper-minimum cost quantum gate sequence. We test the method on the known decompositions of Toffoli gate, the amplification step of the Grover search algorithm, the quantum Fourier transform, and the sender part of the quantum teleportation. Using this procedure, we present the circuit designs for the simulation of the unitary propagators of the Hamiltonians for the hydrogen and the water molecules. The approach is general and can be applied to generate the sequence of quantum gates for larger molecular systems.
Constructing appropriate unitary matrix operators for new quantum algorithms and finding the minimum cost gate sequences for the implementation of these unitary operators is of fundamental importance in the field of quantum information and quantum computation. Evolution of quantum circuits faces two major challenges: complex and huge search space and the high costs of simulating quantum circuits on classical computers. Here, we use the group leaders optimization algorithm to decompose a given unitary matrix into a proper-minimum cost quantum gate sequence. We test the method on the known decompositions of Toffoli gate, the amplification step of the Grover search algorithm, the quantum Fourier transform, and the sender part of the quantum teleportation. Using this procedure, we present the circuit designs for the simulation of the unitary propagators of the Hamiltonians for the hydrogen and the water molecules. The approach is general and can be applied to generate the sequence of quantum gates for larger molecular systems.