All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran; Henry Yuen; Joseph Slote

REVIEW

All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran, Joseph Slote, Henry Yuen

Quantum Physics · Submitted 30 Sep 2026

Pith's verdict: The qualitative claim is real and the load-bearing step (Lemma 4.2) survives scrutiny; the continuous-part gaps are presentational, not fatal, and this deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 1, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.40351 (version 2)

Pith ID4W3SDJ5E, Pith's permanent record of this paper and its review

CitationBarak Nehoran, Henry Yuen, Joseph Slote. "All Unitaries Have Constant Depth Quantum Circuits." arXiv:2609.40351 (2026). https://pith.science/paper/4W3SDJ5E

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Short version: this resolves the open question of whether exponential depth is necessary for general unitaries with unbounded ancillas, and the answer is no. If the proof holds, every n-qubit unitary is implementable in polylog depth with 2^{O(n)} ancillas, and in constant depth with fan-out. That is a field-level result.

What is new: the three-query synthesis against a quadratic-phase oracle on Õ(N) qubits is the first constant-query construction, breaking the folklore √N-query and N²-bit bounds, and the PIR / locally-decodable-code connection is genuinely insightful. The shallow implementation (Theorem 5.1) with the reduction of Theorem 2.1 is a real contribution on its own. I agree the novelty and significance sit at 8.

The structure holds up. I checked the reader's Fresnel worry at Eq 33. It is a real presentational gap — the oscillatory integrals at Eqs 31–41 are asserted rather than derived, and the complex-shift Gaussians deserve justification — but Theorem 4.1 does not lean on Theorem 3.1. The discretized proof goes through the algebraic ideal-isometry identity (Eq 52) plus Lemma 4.2. So the continuous gap is presentational, not load-bearing. A referee should still ask for the analytic cleanup, since Theorem 3.1 is stated as exact, but the headline does not ride on it.

The load-bearing spot is Lemma 4.2's tail bound, and its structure is right: the (2|m|−1)² ≥ 1+8(r−1) split, the factorization into one-dimensional Gaussian-tail sums, the √N from the ℓ¹ bound. What I could not certify by reading is the constant bookkeeping — the "sufficiently large constant" in K ≥ C log(N+1) needs πC/8 ≥ 2, and the behavior of β_K near the threshold. Off-by-constant there changes the constant inside the polylog depth, not the qualitative claim. Proportionate concern, not fatal.

Algorithm 6's exact QFT decoder is intricate but the exactness argument is clean: for a ≠ x the least significant differing bit forces d_a = 0 deterministically, so the decoder is genuinely exact. The width is enormous (Õ(N² log⁴(N/ε))), but that is the point — trading space for depth.

The AI disclosure is unusual but honest, and it is a disclosure, not a scientific claim. No evidence of fitting, no invented entities, low circularity.

Who it is for: circuit complexity and unitary-synthesis researchers. My recommendation: send it to a top venue. The referee brief should be Lemma 4.2's constants and the Theorem 3.1 analytic cleanup. Nothing I saw suggests the qualitative claim is wrong.

Referee report

Significance

If correct, this is a major advance: it would show that the exponential gate complexity of arbitrary unitaries can be parallelized away at the cost of exponentially many ancillas, and that unrestricted fan-out gives constant depth. The proof strategy is credible and largely self-contained. I verified the algebraic identity in Eq. (52), which reduces Theorem 4.1 to the tail bound of Lemma 4.2, and I verified the exactness argument for the one-hot decoding in Step 3 of Algorithm 6: for candidate a=x every tested qubit is deterministic, and for a≠x the least significant differing bit makes the conjunction deterministically false. The construction is parameter-free in the sense that K is chosen from the error budget rather than fitted. The only apparent rigor gap, the Fresnel evaluation in Theorem 3.1, is not load-bearing: Theorem 4.1 is proved independently through the ideal-isometry comparison and Gaussian/Poisson tail bounds.

Minor objections (6)

