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/0308033 · Physical Review A

Minimal universal two-qubit controlled-NOT-based circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

Published Jun 30, 2004• 287 citations
arXivHTMLPDF

Abstract

We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in $\mathrm{C}++$.

DOI
10.1103/physreva.69.062321

Related papers

Smaller two-qubit circuits for quantum communication and computation

Vivek Shende, Igor L. Markov, Stephen S. Bullock

We show how to implement an arbitrary two-qubit unitary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In analogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum computation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expensive, we assume throughout that no extra qubits are available for temporary storage. Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). We study the performance of our synthesis procedures on two-qubit operators that are useful in quantum algorithms and communication protocols. With additional work, we find small circuits and improve upon previously known circuits in some cases.

Design, Automation, and Test in Europe•Feb 16, 2004•14 citations

Smaller two-qubit circuits for quantum communication and computation

Vivek Shende, Igor L. Markov, Stephen S. Bullock

We show how to implement an arbitrary two-qubit unitary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In analogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum computation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expensive, we assume throughout that no extra qubits are available for temporary storage. Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). We study the performance of our synthesis procedures on two-qubit operators that are useful in quantum algorithms and communication protocols. With additional work, we find small circuits and improve upon previously known circuits in some cases.

Design, Automation, and Test in Europe•Jul 20, 2004•22 citations

Finding small two-qubit circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•13 citations

Arbitrary two-qubit computation in 23 elementary gates

Stephen S. Bullock, Igor L. Markov

We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least $17$ gates: $15$ one-qubit rotations and $2$ controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of $23$ elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of $61$ gates, of which $18$ may be CNOT gates.

arXiv:quant-ph/0211002•Physical Review A•Jul 22, 2003•59 citations

Exact Two-Qubit Universal Quantum Circuit

Jun Zhang, Jiří Vala, Shankar Sastry +1 more

We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.

arXiv:quant-ph/0212109•Physical Review Letters•Jul 11, 2003•68 citations

An arbitrary two-qubit computation in 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation according to M. Nielsen and I. Chuang (2000). Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and a small number of elementary quantum gates by A. Barenco et al. (1995) and G. Song and A. Klappenecker (2003) as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound to 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previous known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm according to G. Cybenko (2001) has a worst case of 61 gates of which 18 may be CNOTs. Our technique rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of two-qubit gate with respect to the "magic basis" of phase-shifted Bell states by N. Khaneja et al. (2001) and M. Lewenstein et al. (2001). We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Mar 1, 2004•5 citations
We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in C++\mathrm{C}++C++.
We show how to implement an arbitrary two-qubit unitary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In analogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum computation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expensive, we assume throughout that no extra qubits are available for temporary storage. Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). We study the performance of our synthesis procedures on two-qubit operators that are useful in quantum algorithms and communication protocols. With additional work, we find small circuits and improve upon previously known circuits in some cases.
We show how to implement an arbitrary two-qubit unitary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In analogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum computation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expensive, we assume throughout that no extra qubits are available for temporary storage. Using quantum circuit identities, we improve an earlier lower bound of 17 elementary gates by Bullock and Markov to 18, and their upper bound of 23 elementary gates to 18. We also improve upon the generic circuit with six CNOT gates by Zhang et al. (our circuit uses three), and that by Vidal and Dawson with 11 basic gates (we use 10). We study the performance of our synthesis procedures on two-qubit operators that are useful in quantum algorithms and communication protocols. With additional work, we find small circuits and improve upon previously known circuits in some cases.
An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.
We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 171717 gates: 151515 one-qubit rotations and 222 controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of 232323 elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of 616161 gates, of which 181818 may be CNOT gates.
We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.
Quantum circuits currently constitute a dominant model for quantum computation according to M. Nielsen and I. Chuang (2000). Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and a small number of elementary quantum gates by A. Barenco et al. (1995) and G. Song and A. Klappenecker (2003) as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound to 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previous known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm according to G. Cybenko (2001) has a worst case of 61 gates of which 18 may be CNOTs. Our technique rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of two-qubit gate with respect to the "magic basis" of phase-shifted Bell states by N. Khaneja et al. (2001) and M. Lewenstein et al. (2001). We extend this decomposition in terms of elementary gates for quantum computation.