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• 74 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

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•38 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•23 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•21 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•60 citations

Double-bracket quantum algorithms for diagonalization

Marek Gluza

This work proposes double-bracket iterations as a framework for obtaining diagonalizing quantum circuits. Their implementation on a quantum computer consists of interlacing evolutions generated by the input Hamiltonian with diagonal evolutions which can be chosen variationally. No qubit overheads or controlled-unitary operations are needed but the method is recursive which makes the circuit depth grow exponentially with the number of recursion steps. To make near-term implementations viable, the proposal includes optimization of diagonal evolution generators and of recursion step durations. Indeed, thanks to this numerical examples show that the expressive power of double-bracket iterations suffices to approximate eigenstates of relevant quantum models with few recursion steps. Compared to brute-force optimization of unstructured circuits double-bracket iterations do not suffer from the same trainability limitations. Moreover, with an implementation cost lower than required for quantum phase estimation they are more suitable for near-term quantum computing experiments. More broadly, this work opens a pathway for constructing purposeful quantum algorithms based on so-called double-bracket flows also for tasks different from diagonalization and thus enlarges the quantum computing toolkit geared towards practical physics problems.

arXiv:2206.11772•Quantum•Apr 9, 2024•22 citations

Efficient quantum circuits for diagonal unitaries without ancillas

Jonathan Welch, Daniel Greenbaum, 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 give a simple way to construct efficient circuits for diagonal unitaries without ancillas, using a correspondence between Walsh functions and a basis for diagonal operators. This correspondence reduces the problem of constructing the minimal-depth circuit within a given error tolerance, for an arbitrary diagonal unitary in the 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.

arXiv:1306.3991•New Journal of Physics•Mar 31, 2014•134 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=\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.
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.
This work proposes double-bracket iterations as a framework for obtaining diagonalizing quantum circuits. Their implementation on a quantum computer consists of interlacing evolutions generated by the input Hamiltonian with diagonal evolutions which can be chosen variationally. No qubit overheads or controlled-unitary operations are needed but the method is recursive which makes the circuit depth grow exponentially with the number of recursion steps. To make near-term implementations viable, the proposal includes optimization of diagonal evolution generators and of recursion step durations. Indeed, thanks to this numerical examples show that the expressive power of double-bracket iterations suffices to approximate eigenstates of relevant quantum models with few recursion steps. Compared to brute-force optimization of unstructured circuits double-bracket iterations do not suffer from the same trainability limitations. Moreover, with an implementation cost lower than required for quantum phase estimation they are more suitable for near-term quantum computing experiments. More broadly, this work opens a pathway for constructing purposeful quantum algorithms based on so-called double-bracket flows also for tasks different from diagonalization and thus enlarges the quantum computing toolkit geared towards practical physics problems.
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 give a simple way to construct efficient circuits for diagonal unitaries without ancillas, using a correspondence between Walsh functions and a basis for diagonal operators. This correspondence reduces the problem of constructing the minimal-depth circuit within a given error tolerance, for an arbitrary diagonal unitary in the 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.