arXiv:2610.06551
Mid-circuit measurements and feedforward implement every unitary exactly in constant depth
Chenfeng Cao
Abstract
Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact $n$-qubit unitary synthesis from $Θ(n)$ to $O(1)$, using arbitrary one- and two-qubit gates and unrestricted ancillary space. Measurements and resets without feedforward remain subject to the circuit causal-cone bound. Our deterministic construction uses single-qubit measurements, $O(1)$ rounds of parity feedforward, and $O(n4^n\log(n+2))$ total qubits, with all ancillas starting and ending in $|0\rangle$. Classical processing is not counted in quantum depth. We teleport only the matrix error of an approximation by Nehoran and Yuen. An exactly prepared ancillary state encodes this error, whose action is added back by coherent interference. At operator-norm error $2^{-n}$, one step of amplitude amplification suffices. Coherent fanout circuits achieve the same constant-depth bound, while circuits using only one- and two-qubit gates attain depth $Θ(n)$ with $O(4^n\log^2(n+2))$ gates. Generic targets require $Ω(4^n/(h+1))$ qubits at depth $h$, even under unrestricted classical control. Our depth-width trade-offs meet this bound within a factor $O(n^2)$ for $1\le h\le2^n$.
AI Summary
The paper asks whether mid-circuit measurements and classical feedforward can implement an arbitrary $n$-qubit unitary exactly in constant quantum depth, given unrestricted ancillas. It uses all-to-all connectivity, arbitrary continuously parameterized one- and two-qubit gates, and nonuniform synthesis; classical computation is excluded from quantum depth. Every unitary admits a deterministic depth-$O(1)$ implementation using single-qubit measurements, $O(1)$ rounds of parity feedforward, and $O(n4^n\log(n+2))$ total qubits, with all ancillas initialized and returned to $|0\rangle$. Clean coherent circuits with unbounded fanout achieve the same bounds. Without feedforward, the optimal worst-case depth is $\Theta(n)$: the construction uses $O(4^n\log^2(n+2))$ gates, while generic targets require depth at least $2n-\log_2 n-O(1)$, even with measurements and unconditional resets. The central construction repairs a constant-depth approximation with operator-norm error $2^{-n}$. An exactly prepared state encodes its matrix residual; teleportation and coherent addition produce a block proportional to the target with normalization at most two. One exact oblivious-amplification step completes the implementation. Fanout is then replaced by measurement-and-parity gadgets. Parameter counting gives generic width $\Omega(4^n/(h+1))$ at depth $h$; synthesis trade-offs approach this within $O(n^2)$ for $1\le h\le2^n$. The model permits exponential width and unrestricted classical compilation. Two-input XOR processing adds depth $O(n)$ per feedforward round. Width $O(4^n)$ at constant quantum depth and near-optimal synthesis using a single feedforward round remain open. Generic exact synthesis is impossible over Clifford+$T$ with computational-basis measurements.
The results and derivations were developed through iterative exchanges with GPT-6 Astra, which contributed substantially to the constructions and proofs and drafted much of the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 23 pages, 3 figures