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

Arbitrary two-qubit computation in 23 elementary gates

Stephen S. Bullock, Igor L. Markov

Published Jul 22, 2003• 59 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.68.012318

Related papers

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

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. 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 as small a number of elementary quantum gates [1, 9] 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 worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques 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 a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jun 2, 2003•17 citations

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. 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 as small a number of elementary quantum gates [1, 9] 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 worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques 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 a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•4 citations

Optimal design of two-qubit quantum circuits

Farrokh Vatan, Colin P. Williams

In order to demonstrate non-trivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to nderstand how to decompose a desired quantum computation into the shortest possible sequence of one-qubit and two-qubit gates. We contribute to this effort by providing a method to construct an optimal quantum circuit for a general two-qubit gate that requires at most 3 CNOT gates and 15 elementary one qubit gates. We then prove that these constructions are optimal with respect to the family of CNOT, y-rotation, z-rotation, and phase gates.

•Jan 5, 2004•0 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•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
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.
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.
Quantum circuits currently constitute a dominant model for quantum computation [14]. 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 as small a number of elementary quantum gates [1, 9] 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 worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques 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 a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
Quantum circuits currently constitute a dominant model for quantum computation [14]. 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 as small a number of elementary quantum gates [1, 9] 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 worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques 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 a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
In order to demonstrate non-trivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to nderstand how to decompose a desired quantum computation into the shortest possible sequence of one-qubit and two-qubit gates. We contribute to this effort by providing a method to construct an optimal quantum circuit for a general two-qubit gate that requires at most 3 CNOT gates and 15 elementary one qubit gates. We then prove that these constructions are optimal with respect to the family of CNOT, y-rotation, z-rotation, and phase gates.
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.