For an input string , parity is . A physical layer consists of arbitrary one-qubit unitaries and unbounded-arity Toffoli gates with pairwise disjoint supports. A physical circuit on total qubits starts in and measures one designated output qubit in the computational basis, with arbitrary final states allowed on all discarded qubits. Its depth is the number of physical layers. Computing parity with worst-case advantage means returning with probability at least for every . The question is whether fixed depth and polynomially many total qubits permit a fixed positive worst-case advantage. Strict majority is the Boolean function .
For exact parity computation with ancillary qubits all returned to zero, Fang, Fenner, Green, Homer, and Zhang proved a depth lower bound of order .
The preprint proves that, for every fixed nonnegative integer depth , real , and advantage , all sufficiently large exclude a physical circuit with that computes parity with worst-case advantage . Beyond the results of the Lean library, the preprint also rules out fixed-depth circuits with polynomially many total qubits that compute strict majority with uniform-input average success at least for all sufficiently large , for any fixed .
A mismatch count is the operator , for a subset and separately chosen unit vectors . A product projection fixes a unit vector on each qubit of a selected subset and acts as the identity elsewhere. The enlarged depth- circuit model consists of disjoint layers of reflections about product projections , interleaved with products of one-qubit unitaries. The Lean library proves uniform localization: for every fixed depth and real , the operator norm of the transition from zero mismatches to at least mismatches under a product projection conjugated by an enlarged depth- circuit is at most for all sufficiently large , uniformly over the circuits and mismatch counts. The Lean library’s polynomial-size parity theorem states that, for all positive integers and sufficiently large , every physical circuit of depth at most with has an input on which its success probability is strictly less than . Lean has checked every result of the Lean library, including its general parity lower bound, so the Lean library is the reference. Each result on these pages has the Lean library’s statement, with any differing preprint statement given beside it. The preprint is a guide only to the order and names of the results.
QuantumCircuit is a Lean library: 13 items, in six groups. Each has a page written by OctoInform, listed below.
No item matches.