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 computations

Stephen S. Bullock, Igor L. Markov

Published Jan 1, 2004• 37 citations
Publisher

Abstract

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\}.

DOI
10.26421/qic4.1-3

Related papers

Asymptotically optimal circuits for arbitrary n-qubit diagonal comutations

Stephen S. Bullock, Igor L. Markov

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.

Quantum Information and Computation•Jan 1, 2004•46 citations

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

DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS

YOSHIFUMI NAKATA, Mio Murao

We study efficient generations of random diagonal-unitary matrices, an ensemble of unitary matrices diagonal in a given basis with randomly distributed phases for their eigenvalues. Despite the simple algebraic structure, they cannot be achieved by quantum circuits composed of a few-qubit diagonal gates. We introduce diagonal-unitaryt-designs and present two quantum circuits that implement diagonal-unitary 2-design with the computational basis in N-qubit systems. One is composed of single-qubit diagonal gates and controlled-phase gates with randomized phases, which achieves an exact diagonal-unitary 2-design after applying the gates on all pairs of qubits. The number of required gates is N(N - 1)/2. If the controlled-Z gates are used instead of the controlled-phase gates, the circuit cannot achieve an exact 2-design, but achieves an ϵ-approximate 2-design by applying gates on randomly selected pairs of qubits. Due to the random choice of pairs, the circuit obtains extra randomness and the required number of gates is at most O(N2(N + log 1/∊)). We also provide an application of the circuits, a protocol of generating an exact 2-design of random states by combining the circuits with a simple classical procedure requiring O(N) random classical bits.

arXiv:1206.4451•International Journal of Quantum Information•Oct 1, 2013•18 citations

Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count

Shihao Zhang, Kai Huang, Lvzhou Li

Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, ${R}_{Z}$} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.

arXiv:2212.01002•Physical Review A•Apr 1, 2024•12 citations

Quantum circuit optimization for unitary operators over non-adjacent qudits

Giuseppe Sergioli

Within the general context of the architecture in quantum computer design, this paper aims is to provide a general strategy to obtain a block-matrix representation of quantum gates applied to qubits placed in arbitrary positions over an arbitrary dimensional input state. The model is also extended to the framework of quantum computation with qudits. An application in the context of the quantum computational logic is provided.

arXiv:1711.09765•Nov 27, 2017•1 citation

Efficient quantum circuits for diagonal unitaries without ancillas

Jonathan Welch, Greenbaum, Daniel, Sarah Mostame +1 more

The accurate evaluation of diagonal unitary operators is often the most resource-intensive element of quantum algorithms such as real-space quantum simulation and Grover search. Efficient circuits have been demonstrated in some cases but generally require ancilla registers, which can dominate the qubit resources. In this paper, we point out a correspondence between Walsh functions and basis for diagonal operators that gives a simple way to construct efficient circuits for diagonal unitaries without ancillas. This correspondence reduces the problem of constructing the minimal-depth circuit within a given error tolerance, for an arbitrary diagonal unitary eif(ˆx) in the |xi basis, to that of finding the minimal-length Walsh-series approximation to the function f(x). We apply this approach to the quantum simulation of the classical Eckart barrier problem of quantum chemistry, demonstrating that high-fidelity quantum simulations can be achieved with few qubits and low depth.

•Jan 1, 2014•35 citations
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}.
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.
We study efficient generations of random diagonal-unitary matrices, an ensemble of unitary matrices diagonal in a given basis with randomly distributed phases for their eigenvalues. Despite the simple algebraic structure, they cannot be achieved by quantum circuits composed of a few-qubit diagonal gates. We introduce diagonal-unitaryt-designs and present two quantum circuits that implement diagonal-unitary 2-design with the computational basis in N-qubit systems. One is composed of single-qubit diagonal gates and controlled-phase gates with randomized phases, which achieves an exact diagonal-unitary 2-design after applying the gates on all pairs of qubits. The number of required gates is N(N - 1)/2. If the controlled-Z gates are used instead of the controlled-phase gates, the circuit cannot achieve an exact 2-design, but achieves an ϵ-approximate 2-design by applying gates on randomly selected pairs of qubits. Due to the random choice of pairs, the circuit obtains extra randomness and the required number of gates is at most O(N2(N + log 1/∊)). We also provide an application of the circuits, a protocol of generating an exact 2-design of random states by combining the circuits with a simple classical procedure requiring O(N) random classical bits.
Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, RZ{R}_{Z}RZ​} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.
The accurate evaluation of diagonal unitary operators is often the most resource-intensive element of quantum algorithms such as real-space quantum simulation and Grover search. Efficient circuits have been demonstrated in some cases but generally require ancilla registers, which can dominate the qubit resources. In this paper, we point out a correspondence between Walsh functions and basis for diagonal operators that gives a simple way to construct efficient circuits for diagonal unitaries without ancillas. This correspondence reduces the problem of constructing the minimal-depth circuit within a given error tolerance, for an arbitrary diagonal unitary eif(ˆx) in the |xi basis, to that of finding the minimal-length Walsh-series approximation to the function f(x). We apply this approach to the quantum simulation of the classical Eckart barrier problem of quantum chemistry, demonstrating that high-fidelity quantum simulations can be achieved with few qubits and low depth.