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/0401162 · Quantum Information and Computation

Quantum circuits for incompletely specified two-qubit operators

Vivek Shende, Igor L. Markov

Published Jan 1, 2005• 60 citations
arXivHTMLPDF

Abstract

While the question ``how many CNOT gates are needed to simulate an arbitrary two-qubit operator'' has been conclusively answered -- three are necessary and sufficient -- previous work on this topic assumes that one wants to simulate a given unitary operator up to global phase. However, in many practical cases additional degrees of freedom are allowed. For example, if the computation is to be followed by a given projective measurement, many dissimilar operators achieve the same output distributions on all input states. Alternatively, if it is known that the input state is $\ket{0}$, the action of the given operator on all orthogonal states is immaterial. In such cases, we say that the unitary operator is incompletely specified; in this work, we take up the practical challenge of satisfying a given specification with the smallest possible circuit. In particular, we identify cases in which such operators can be implemented using fewer quantum gates than are required for generic completely specified operators.

DOI
10.26421/qic5.1-5

Related papers

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•12 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•24 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 uni-tary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In anal-ogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum compu-tation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expen-sive, we assume throughout that no extra qubits are avail-able 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 cir-cuits in some cases. 1

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

Numerical analysis of quantum circuits for state preparation and unitary operator synthesis

Sahel Ashhab, Naoki Yamamoto, Fumiki Yoshihara +1 more

We perform optimal-control-theory calculations to determine the minimum number of two-qubit controlled-not (cnot) gates needed to perform quantum state preparation and unitary operator synthesis for few-qubit systems. By considering all possible gate configurations, we determine the maximum achievable fidelity as a function of quantum circuit size. This information allows us to identify the minimum circuit size needed for a specific target operation and enumerate the different gate configurations that allow a perfect implementation of the operation. We find that there are a large number of configurations that all produce the desired result, even at the minimum number of gates. We also show that the number of entangling gates can be reduced if we use multiqubit entangling gates instead of two-qubit cnot gates, as one might expect based on parameter counting calculations. In addition to treating the general case of arbitrary target states or unitary operators, we apply the numerical approach to the special case of synthesizing the multiqubit Toffoli gate. This approach can be used to investigate any other specific few-qubit task and provides insight into the tightness of different bounds in the literature.

arXiv:2204.13524•Physical Review A•Aug 23, 2022•24 citations

Universal quantum circuit for two-qubit transformations with three controlled-NOT gates

Guifré Vidal, Christopher M. Dawson

We consider quantum circuits made of controlled-NOT (CNOT) gates and single-qubit unitary gates and look for constructions that minimize the use of CNOT gates. We show, by means of an explicit quantum circuit, that three CNOT gates are necessary and sufficient in order to implement an arbitrary unitary transformation of two qubits. We also identify the subset of two-qubit gates that can be performed with only two CNOT gates and provide a simple characterization for them.

arXiv:quant-ph/0307177•Physical Review A•Jan 8, 2004•296 citations

A Practical Top-down Approach to Quantum Circuit Synthesis

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

Operators acting on a collection of two-level quantum-mechanical systems can be represented by quantum circuits. In this work we develop a decomposition of such unitary operators which reveals their top-down structure and can be implemented numerically with well-known primitives. It leads to simultaneous improvements by a factor of two over (i) the best known n-qubit circuit synthesis algorithms for large n, and (ii) the best known three-qubit circuits. In the worst case, our algorithm NQ produces circuits that differ from known lower bounds by approximately a factor of two. Thus, the required number of quantum controlled-not's (i.e. two-qubit interactions) is only half of the number of real degrees of freedom (4^n-1) of a generic unitary operator. This is desirable since CNOTs are typically slower and more error-prone than one-qubit rotations, and they may in addition may require physically coupling distant two-level systems.

•Jun 23, 2004•20 citations
While the question ``how many CNOT gates are needed to simulate an arbitrary two-qubit operator'' has been conclusively answered -- three are necessary and sufficient -- previous work on this topic assumes that one wants to simulate a given unitary operator up to global phase. However, in many practical cases additional degrees of freedom are allowed. For example, if the computation is to be followed by a given projective measurement, many dissimilar operators achieve the same output distributions on all input states. Alternatively, if it is known that the input state is ∣0⟩\ket{0}∣0⟩, the action of the given operator on all orthogonal states is immaterial. In such cases, we say that the unitary operator is incompletely specified; in this work, we take up the practical challenge of satisfying a given specification with the smallest possible circuit. In particular, we identify cases in which such operators can be implemented using fewer quantum gates than are required for generic completely specified operators.
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 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 uni-tary operation using any of several quantum gate libraries with small a priori upper bounds on gate counts. In anal-ogy to library-less logic synthesis, we consider circuits and gates in terms of the underlying model of quantum compu-tation, and do not assume any particular technology. As increasing the number of qubits can be prohibitively expen-sive, we assume throughout that no extra qubits are avail-able 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 cir-cuits in some cases. 1
We perform optimal-control-theory calculations to determine the minimum number of two-qubit controlled-not (cnot) gates needed to perform quantum state preparation and unitary operator synthesis for few-qubit systems. By considering all possible gate configurations, we determine the maximum achievable fidelity as a function of quantum circuit size. This information allows us to identify the minimum circuit size needed for a specific target operation and enumerate the different gate configurations that allow a perfect implementation of the operation. We find that there are a large number of configurations that all produce the desired result, even at the minimum number of gates. We also show that the number of entangling gates can be reduced if we use multiqubit entangling gates instead of two-qubit cnot gates, as one might expect based on parameter counting calculations. In addition to treating the general case of arbitrary target states or unitary operators, we apply the numerical approach to the special case of synthesizing the multiqubit Toffoli gate. This approach can be used to investigate any other specific few-qubit task and provides insight into the tightness of different bounds in the literature.
Operators acting on a collection of two-level quantum-mechanical systems can be represented by quantum circuits. In this work we develop a decomposition of such unitary operators which reveals their top-down structure and can be implemented numerically with well-known primitives. It leads to simultaneous improvements by a factor of two over (i) the best known n-qubit circuit synthesis algorithms for large n, and (ii) the best known three-qubit circuits. In the worst case, our algorithm NQ produces circuits that differ from known lower bounds by approximately a factor of two. Thus, the required number of quantum controlled-not's (i.e. two-qubit interactions) is only half of the number of real degrees of freedom (4^n-1) of a generic unitary operator. This is desirable since CNOTs are typically slower and more error-prone than one-qubit rotations, and they may in addition may require physically coupling distant two-level systems.