Every textbook proof that a quantum computer can implement any unitary comes with a sobering footnote: a generic n-qubit unitary needs about 2O(n) one- and two-qubit gates, and counting arguments show that exponential gate count cannot be avoided. A quieter question has stayed open: does a generic unitary also need exponential depth, or could those gates be run in parallel if you had enough spare qubits? A new preprint by Barak Nehoran and Henry Yuen (Columbia University) answers it, and the answer is the one many people would not have bet on.
This article was drafted with Claude and fact-checked against the cited primary sources.
Why this paper is worth your time
Classical computation has long known that depth can be traded for size: every Boolean function can be computed by a depth-three circuit of exponentially many AND, OR and NOT gates with unbounded fan-in and fan-out. Whether something similar holds for quantum circuits was unclear, because a quantum circuit must act correctly on superpositions, preserving amplitudes and relative phases, not just on each basis input. Nehoran and Yuen show that the quantum analogue does hold, provided you are willing to pay in ancilla qubits. Along the way they settle a long-standing question about unitary synthesis with classical oracles, by connecting it to locally decodable codes and private information retrieval.
What the paper does
The headline result (Theorem 1.1, made precise as Theorem 5.1) is stated by the authors as follows:
Every n-qubit unitary can be approximated to operator-norm error ε by a circuit of one- and two-qubit gates of depth poly(n, log 1/ε), using 2O(n) ancilla qubits. In the paper’s notation, with N = 2n, the depth is O(log N + log log(N/ε)).
If unbounded fan-out gates are allowed, the same unitaries can be implemented in constant depth.
The engine behind this is a second result (Theorem 1.2): a fixed quantum algorithm that makes only three queries to a diagonal phase oracle (equivalently six queries to a classical Boolean oracle) and, for every N-dimensional unitary U, implements U to error ε when the oracle is chosen to depend on U. The oracle acts on O(N log log(N/ε)) qubits. The paper describes this as the first constant-query algorithm for this “unitary synthesis” task relative to an oracle of roughly N size. Previously, the best known approaches needed either about N queries or a classical oracle on N2 bits, as summarized in the paper.
The key idea: reading a unitary off a quadratic phase
The unitary synthesis problem, posed by Aaronson and Kuperberg, asks whether implementing an arbitrary unitary can be reduced to querying some cleverly chosen classical function. The authors observe that a known “folklore” two-query construction can be viewed as a coherent version of a two-server private-information-retrieval scheme: the oracle hides the matrix entries of U in a linear function, and each query is a query to a locally decodable code.
Their new move is to hide U in a quadratic function instead. After a reduction (Lemma 2.1) showing that it is enough to handle real, symmetric, traceless involutions S, the oracle applies the phase exp(i·vTSv/2) to a register holding a vector v, a “chirp” in signal-processing language. A quadratic polynomial can be locally decoded from three points on a line, in the spirit of Reed–Muller codes: for example, 4f((u+v)/2) − f(u) − f(v) = 2uTSv. The three queries play exactly those three roles.
How the construction works
The algorithm has seven steps: encode, query, Fourier transform, query, Fourier transform, query, decode.
Encoding. The input state on N dimensions is mapped into the single-excitation sector of an N-mode harmonic oscillator, a “generalized one-hot encoding” in which each mode holds either a Gaussian or the first excited state.
The middle sandwich. A query surrounded by two Fourier transforms acts like a query at the midpoint of two points with weight −4. Together with the first and last queries, this realizes the quadratic decoding identity. In the continuous setting the authors prove the exact identity S = i·E†QSFQSFQSE (Theorem 3.1).
Discretization. To make it finite, each mode is sampled on a grid of K = Θ(log(N/ε)) points. Using Poisson summation, the authors bound the operator-norm error by O(N3/2K3/4e−πK/8) (Theorem 4.1).
Shallow implementation. Each step is then compiled into constant depth with fan-out: the one-hot encoding uses fan-out and exact constant-depth AND gates; the quadratic phase splits into N2 pairwise phases computed in parallel and applied as single-qubit Z rotations; and the Fourier transform over ZK is implemented exactly in constant depth using earlier fan-out techniques. Replacing each fan-out gate by a binary tree of CNOTs gives the logarithmic-in-N depth with only one- and two-qubit gates.
Why it matters
As the authors put it, the result is “perhaps surprising from a physics point of view.” Intuitions such as the No Fast-Forwarding Theorem, or the expectation that scrambling systems like the SYK model generate complexity at a maximal rate, suggest that time evolution cannot in general be compressed. The paper explains why there is no contradiction: those intuitions concern circuits with few or no ancillas, or count oracle queries rather than whether they can be parallelized. What the result shows is a clean statement that, for general unitaries, depth can be traded for space.
For complexity theory, the three-query algorithm is significant on its own: it gives a constant-query reduction from implementing any unitary to querying a classical oracle of about N bits. For comparison, the lower bound the paper cites (Lombardi, Ma and Wright) shows only that a reduction to a function on o(N) bits needs more than one query.
Technical perspective (interpretation)
The following is our reading, not a claim made in the paper. The construction makes a quantum analogue of the classical “write out the whole truth table in parallel” trick work, and the price is exactly where one would expect: exponentially many ancillas, plus a classical description of U compiled into the rotation angles. It suggests that lower bounds on depth for general unitaries must use restrictions on space or gate types, not depth alone. The link between unitary synthesis and locally decodable codes also looks like a productive bridge: if better codes or PIR schemes translate into better synthesis algorithms, techniques from coding theory and cryptography may keep feeding into quantum circuit complexity.
Limitations and open questions
Exponential resources remain. The construction uses 2O(n) ancillas (Theorem 5.1 gives width Õ(N2log(N/ε)4)), and the total gate count is still exponential. This is a statement about depth, not a practical compilation method.
Constant depth needs fan-out. The constant-depth version assumes fan-out gates acting on roughly N qubits at once. With ordinary two-qubit gates, the depth is O(log N + log log(N/ε)), which is polynomial in n.
Approximate, U-dependent circuits. The implementation is approximate in operator norm, and the circuit for each U encodes U’s matrix entries in its rotation angles.
Preprint status. This is version 1 of a 35-page preprint and has not yet been peer reviewed.
AI-assistance disclosure. The authors state that ChatGPT and Claude suggested the specific quadratic form that simplified the analysis, and that ChatGPT helped with the Poisson summation argument and the constant-depth Fourier transform; they write that every suggestion was vetted and that they take full responsibility for correctness.
Open questions (our framing): how few ancillas suffice for polynomial depth; whether fewer than three phase queries are possible with an oracle of about N bits; and what this implies for models of complexity growth that allow ancillas.
Paper information
Title: All Unitaries Have Constant Depth Quantum Circuits
Authors: Barak Nehoran, Henry Yuen (Department of Computer Science, Columbia University)
arXiv: 2609.40351v1 [quant-ph], submitted 30 September 2026
Length: 35 pages; theory paper, no code or data
Primary sources
arXiv abstract page: arxiv.org/abs/2609.40351
Full text (HTML): arxiv.org/html/2609.40351v1