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

Quantum Information and Computation

Asymptotically optimal circuits for arbitrary n-qubit diagonal comutations

Stephen S. Bullock, Igor L. Markov

Published Jan 1, 2004• 46 citations
Publisher

Abstract

A unitary operator U = Σj,k uj,k|k〉〈j| is called diagonal when uj,k = 0 unless j = k. The definition extends to quantum computations, where j and k vary over the 2n binary expressions for integers 0,1 ...,2n - 1, given n qubits. Such operators do not affect outcomes of the projective measurement {|j〉〈j|; 0 ≤ j ≤ 2n - 1} but rather create arbitrary relative phases among the computational basis states {|j〉 ; 0 ≤ j ≤ 2n - 1}. Prior quantum circuits for diagonal computations require O(n22n) controlled-not gates and one-qubit Blodl sphere rotations. This work provides a recursive, constructive procedure which inputs U and outputs such a diagram containing 2n+1 - 3 alternating controlled-not gates and one-qubit z- axis Bloch sphere rotations. Up to a factor of two, these circuits are provably the smallest possible. Moreover, the algorithm recognizes certain special case structures within U. For example, if U is a full diagonal tensor of Rz(α) = e-iα/2|0〉〈0| + e-iα/2|1〉〈1| rotations, then a cancellation of controlled-not gates reduces our circuit to the n gate tensor. Moreover, any V ⊕ Rz will output half as many gates as a generic U.

DOI
10.5555/2011572.2011575

Related papers

Smaller Circuits for Arbitrary n-qubit Diagonal Computations

Stephen S. Bullock, Igor L. Markov

A unitary operator U=\sum u_{j,k} |k> ; 0 <= j <= 2^n-1}. These relative phases are often required in applications. Constructing quantum circuits for diagonal computations using standard techniques requires either O(n^2 2^n) controlled-not gates and one-qubit Bloch sphere rotations or else O (n 2^n) such gates and a work qubit. This work provides a recursive, constructive procedure which inputs the matrix coefficients of U and outputs such a diagram containing 2^{n+1}-3 alternating controlled-not gates and one-qubit z-axis Bloch sphere rotations. Up to a factor of two, these circuits are the smallest possible. Moreover, should the computation U be a tensor of diagonal one-qubit computations of the form R_z(α)=e^{-i α/2}|0><0|+ e^{i α/2} |1><1|, then a cancellation of controlled-not gates reduces our circuit to that of an n-qubit tensor.

arXiv:quant-ph/0303039•Quantum Information and Computation•Mar 7, 2003•13 citations

Asymptotically optimal circuits for arbitrary n-qubit diagonal computations

Stephen S. Bullock, Igor L. Markov

A unitary operator $U=\sum_{j,k} u_{j,k} \ket{k} \bra{j}$ is called \emph{diagonal} when $u_{j,k}=0$ unless $j=k$. The definition extends to quantum computations, where $j$ and $k$ vary over the $2^n$ binary expressions for integers $0,1 \cdots ,2^n-1$, given $n$ qubits. Such operators do not affect outcomes of the projective measurement $\{ \ket{j}\bra{j} \; ; \; 0 \leq j \leq 2^n-1\}$ but rather create arbitrary relative phases among the computational basis states $\{ \ket{j} \; ; \; 0 \leq j \leq 2^n-1\}.

Quantum Information and Computation•Jan 1, 2004•37 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

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

The Design and Optimization of Quantum Circuits using the Palindrome Transform

Krysta M. Svore, Alfred V. Aho

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n unitary matrices into efficient circuits of (n−1)-controlled single-qubit and (n−1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative algorithm for minimal (n−1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n − 1)-controlled single-qubit and (n − 1)-controlled-NOT gates.

•Sep 1, 2003•5 citations

Quantum circuits for incompletely specified two-qubit operators

Vivek Shende, Igor L. Markov

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.

arXiv:quant-ph/0401162•Quantum Information and Computation•Jan 1, 2005•50 citations
A unitary operator U = Σj,k uj,k|k〉〈j| is called diagonal when uj,k = 0 unless j = k. The definition extends to quantum computations, where j and k vary over the 2n binary expressions for integers 0,1 ...,2n - 1, given n qubits. Such operators do not affect outcomes of the projective measurement {|j〉〈j|; 0 ≤ j ≤ 2n - 1} but rather create arbitrary relative phases among the computational basis states {|j〉 ; 0 ≤ j ≤ 2n - 1}.
Prior quantum circuits for diagonal computations require O(n22n) controlled-not gates and one-qubit Blodl sphere rotations. This work provides a recursive, constructive procedure which inputs U and outputs such a diagram containing 2n+1 - 3 alternating controlled-not gates and one-qubit z- axis Bloch sphere rotations. Up to a factor of two, these circuits are provably the smallest possible. Moreover, the algorithm recognizes certain special case structures within U. For example, if U is a full diagonal tensor of Rz(α) = e-iα/2|0〉〈0| + e-iα/2|1〉〈1| rotations, then a cancellation of controlled-not gates reduces our circuit to the n gate tensor. Moreover, any V ⊕ Rz will output half as many gates as a generic U.
A unitary operator U=\sum u_{j,k} |k> ; 0 <= j <= 2^n-1}. These relative phases are often required in applications. Constructing quantum circuits for diagonal computations using standard techniques requires either O(n^2 2^n) controlled-not gates and one-qubit Bloch sphere rotations or else O (n 2^n) such gates and a work qubit. This work provides a recursive, constructive procedure which inputs the matrix coefficients of U and outputs such a diagram containing 2^{n+1}-3 alternating controlled-not gates and one-qubit z-axis Bloch sphere rotations. Up to a factor of two, these circuits are the smallest possible. Moreover, should the computation U be a tensor of diagonal one-qubit computations of the form R_z(α)=e^{-i α/2}|0><0|+ e^{i α/2} |1><1|, then a cancellation of controlled-not gates reduces our circuit to that of an n-qubit tensor.
A unitary operator U=∑j,kuj,k∣k⟩⟨j∣U=\sum_{j,k} u_{j,k} \ket{k} \bra{j}U=∑j,k​uj,k​∣k⟩⟨j∣ is called \emph{diagonal} when uj,k=0u_{j,k}=0uj,k​=0 unless j=kj=kj=k. The definition extends to quantum computations, where jjj and kkk vary over the 2n2^n2n binary expressions for integers 0,1⋯ ,2n−10,1 \cdots ,2^n-10,1⋯,2n−1, given nnn qubits. Such operators do not affect outcomes of the projective measurement {∣j⟩⟨j∣  ;  0≤j≤2n−1}\{ \ket{j}\bra{j} \; ; \; 0 \leq j \leq 2^n-1\}{∣j⟩⟨j∣;0≤j≤2n−1} but rather create arbitrary relative phases among the computational basis states $\{ \ket{j} \; ; \; 0 \leq j \leq 2^n-1\}.
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.
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n unitary matrices into efficient circuits of (n−1)-controlled single-qubit and (n−1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative algorithm for minimal (n−1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n − 1)-controlled single-qubit and (n − 1)-controlled-NOT gates.
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.