Shallow Quantum Circuits and Causal ConesTextbook
## Motivation A quantum circuit of depth $d$ built from gates of fan-in at most two cannot let an output wire depend on more than $2^d$ input wires. The argument is folklore and takes a paragraph on paper: the *causal cone* of the measured wire grows by at most a factor of two per layer. Formalizing it exposes a subtlety that the paper argument hides, and that is what this mission is about. ## The subtlety Define the backward cone step of a wire set $S$ through a layer $l$ by adjoining the support of every gate of $l$ that meets $S$. There is a choice here: test each gate against the **incoming** set $S$, or against the **partially accumulated** cone. Testing against the accumulator over-approximates, and the doubling bound fails. Testing against the incoming set gives the bound — but is only *correct* when the gates within a layer act on pairwise disjoint wires. Without that hypothesis (`LayerOk`) the semantic statement is false, and the counterexample is small: on three wires, the single layer `[cnot 2 1, cnot 1 0]` has cone $\{0,1\}$ around wire $0$, yet wire $0$ ends up holding $x_0 \oplus x_1 \oplus x_2$. So the cone under-approximates the true dependence. This mission's development carries `LayerOk` throughout, and the counterexample is recorded in the source. ## What is formalized Layered circuits over $\{H, S, T, \mathrm{CNOT}\}$ on $n$ wires, with states as amplitude functions on bit-strings and no tensor products anywhere. On top of that: - the combinatorial half — one layer at most doubles the cone, hence $|\mathrm{cone}| \le 2^{d}\,|S|$; - norm preservation, so that `acceptProb` is a genuine probability in $[0,1]$; - the semantic half — inputs agreeing on the causal cone of the output wire are accepted with *equal probability*. The semantic half is proved in the Heisenberg picture. The measurement observable is conjugated backwards through the circuit and its support tracked: a gate meeting the support enlarges it by that gate's own wires, and a gate missing it **commutes** with the observable and cancels against its own adjoint. That cancellation is the reason the non-cascading cone step is correct, and it is why unitarity of the gate set is needed at the $2^n$-dimensional level rather than gate by gate. Supporting this is a small reusable algebra of local operators: locality is monotone, closed under adjoint and product, and disjointly supported operators commute. ## The frontier The published depth bound assumes each input wire lies in the *syntactic* cone of the output. That is weaker than saying the wire *matters*. Milestone 1 asks for the semantically honest version, stated in terms of genuine functional dependence; the bridge is the semantic cone theorem already in the development. Beyond that, the natural continuations are the same argument for fan-in-$k$ gates ($|\mathrm{cone}| \le k^{d}$), for geometrically local circuits where cone growth is linear rather than exponential, and ultimately the Bravyi–Gosset–König separation $\mathrm{QNC}^{0} \not\subset \mathrm{NC}^{0}$ — which needs machinery (non-local games, magic squares) that this development deliberately does not build.