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

Physical Review A

Comment on “Universal quantum circuit for two-qubit transformations with three controlled-NOT gates” and “Recognizing small-circuit structure in two-qubit operators”

Mark W. Coffey, Ron Deiotte, Torey Semi

Published Jun 26, 2008• 20 citations
Publisher

Abstract

Recent papers in Physical Review A have considered small quantum circuit decompositions in terms of a minimal number of controlled-NOT (CNOT) gates. Specifically, we point out errors in the papers by Vidal and Dawson [Phys. Rev. A 69, 010301(R) (2004)] and by Shende et al. [Phys. Rev. A 70, 012310 (2004)].
DOI
10.1103/physreva.77.066301

Related papers

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•276 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•335 citations

Comment on “Linear-depth quantum circuits for n -qubit Toffoli gates with no ancilla”

Ming-Xing Luo, Hui-Ran Li

Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary $n$-qubit Toffoli gate with ancillary qubits [M. Saeedi and M. Pedram, Phys. Rev. A 87, 062318 (2013)]. Their circuits are based on an equivalent representation of the not gate regardless of the global phase. However, we find that this equivalence cannot be extended to the controlled-not gate or the $n$-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an $n$-qubit Toffoli gate and an $n$-qubit phase-flip gate.

Physical Review A•Aug 18, 2016•3 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

Recognizing small-circuit structure in two-qubit operators

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

This work proposes numerical tests which determine whether a two-qubit operator has an atypically simple quantum circuit. Specifically, we describe formulas, written in terms of matrix coefficients, characterizing operators implementable with exactly zero, one, or two controlled-NOT (CNOT) gates and all other gates being one-qubit gates. We give an algorithm for synthesizing two-qubit circuits with an optimal number of CNOT gates and illustrate it on operators appearing in quantum algorithms by Deutsch-Josza, Shor, and Grover. In another application, our explicit numerical tests allow timing a given Hamiltonian to compute a CNOT modulo one-qubit gate, when this is possible.

arXiv:quant-ph/0308045•Physical Review A•Jul 19, 2004•58 citations

Beyond Quantum Shannon: Circuit Construction for General n-Qubit Gates Based on Block ZXZ-Decomposition

Anna M. Krol, Zaid Al-Ars

This paper proposes a new optimized quantum block-ZXZ decomposition method [7,8,10] that results in more optimal quantum circuits than the quantum Shannon decomposition (QSD)[27], which was introduced in 2006 by Shende et al. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only one-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general 3-qubit gate can be decomposed using 19 CNOT gates (rather than 20). For general $n$-qubit gates, the proposed decomposition generates circuits that have $\frac{22}{48}4^n - \frac{3}{2}2^n +\frac{5}{3}$ CNOT gates, which is less that the best known exact decomposition algorithm by $(4^{n-2} -1)/3$ CNOT gates.

arXiv:2403.13692•Mar 20, 2024•1 citation
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
Multiqubit quantum gates are natural quantum operations derived from various decompositions of quantum evolutions. Recently, linear-depth quantum circuits were proposed for an arbitrary nnn-qubit Toffoli gate with ancillary qubits [M. Saeedi and M. Pedram, Phys. Rev. A 87, 062318 (2013)]. Their circuits are based on an equivalent representation of the not gate regardless of the global phase. However, we find that this equivalence cannot be extended to the controlled-not gate or the nnn-qubit Toffoli gate. By reevaluating their circuits, we argue that their linear-depth quantum circuits could realize the joint operations of an nnn-qubit Toffoli gate and an nnn-qubit phase-flip gate.
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++.
This work proposes numerical tests which determine whether a two-qubit operator has an atypically simple quantum circuit. Specifically, we describe formulas, written in terms of matrix coefficients, characterizing operators implementable with exactly zero, one, or two controlled-NOT (CNOT) gates and all other gates being one-qubit gates. We give an algorithm for synthesizing two-qubit circuits with an optimal number of CNOT gates and illustrate it on operators appearing in quantum algorithms by Deutsch-Josza, Shor, and Grover. In another application, our explicit numerical tests allow timing a given Hamiltonian to compute a CNOT modulo one-qubit gate, when this is possible.
This paper proposes a new optimized quantum block-ZXZ decomposition method [7,8,10] that results in more optimal quantum circuits than the quantum Shannon decomposition (QSD)[27], which was introduced in 2006 by Shende et al. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only one-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general 3-qubit gate can be decomposed using 19 CNOT gates (rather than 20). For general nnn-qubit gates, the proposed decomposition generates circuits that have 22484n−322n+53\frac{22}{48}4^n - \frac{3}{2}2^n +\frac{5}{3}4822​4n−23​2n+35​ CNOT gates, which is less that the best known exact decomposition algorithm by (4n−2−1)/3(4^{n-2} -1)/3(4n−2−1)/3 CNOT gates.