All quantum operations can run in parallel steps with helper bits
A preprint proves that quantum circuits need only linear depth for any operation, an exponential improvement on the previous best bound by Rosenthal.
Edited by Boris Djordjevic · Paperfoot
In a theory preprint, the authors proved that every n-qubit unitary—a general quantum operation on n quantum bits—can be implemented exactly by a circuit of one- and two-qubit gates in linear depth. Circuit depth measures the sequential steps required when gates operate in parallel, while ancilla qubits are extra helper bits. Whether general unitaries strictly required exponential depth, even with unlimited helper bits, had remained an open question. Using an exponential number of helper bits, the researchers showed, perhaps surprisingly, that all unitaries can be parallelized to polynomial depth. Their linear depth bound is the best possible and exponentially improves on the previous best bound by Rosenthal. If unbounded fan-out gates are permitted, circuit depth falls to a constant. The construction connects unitary synthesis to locally decodable codes, private information retrieval, and bosonic quantum computation.
Why it matters
The mathematical proof resolves an open question in quantum computing theory by showing that exponential circuit depth is not necessary for general quantum operations. It establishes that all operations can be parallelized to linear depth with helper bits, or constant depth if unbounded fan-out gates are permitted.
Caveats
The theoretical construction requires an exponential number of auxiliary quantum bits, and achieving constant depth relies on unbounded fan-out gates that physical hardware may not support. In addition, the findings are presented in a preprint that has not yet undergone peer review.
In this paper
unitary synthesis
What it shows
- Allowing unbounded fan-out gates permits reducing the circuit implementation of all unitaries to constant depth.
Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth.
Abstract
- Unitary synthesis in both oracle and plain circuit models is equivalent for general unitaries, real unitaries, and symmetric real unitaries.
In fact, we show in Lemma 3.1 that unitary synthesis (both in the oracle model and in the plain circuit model) is equivalent for real unitaries, for symmetric real unitaries, and for all unitaries.
Symmetric Encoding of the Unitary
- Any fan-out gate on multiple qubits can be replaced exactly by a logarithmic-depth circuit in the standard model without extra ancillae.
First, any fan-out gate on \ell qubits can be exactly replaced by a \log(\ell) -depth circuit in the standard circuit model (see e.g., ) with no extra ancillae.
3.1 Circuit models and unbounded fan-out
- The harmonic oscillator encoding enables an exact implementation of a target unitary via a three-query algorithm.
Using the harmonic oscillator encoding, we show that our three query algorithm gives an exact implementation of U.
2.4 Getting a Discrete Algorithm
Quoted word for word from the full text on arXiv.
The paper
All Unitaries Have Constant Depth Quantum Circuits
arXiv, Sep 30, 2026, Open access, CC BY, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2609.40351
arXiv:2609.40351v2 in quant-ph
Comments: 47 pages, additional co-author, added boosting to exact implementation, expanded introduction and technical overview
Cite as BibTeX
@misc{nehoran2026unitaries,
title = {All Unitaries Have Constant Depth Quantum Circuits},
author = {Nehoran, Barak and Slote, Joseph and Yuen, Henry},
year = {2026},
eprint = {2609.40351},
archivePrefix = {arXiv},
primaryClass = {quant-ph},
doi = {10.48550/arxiv.2609.40351},
url = {https://arxiv.org/abs/2609.40351}
}