OAI.QAC.parity_lower_bound

The theorem states that the defined proposition QAC.ParityStatement holds, a measured-output lower bound for computing parity with constant-depth circuits of one-qubit unitaries and unbounded-arity Toffoli gates on polynomially many qubits. Here a physical layer is a list of gates with pairwise disjoint supports (a one-qubit unitary acts on its qubit; a Toffoli with a control set and a target outside it flips the target exactly when all controls are 1), a circuit is a list of layers whose matrices are multiplied with the first layer acting first, and the input is x in {0,1}^n padded with zeros to N qubits. The success probability for a designated output qubit is the total Born probability of all final basis states whose output bit equals the parity of x, summed over all garbage on the other qubits with no cleanliness assumption. The statement is: for every depth bound d, every c ≥ 1 and every 0 < ε ≤ 1/2, there is n₀ such that for all n ≥ n₀, all N with n ≤ N ≤ n^c, all circuits with at most d layers on N qubits, and every output qubit, it is not the case that the success probability is at least 1/2 + ε for every input x in {0,1}^n.