Skip to content
Preprint

All Unitaries Have Constant Depth Quantum Circuits

Sep 2026 · 5 citations · ⚡ 1 influential · 37 references
Physics

Abstract

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth $\mathsf{poly}(n)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in $n$, which is the best possible, and an exponential improvement on the previous best bound of $2^{n/2}$ due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.

View source

Similar papers

Preprint Sep 2026

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any s...

Robert Koenig, M. Tomamichel · 1 citation
Preprint Sep 2026

Fast Cliffords When Your Quantum Memory Is Full

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their jo...

Marten Folkertsma, Ian Mertz, Sergii Strelchuk et al. · 0 citations
Preprint Nov 2026

An Efficient Quantum Algorithm for Preparing Uniform Superpositions over Arbitrary Integer Intervals

We consider exact preparation of the uniform quantum state supported on an arbitrary nonempty interval of integer labels in an $n$-qubit register. For every $0\leq a<a+M\leq2^n$, we give an ancilla-free circuit using only one-qubit gates and singly controlled one-qubit gates. In the logical gate model specified in the...

Alok Shukla, P. Vedula · 0 citations
Sep 2026

Depth-Optimal Quantum Compilation

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 $\delta>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+\delta}(1/\varepsilon))$ cle...

F. Vasconcelos · 1 citation · ⚡1
Preprint Oct 2026

Optimal Quantum-Circuit Synthesis and Implementation of General Unitaries with Parallelized Bitstring-Conditioned Rotations

We theoretically introduce a quantum-circuit synthesis protocol to realize any $n$-qubit transformation $U\in U(2^n)$, up to a diagonal. The resulting circuit is directly native to and optimal in gate count and depth for systems where bitstring-conditioned rotations with tunable angle and axis, $C^{(n-1)}R(\theta,\phi)...

Heikki Suominen, Suman Kundu, Heidi Kivijärvi et al. · 0 citations
Preprint Oct 2026

Ancilla-free optimal quantum adder

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data...

Jun-Hong Nie, Jia-Liang Tang, Xiao-Ming Sun et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.