[§3.5, Eq. (33)] The proof of Theorem 3.1 evaluates ∫ e^{(i/2)w^T S w}dw as (2π)^{N/2} with the justification 'since Tr(S)=0'; this is a non-absolutely-convergent oscillatory integral and should be justified by an explicit Fresnel regularization or the theorem should be labelled as a formal continuous identity. Since Theorem 4.1 does not use Theorem 3.1, this is a presentation and rigor issue rather than a block to the main claim.
[§2.4 and §2.5] The subsections 'The Oracle Model' and 'The Constant Depth Model' appear in the table of contents but contain no text in the manuscript; the paper should define the oracle model and the exact depth and width conventions for circuits with unbounded fan-out before Theorem 5.1 is stated.
[§4.2, proof of Theorem 4.1] The proof cites 'Theorem 4.2' and 'Theorem 4.3' where Lemma 4.2 and Lemma 4.3 are meant; the cross-references should be corrected throughout Section 4.
[§5.3.1, Algorithm 6] The modular-sum cleanup in Step 6 is correct, but the inference from '[TT16, Lemma 4]' to width O(K^4) is compressed; the counting circuit on O(K^2) bits and its workspace should be described explicitly so the stated width O(N K^4) for the shallow Fourier transform is directly accounted for.
[§2.1, Lemma 2.1] The reductions (1)⇒(3) and (3)⇒(4) are dismissed as 'trivial'; since the traceless condition is used critically in Eq. (33), the trace-zero embedding should be written out.
[Throughout] There are several typos and imprecise labels: 'Berstein-Vazirani' should be 'Bernstein-Vazirani', 'Four our current purposes' should be 'For our current purposes', and Theorem 2.1 is sometimes referenced where Lemma 2.1 is meant.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper claims that, with enough ancilla qubits, every n-qubit unitary can be approximated to operator-norm error ε by a quantum circuit of depth polynomial in n and logarithmic in 1/ε — and constant depth if fan-out gates are allowed.

The reading

This paper claims that every $n$-qubit unitary map can be approximated to operator-norm error $\epsilon$ by a quantum circuit whose depth is polynomial in $n$ and logarithmic in $1/\epsilon$, provided one is willing to use $2^{O(n)}$ ancilla qubits. With unbounded fan-out gates, the same construction runs in constant depth. Counting arguments have long shown that most unitaries need exponentially many gates, but those arguments bound gate count, not depth; the paper shows the exponentially many gates can be laid out in parallel. The route goes through a three-query unitary-synthesis algorithm: a diagonal quadratic-phase oracle encodes the matrix entries of the target unitary into a quadratic form, and three queries with Fourier transforms between them decode those entries exactly in the continuous limit.

What carries the argument

The load-bearing object is the operator identity $S = iE^\dagger Q_S F Q_S F Q_S E$, where $E$ is an isometry encoding $\mathbb{C}^N$ into the single-excitation sector of the $N$-mode harmonic oscillator — a one-hot-style encoding whose per-mode states $|h_0\rangle$ and $|h_1\rangle$ are Gaussian wavefunctions — and $Q_S$ is the diagonal quadratic-phase oracle acting as $|v\rangle \mapsto e^{\frac{i}{2}v^T S v}|v\rangle$, with $F$ the continuous Fourier transform. Three queries at $u$, the midpoint $(u+v)/2$, and $v$ implement a quadratic, Reed-Muller-style polynomial decoding of the matrix entries $\langle y|S|x\rangle$, the quadratic analogue of the linear decoding in the folklore Bernstein-Vazirani/PIR construction. Discretization samples a grid of spacing $\Delta=\sqrt{2\pi/K}$ along each dimension, and the error is bounded through Poisson summation over the lattice tails in both the position and Fourier bases, each tail decaying as $O(K^{3/4}e^{-\pi K/8})$.

Extended reading notes

Core claim

The central claim, Theorem 5.1, is that for every unitary $U\in U(N)$ and every tolerance $\epsilon>0$ there is a circuit of one- and two-qubit gates of depth $O(\log N + \log\log(N/\epsilon))$ and width $\tilde{O}(N^2\log(N/\epsilon)^4)$ satisfying $\|U\otimes|0\rangle - C_U(I\otimes|0\rangle)\|\le\epsilon$, plus a second circuit of constant depth using fan-out gates of the same width. The technical core is a three-query synthesis algorithm: encode the input into the single-excitation sector of an $N$-mode harmonic oscillator, apply a diagonal quadratic-phase oracle three times with Fourier transforms between applications, and decode. In the continuous limit this is the exact identity $S = iE^\dagger Q_S F Q_S F Q_S E$ for traceless real symmetric $S$ (Theorem 3.1), and its discretized version on a grid of $K=\Theta(\log(N/\epsilon))$ points per dimension carries operator-norm error $O(N^{3/2}K^{3/4}e^{-\pi K/8})\le\epsilon^2$ (Theorem 4.1). Showing the encoding, the diagonal phase, and the Fourier transform each admit constant-depth implementations with fan-out — or logarithmic depth with CNOT trees — yields the shallow-circuit theorem.

Load-bearing premise

