arXiv:2609.40351
All Unitaries Have Constant Depth Quantum Circuits
Barak Nehoran, Joseph Slote, Henry Yuen
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.
AI Summary
The paper asks whether arbitrary $n$-qubit unitaries require exponential circuit depth even with unlimited ancillas. It proves that every such unitary has a clean, exact implementation of depth $O(n)$ using arbitrary one- and two-qubit gates, all-to-all connectivity, and $2^{O(n)}$ ancilla qubits. The depth is optimal in this model and improves the previous generic upper bound of $2^{n/2}$. Allowing unbounded quantum fan-out reduces the depth to $O(1)$. The construction first addresses unitary synthesis relative to a classical oracle. For dimension $N=2^n$, a fixed algorithm approximately implements any unitary using three diagonal-phase queries on $O(N\log\log(N/\epsilon))$ qubits, or six classical-oracle queries. After reducing to real symmetric involutions, it encodes the input into the single-excitation sector of $N$ harmonic-oscillator modes. Three quadratic-phase operations interleaved with Fourier transforms implement the target transformation exactly in the continuous setting. Discretization uses $K=\Theta(\log(N/\epsilon))$ grid points per coordinate, with error controlled through Poisson summation and Gaussian tails. Encoding, quadratic phases, and discrete Fourier transforms admit constant-depth fan-out implementations with polynomial workspace in $N$ and $\log(1/\epsilon)$. A block-encoding correction followed by one round of oblivious amplitude amplification removes approximation error, adding $\widetilde O(4^n)$ ancillas. Replacing fan-out by CNOT trees gives the standard-model bound. The result trades depth for exponential space; it does not reduce the exponential gate-count requirement for general unitaries. Its circuit-model guarantees are distinct from oracle-query lower bounds for Hamiltonian simulation and from complexity-growth statements restricted to few ancillas.
At a later stage, we began considering variants of the quadratic form oracle, and ChatGPT and Claude suggested this specific form, which made the algorithm and analysis simpler.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 47 pages, additional co-author, added boosting to exact implementation, expanded introduction and technical overview