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:1306.3991 · New Journal of Physics

Efficient quantum circuits for diagonal unitaries without ancillas

Jonathan Welch, Daniel Greenbaum, Sarah Mostame, Alán Aspuru‐Guzik

Published Mar 31, 2014• 134 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1367-2630/16/3/033040

Related papers

Efficient Quantum Circuits for Non-Unitary and Unitary Diagonal Operators with Space-Time-Accuracy Trade-Offs

Julien Zylberman, Ugo Nzongani, Andrea Simonetto +1 more

Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms with applications in the resolution of partial differential equations, Hamiltonian simulations, the loading of classical data on quantum computers (quantum state preparation), and many others. In this paper, we introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits. The depth, i.e., the number of layers of quantum gates of the quantum circuit, is reducible with respect either to the width, i.e., the number of ancilla qubits, or to the accuracy between the implemented operator and the target one. While exact methods have an optimal exponential scaling either in terms of size, i.e., the total number of primitive quantum gates, or width, approximate methods prove to be efficient for the class of diagonal operators depending on smooth, at least differentiable, functions. Our approach is general enough to allow any method for diagonal operators to become adjustable-depth or approximate, decreasing the depth of the circuit by increasing its width or its approximation level. This feature offers flexibility and can match with the hardware limitations in coherence time or cumulative gate error. We illustrate these methods by performing quantum state preparation and non-unitary-real-space simulation of the diffusion equation. This simulation paves the way to efficient implementations of stochastic models useful in physics, chemistry, biology, image processing, and finance.

arXiv:2404.02819•ACM Transactions on Quantum Computing•Feb 19, 2025•18 citations

On the Synthesis of Quantum Circuits for Diagonal Operators in Quantum Computation

Jonathan Welch

Diagonal unitary operators are commonly found in many quantum algorithms. They find application as analytical potential operators for quantum simulation, as well as for complex oracles used in quantum searches. However, in order to implement a quantum algorithm on a given quantum device, each operator must be decomposed into a sequence of fault-tolerant, device-level instructions. In general, to implement an $n$-qubit diagonal unitary {\\em exactly} on a quantum computer generally requires $2^{n+1}-3$ one- and two-qubit gates. However, for most practical implementations of diagonal unitaries, some degree of approximation will be necessary if the circuit is to be efficient. In this thesis we develop two complementary methods for the approximate synthesis of quantum circuits for diagonal unitaries. We show how to apply these techniques to real-space quantum simulation and show how efficient high fidelity quantum simulations can be implemented with low-depth quantum circuits.

•Sep 29, 2015•2 citations

Low-Depth Random Unitaries without Ancillae

Zhenyu Du, Siyuan Cheng, Xiongfeng Ma

Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate $k$-designs on $n$ qubits, our circuits achieve a depth of $\widetilde{O} (k) (\log n)^{1/δ}$ on $δ$-dimensional architectures and $\widetilde{O}(k) \log \log n$ with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact $k$-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.

quant-pharXiv:2609.06528•Sep 8, 2026•2 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

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•1 citation

High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization

Mathias Weiden, Justin Kalloor, John David Kubiatowicz +2 more

Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.

arXiv:2409.00433•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•9 citations
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.
Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms with applications in the resolution of partial differential equations, Hamiltonian simulations, the loading of classical data on quantum computers (quantum state preparation), and many others. In this paper, we introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits. The depth, i.e., the number of layers of quantum gates of the quantum circuit, is reducible with respect either to the width, i.e., the number of ancilla qubits, or to the accuracy between the implemented operator and the target one. While exact methods have an optimal exponential scaling either in terms of size, i.e., the total number of primitive quantum gates, or width, approximate methods prove to be efficient for the class of diagonal operators depending on smooth, at least differentiable, functions. Our approach is general enough to allow any method for diagonal operators to become adjustable-depth or approximate, decreasing the depth of the circuit by increasing its width or its approximation level. This feature offers flexibility and can match with the hardware limitations in coherence time or cumulative gate error. We illustrate these methods by performing quantum state preparation and non-unitary-real-space simulation of the diffusion equation. This simulation paves the way to efficient implementations of stochastic models useful in physics, chemistry, biology, image processing, and finance.
Diagonal unitary operators are commonly found in many quantum algorithms. They find application as analytical potential operators for quantum simulation, as well as for complex oracles used in quantum searches. However, in order to implement a quantum algorithm on a given quantum device, each operator must be decomposed into a sequence of fault-tolerant, device-level instructions. In general, to implement an nnn-qubit diagonal unitary {\\em exactly} on a quantum computer generally requires 2n+1−32^{n+1}-32n+1−3 one- and two-qubit gates. However, for most practical implementations of diagonal unitaries, some degree of approximation will be necessary if the circuit is to be efficient. In this thesis we develop two complementary methods for the approximate synthesis of quantum circuits for diagonal unitaries. We show how to apply these techniques to real-space quantum simulation and show how efficient high fidelity quantum simulations can be implemented with low-depth quantum circuits.
Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate kkk-designs on nnn qubits, our circuits achieve a depth of O~(k)(log⁡n)1/δ\widetilde{O} (k) (\log n)^{1/δ}O(k)(logn)1/δ on δδδ-dimensional architectures and O~(k)log⁡log⁡n\widetilde{O}(k) \log \log nO(k)loglogn with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact kkk-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.
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.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.