Workshop on Physics and Computation (PhysComp)

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

Published Dec 17, 2002• 15 citations

Abstract

We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is the universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very nonclassical feature of the operation, its exact quantum phase factor.>

DOI: 10.1109/phycmp.1994.363704

Related papers

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

arXiv:cond-mat/9409111Sep 26, 199414 citations

Elementary gates for quantum computation

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

arXiv:quant-ph/9503016Physical Review ANov 1, 19954,309 citations

Two-bit gates are universal for quantum computation

David Peter Divincenzo

arXiv:cond-mat/9407022Physical Review AFeb 1, 19951,068 citations

Reversible Computing Foundations in Quantum Computation: From Classical Logic to Quantum Algorithms

Keval Barvaliya

Advances in intelligent systems research/Advances in Intelligent Systems ResearchJan 1, 20260 citations

A Systematic Algorithm for Quantum Boolean Circuits Construction

I.-M. Tsai, Sy‐Yen Kuo

arXiv:quant-ph/0104037Apr 9, 20012 citations

Optimal simulation of three-qubit gates

Nengkun Yu, Mingsheng Ying

arXiv:1301.3727Jan 16, 20132 citations

Workshop on Physics and Computation (PhysComp)

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

Published Dec 17, 2002• 15 citations

Publisher

Abstract

DOI: 10.1109/phycmp.1994.363704

Related papers

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is a universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very non-classical feature of the operation, its exact quantum phase factor.We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is a universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very non-classical feature of the operation, its exact quantum phase factor.

arXiv:cond-mat/9409111Sep 26, 199414 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.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/9503016Physical Review ANov 1, 19954,309 citations

Two-bit gates are universal for quantum computation

David Peter Divincenzo

A proof is given, which relies on the commutator algebra of the unitary Lie groups, that quantum gates operating on just two bits at a time are sufficient to construct a general quantum circuit. The best previous result had shown the universality of three-bit gates, by analogy to the universality of the Toffoli three-bit gate of classical reversible computing. Two-bit quantum gates may be implemented by magnetic resonance operations applied to a pair of electronic or nuclear spins. A ``gearbox quantum computer'' proposed here, based on the principles of atomic-force microscopy, would permit the operation of such two-bit gates in a physical system with very long phase-breaking (i.e., quantum-phase-coherence) times. Simpler versions of the gearbox computer could be used to do experiments on Einstein-Podolsky-Rosen states and related entangled quantum states.A proof is given, which relies on the commutator algebra of the unitary Lie groups, that quantum gates operating on just two bits at a time are sufficient to construct a general quantum circuit. The best previous result had shown the universality of three-bit gates, by analogy to the universality of the Toffoli three-bit gate of classical reversible computing. Two-bit quantum gates may be implemented by magnetic resonance operations applied to a pair of electronic or nuclear spins. A ``gearbox quantum computer'' proposed here, based on the principles of atomic-force microscopy, would permit the operation of such two-bit gates in a physical system with very long phase-breaking (i.e., quantum-phase-coherence) times. Simpler versions of the gearbox computer could be used to do experiments on Einstein-Podolsky-Rosen states and related entangled quantum states.

arXiv:cond-mat/9407022Physical Review AFeb 1, 19951,068 citations

Reversible Computing Foundations in Quantum Computation: From Classical Logic to Quantum Algorithms

Keval Barvaliya

Reversible computing provides a foundational framework for understanding quantum computation.This paper first examines classical reversible logic gates, including the CNOT and Toffoli gates, and demonstrates how they can simulate arbitrary Boolean functions.We then extend these concepts to quantum gates and circuits, where all operations are inherently unitary and reversible.Quantum algorithms such as the Deutsch-Jozsa algorithm, phase estimation, and Shor's factoring algorithm are discussed to illustrate how reversibility enables exponential computational speedups.Finally, current challenges and future directions in quantum hardware and algorithm design are presented.Highlighting the essential role of reversible computing in the realisation of practical quantum computers.Reversible computing provides a foundational framework for understanding quantum computation.This paper first examines classical reversible logic gates, including the CNOT and Toffoli gates, and demonstrates how they can simulate arbitrary Boolean functions.We then extend these concepts to quantum gates and circuits, where all operations are inherently unitary and reversible.Quantum algorithms such as the Deutsch-Jozsa algorithm, phase estimation, and Shor's factoring algorithm are discussed to illustrate how reversibility enables exponential computational speedups.Finally, current challenges and future directions in quantum hardware and algorithm design are presented.Highlighting the essential role of reversible computing in the realisation of practical quantum computers.

Advances in intelligent systems research/Advances in Intelligent Systems ResearchJan 1, 20260 citations

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.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/0104037Apr 9, 20012 citations

Optimal simulation of three-qubit gates

Nengkun Yu, Mingsheng Ying

In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary $u$ on the target qubit only if both the states of the control are $\ket{1}$ . Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of $u$ is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary $u$ on the target qubit only if both the states of the control are $\ket{1}$. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of $u$ is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.

arXiv:1301.3727Jan 16, 20132 citations

{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.

u

on the target qubit only if both the states of the control are

\ket{1}

. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of

u

is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.