The Setting
Parity computation asks for the parity of an -bit input at one measured output wire of a circuit on qubits. The total counts both input qubits and ancillas.
A bit is an element of , with addition modulo two.✦ An -bit word is a function from the wire set to the bits.✦ An -qubit operator is a complex matrix indexed by -bit words✦, and a single-qubit operator is a complex matrix.✦ The tensor product of single-qubit operators is the -qubit operator with entries given by (1). (1)✦
A gate on qubits is either a single-qubit unitary on a wire , or a Toffoli gate with a control set and a target wire .✦ The Toffoli basis map is the map on -bit words defined by (2). (2)✦
The gate matrix of a gate is the operator specified in (3), where is the single-qubit identity. (3)✦ The support of a local gate on is , and the support of a Toffoli gate with controls and target is .✦
A physical layer is a list of gates with pairwise disjoint supports.✦ For a physical layer and a circuit with chronological layer list , the layer matrix and circuit matrix are the operators given by the products in (4); the rightmost matrix acts first. The depth of a circuit with chronological layer list is . (4) with an empty product equal to the identity.
For and an -bit word , the zero-padded input is the -bit word and the parity is the bit defined by (5). (5)
The parity success probability of an -qubit operator , an output wire and an input is the sum in (6) over full output words with the correct measured bit. (6)✦
The Claim
Theorem 1. Fix a depth , a real exponent , and a real number . For all sufficiently large , let be a circuit of depth at most on qubits, where , and let be any output wire. There is an input such that (7)✦
Theorem 2. Fix positive integers . For all sufficiently large , let be a circuit of depth at most on qubits, where , and let be any output wire. There is an input such that (8)✦
What Is Checked
The parity hardness statements (7) and (8) are stated over disjoint gate layers with the circuit matrices (4) and the parity success probability (6).