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•4 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•18 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•61 citations

Quantum circuit synthesis using Solovay-Kitaev algorithm and optimization techniques

Al-Ta'ani, Ola

Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.

•May 1, 2015•7 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.
Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.