Linear Growth of Quantum Circuit Complexity
summary
Shows a rigorous linear lower bound on exact quantum circuit complexity for Haar-random two‑qubit gates arranged in local architectures, holding with probability one until the dimension ceiling ≈4^n. Proof compares algebraic dimensions of achievable-unitary images (Tarski‑Seidenberg) and reduces to Jacobian rank by inserting Pauli strings; a specific Clifford construction produces many independent partial derivatives across backwards light cones. Brickwork circuits give a bound scaling like gates/(9 N^2). Result requires exact implementation (no approximate robustness) and fails for discrete gate sets.
AI-written summary · about