All Unitaries Have Constant Depth Quantum Circuits
Abstract
It is well-known that every n-qubit unitary can be implemented by a 2O(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 poly(n) with 2O(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 2n/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.
Related
- The power of constant-depth quantum circuits of unbounded size
- Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure
- Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depth
- Branch-Aware Quantum Constant Propagation for Dynamic Quantum Circuits
- Constant-Per-Layer-Depth MPS-Pretrained Ansatz for Noisy Distributed Quantum Processors
BibTeX
@misc{nehoran2026unitaries,
title = {{All Unitaries Have Constant Depth Quantum Circuits}},
author = {Barak Nehoran and Joseph Slote and Henry Yuen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40351},
eprint = {2609.40351},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40351},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - All Unitaries Have Constant Depth Quantum Circuits
AU - Barak Nehoran
AU - Joseph Slote
AU - Henry Yuen
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.40351
UR - https://arxiv.org/abs/2609.40351
AB - 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 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.
ER -