Regular trajectories, pruning and quantum parity
Fix positive integers and a real . There is an integer such that, for every , every allowed circuit of depth at most on at most total qubits (with ancillary qubits initialized to , one output qubit measured, and all other final registers discarded without restriction) has an input on which its answer equals with probability strictly less than .
The proof in Section 7 is complete and logically sound, relying on the structural results (Proposition 6.5 and Corollary 6.2) proved in earlier sections.
“Theorem 1.1. Fix positive integers d, k, C and a real 0 < ε ≤ 1/2. There is an integer n0 = n0(d, k, C, ε) such that, for every n ≥ n0, every allowed circuit of depth at most d on at most C(n + 1)k total qubits has an input x ∈ {0, 1}n on which its answer equals PARITYn(x) with probability strictly less than 1/2 + ε.” · Show in paper