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

arXiv:quant-ph/0104037

A Systematic Algorithm for Quantum Boolean Circuits Construction

I.-M. Tsai, Sy‐Yen Kuo

Published Apr 9, 2001• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0104037

Related papers

AN ALGORITHM FOR MINIMUM SPACE QUANTUM BOOLEAN CIRCUITS CONSTRUCTION

I-Ming Tsai, Sy‐Yen Kuo

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.

Journal of Circuits Systems and Computers•Oct 1, 2006•17 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

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

Elementary gates for quantum computation

Adriano Barenco, Charles H. Bennett, Richard Cleve +6 more

We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(${2}^{\mathit{n}}$)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.

arXiv:quant-ph/9503016•Physical Review A•Nov 1, 1995•4,309 citations

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

IEEE Access•Jan 1, 2023•3 citations

Universal construction of unitary transformation of quantum computation with one- and two-body interactions

Xijia Miao

Any unitary transformation of quantum computational networks is explicitly decomposed, in an exact and unified form, into a sequence of a limited number of one-qubit quantum gates and the two-qubit diagonal gates that have diagonal unitary representation in usual computational basis. This decomposition may be simplified greatly with the help of the properties of the finite-dimensional multiple-quantum operator algebra spaces of a quantum system and the specific properties of a given quantum algorithm. As elementary building blocks of quantum computation, the two-qubit diagonal gates and one-qubit gates may be constructed physically with one- and two-body interactions in a two-state quantum system and hence could be conveniently realized experimentally. The present work will be helpful for implementing generally any N-qubit quantum computation in those feasible two-state quantum systems and determining conveniently the time evolution of these systems in course of quantum computation.

arXiv:quant-ph/0003068•Mar 17, 2000•6 citations
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.
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.
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.
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.
We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(2n{2}^{\mathit{n}}2n)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.
Any unitary transformation of quantum computational networks is explicitly decomposed, in an exact and unified form, into a sequence of a limited number of one-qubit quantum gates and the two-qubit diagonal gates that have diagonal unitary representation in usual computational basis. This decomposition may be simplified greatly with the help of the properties of the finite-dimensional multiple-quantum operator algebra spaces of a quantum system and the specific properties of a given quantum algorithm. As elementary building blocks of quantum computation, the two-qubit diagonal gates and one-qubit gates may be constructed physically with one- and two-body interactions in a two-state quantum system and hence could be conveniently realized experimentally. The present work will be helpful for implementing generally any N-qubit quantum computation in those feasible two-state quantum systems and determining conveniently the time evolution of these systems in course of quantum computation.