The exactness of the continuous three-query identity in Theorem 3.1 rests on evaluating non-absolutely-convergent oscillatory integrals as though they converged absolutely, in particular $\int_{\mathbb{R}^N} e^{\frac{i}{2}w^T S w}\,dw = (2\pi)^{N/2}$ at the step marked 'since $\operatorname{Tr}(S)=0$', alongside the completion-of-square and integration-by-parts steps, and the finite algorithm only approximates this continuous identity.

Editorial extensions

If this is right

Every $n$-qubit unitary can be implemented in depth $\mathrm{poly}(n,\log 1/\epsilon)$ using $2^{O(n)}$ ancillas, so exponential depth is never required once ancillas are free.
With unbounded fan-out gates, depth falls to a constant independent of $n$ and $\epsilon$, at the same width.
The three-query algorithm is the first constant-query unitary-synthesis procedure relative to a diagonal phase oracle of $\tilde{O}(N)$ bits, giving six queries to a classical oracle.
No-fast-forwarding intuitions drawn from oracle-based Hamiltonian simulation do not transfer to the regime of many ancillas and arbitrary unitaries.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the theorem survives scrutiny, the implied depth-versus-width tradeoff is extreme and one-way: exponentially many ancillas collapse depth to near-constant, and a natural next question is the minimal ancilla budget below which poly-logarithmic depth becomes impossible.
The PIR/LDC reading suggests the three-query structure is tight only if one-query lower bounds can be pushed to rule out two queries, and that higher-degree (higher-order Reed-Muller) phases might encode richer families of maps than unitaries alone.
The largest technical risk is the analytic evaluation of oscillatory integrals; a convergence-justified reformulation would settle whether the continuous identity holds up to a global phase, which is all the discretized version actually needs.

Original 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-01: 1 request, 5,048 input tokens.

What the abstract itself states, as probabilities: claims first 0.11 · states limitation 0.42 · human participants 0.01 · controlled comparison 0.04 · randomized assignment 0.01 · states quantitative result 0.97 · compares with prior results 0.90 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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 \emph{necessary} for general unitaries, even when allowing for unlimited number of ancilla qubits. We show, perhaps surprisingly, that all unitaries can be approximated to operator norm $\epsilon$ by a circuit of one- and two-qubit gates of depth $\poly(n,\log 1/\epsilon)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. Moreover, if we allow unbounded fan-out gates, these circuits can be reduced further to \emph{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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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.	background 1.00	0.03	0.02	asserted 1.00
s1	It has been open whether exponential depth is \emph{necessary} for general unitaries, even when allowing for unlimited number of ancilla qubits.	gap 1.00	0.03	0.02	asserted 0.63
s2	We show, perhaps surprisingly, that all unitaries can be approximated to operator norm $\epsilon$ by a circuit of one- and two-qubit gates of depth $\poly(n,\log 1/\epsilon)$ with $2^{O(n)}$ ancilla qubits.	result 0.88	0.96	0.86	asserted 1.00
s3	In other words, every $n$-qubit unitary can be parallelized to polynomial depth.	interpretation 0.86	0.83	0.46	asserted 1.00
s4	Moreover, if we allow unbounded fan-out gates, these circuits can be reduced further to \emph{constant} depth.	result 0.97	0.89	0.27	asserted 0.97
s5	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.	method 0.93	0.82	0.02	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Mid-circuit measurements and feedforward implement every unitary exactly in constant depth
quant-ph 2026-10 conditional novelty 8.0 of 10

Any n-qubit unitary can be implemented exactly in constant quantum depth using single-qubit measurements with parity feedforward and O(n 4^n log n) ancillas, versus the Theta(n) depth required without feedforward.
A simple proof of unitary parallelization via port-based teleportation
quant-ph 2026-10 accept novelty 7.0 of 10

A single-reflection protocol realizes port-based teleportation with polylogarithmic depth, enabling a simple proof of unitary parallelization.
$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation
quant-ph 2026-10 accept novelty 7.0 of 10

Worst-case Clifford+T T-count for arbitrary n-qubit unitary synthesis is improved from O~(N^{5/4}) to O~(N^{8/7}) at constant operator-norm error, with a matching lower bound in a sequential block-SELECT model.
State Synthesis with an NP oracle
quant-ph 2026-11 reject novelty 6.0 of 10

A claimed polynomial-time quantum algorithm prepares arbitrary n-qubit states to inverse-exponential error using an NP oracle plus an amplitude-entry oracle, improving the previous PP oracle upper bound at the cost of...

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.