The Setting
A parity circuit receives input qubits among total qubits and measures one output wire . The remaining input wires start at zero, and the unmeasured output wires may contain arbitrary garbage. A classical bit belongs to ; a word of length assigns a bit to each wire. A quantum operator on qubits is a complex matrix indexed by these words, and a single-qubit operator is a complex matrix indexed by bits.
For a bit , the computational basis vector is the single-qubit vector with amplitude one at and zero at the other bit.✦ For a one-qubit vector , the rank-one operator has entries for bits .✦ Tensor products of single-qubit operators are defined by (1). (1)✦
The input wire set , the zero-padded input of a word , and its complementary input word are specified in (2). For any wire set , complements the bits in and fixes all other bits.✦ (2)
The parity is the sum of the input bits modulo two.✦ The bit character is the real-valued function on defined in (3). (3)
For an operator on qubits and a full input word , the output Born probability and parity success probability are the sums over full output words in (4). (4)
A local unitary layer on qubits is a family of one-qubit unitaries, one for every wire; its matrix is . The Hadamard gate , with normalization , and the input Hadamard layer matrix are given in (5), where is the single-qubit identity matrix. (5)
Product Projections and Circuit Classes
Product projection data on qubits consist of a support of wires and one-qubit vectors , normalized for every .✦ For a wire set , the mismatch pattern projection , the product projection , and the high spectral projection are defined in (6); the real cutoff includes equality. (6)
For a full word , the computational basis count is the product projection data on qubits with every wire in its support and local vectors .✦ The zero-outcome count for an output wire among qubits is the product projection data with support and local vector at every wire; write .✦ For an operator , let denote the input Hadamard conjugate of its zero-outcome operator, as in (7). (7)
A local gate on qubits is an operator that applies a one-qubit unitary on a wire and the identity elsewhere; its support is . A Toffoli gate has a control set and a target , with support . The basis action of a Toffoli gate with control set and target is the permutation of full basis words that complements the target bit exactly when every control bit is one and otherwise fixes the word; its gate matrix is the permutation matrix of this action.
A disjoint gate layer is a chronological list of local or Toffoli gates with pairwise disjoint supports.✦ Its layer matrix is the product of its gate matrices.✦ For a chronological circuit list , the circuit matrix is (8); the rightmost matrix acts first. (8)✦
For a natural depth , the enlarged reflection-circuit class consists at depth zero of local layer matrices, and at depth of products , where , is a product of reflections associated with product projections on pairwise disjoint sets of wires, and is a local-layer matrix.✦ Identity layers are allowed.
For a natural depth and real exponents , the uniform localization assertion is the existence of a threshold such that (9) holds for every , every , and all product projection data on qubits. The full localization assertion is the statement that holds for every natural depth and every pair of real exponents .✦ Every operator norm here is the Euclidean operator norm. (9)
The Claim
Theorem 1. Let and let be an output wire. For every operator on qubits and every full input word , the Born diagonal identity is (10). (10)✦
For every operator on qubits, the parity character trace identity is (11). (11)✦
Suppose and is unitary. Let be real numbers such that every input satisfies and . Then the parity advantage satisfies (12). (12)✦
For every operator , input , and real cutoff , the complementary Hadamard entry obeys (13). (13)✦
Assume the full localization assertion. Fix a natural depth bound , a real , and a bias ; the following polynomial-qubit parity lower bound then holds for all input sizes from some natural threshold onward. When and , a chronological list of at most disjoint gate layers has, for each measured output wire , an input satisfying (14). (14)✦
What Is Checked
The identities and entry localization estimate are stated over arbitrary complex operators, the advantage estimate over unitary operators, and the asymptotic statement over disjoint gate layers with zero-initialized ancillas. The single-qubit Hadamard matrix in (5) is unitary.✦