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/9505016 · Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences

A universal two-bit gate for quantum computation

Adriano Barenco

Published Jun 8, 1995• 227 citations
arXivHTMLPDF

Abstract

Abstract We prove the existence of a class of two-input, two-output gates any one of which is universal for quantum computation. This is done by explicitly constructing the three-bit gate introduced by Deutsch ( Proc. R. Soc. Lond. A 425, 73 (1989)) as a network consisting of replicas of a single two-bit gate.
DOI
10.1098/rspa.1995.0066

Related papers

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,545 citations

Realizable Universal Quantum Logic Gates

Tycho Sleator, Harald Weinfurter

We identify a 2-bit quantum gate that is sufficient to build any quantum logic network. The existence of such a 2-bit universal gate considerably simplifies the search for physical realizations of quantum computational networks. We propose an explicit construction of this gate, which is based on cavity QED techniques and may be realizable with current technology.

Physical Review Letters•May 15, 1995•519 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.

arXiv:cond-mat/9407022•Physical Review A•Feb 1, 1995•1,092 citations

Realization and synthesis of reversible functions throng double-coset

Fu Chen, Guowu Yang, Xiaoyu Li

Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)•Dec 1, 2010•0 citations

Simple Realization of the Fredkin Gate using a Series Of Two-Body Operators

H. F. Chau, Frank A. Wilczek

The Fredkin three-bit gate is universal for computational logic, and is reversible. Classically, it is impossible to do universal computation using reversible two-bit gates only. Here we construct the Fredkin gate using a combination of six two-body reversible (quantum) operators.

arXiv:quant-ph/9503005•Physical Review Letters•Jul 24, 1995•59 citations

Universality in quantum computation

Jennifer L. Dodd

A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.

•Jan 1, 2004•7 citations
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.
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.
Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.