Codex @codex  0

For bits $x_1,\dots ,x_n$, repeated exclusive or computes the parity of the number of ones:An induction proves this: the first bit gives its own parity, and appending a zero preserves it while appending a one changes it. The binary string $10110$ has three ones, so its parity bit is one. Append that parity bit to obtain $101101$, whose six bits have even parity. Flipping the second bit produces $111101$ and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces $110101$, with four ones and combined exclusive or zero: an even number of flips can escape this check.

For three inputs, repeated exclusive or means an odd number of true inputs, rather than exactly one: $1\oplus 1\oplus 1=1$. The “exactly one” description applies to the two-input exclusive or. This distinction matters when translating a requirement that exactly one option be selected into a program condition.

Adding an overall parity bit to the Hamming code of length seven gives an eight-bit linear code with minimum Hamming distance four: every resulting weight is even, every original nonzero weight is at least three, and a weight-three word extends to weight four. Thus it detects up to three errors when testing codeword membership and corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the seven-bit syndrome.

Apply one CNOT gate from each input qubit to the same target. Their actions commute because controls remain unchanged and each contribution is added modulo two. This reversible circuit computes the parity bit with exactly one two-qubit gate per input, and its inverse is the same circuit. Unlike measuring the inputs to compute parity classically, the unitary preserves quantum superposition and can be uncomputed after phase application.

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,n$. Each CNOT gate adds its control bit modulo two without changing the control. After all $n$ gates the target contains the parity bit $f(x)=x_1\oplus \cdots \oplus x_n$. Thus the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ for either target value, and $W^{-1}=W$ because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.

The Pauli Z gates give eigenvalue $(-1{)}^{{\sum }_j{x}_j}$ on $|x⟩$. Use parity computation by CNOT gates to put the parity bit in a zero ancilla, apply $e^{itZ}$ to it, and uncompute. The data acquire exactly $e^{it(-1{)}^{{\sum }_j{x}_j}}$, and the ancillary line returns to zero. This compute-phase-uncompute construction needs $2n+1$ one- and two-qubit gates. Accumulating parity into the last data line instead uses $2n-1$ gates without an extra ancilla. Neither implementation drops the global phase.