Error detection and correction Created 2026-10-24 Updated 2026-11-05
Error detection and correction adds structured redundancy to messages so that corruption can be noticed or repaired. For a block block code with minimum Hamming distance , all patterns of at most symbol changes are detectable, and all patterns of at most changes are uniquely correctable.
The correction bound follows because radius- Hamming balls around distinct codewords are disjoint when . For example, encoding a bit as or gives distance three, so majority decoding corrects one flipped bit. A single parity bit detects one flipped bit but cannot identify its position; detection and correction require different amounts of information.
For bits , 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 has three ones, so its parity bit is one. Append that parity bit to obtain , whose six bits have even parity. Flipping the second bit produces and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces , 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: . 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.
Extended Hamming code Created 2026-10-14 Updated 2026-11-05
Appending an overall parity bit to a binary Hamming code of redundancy gives the extended Hamming code with parameters
The extension preserves dimension. Every resulting codeword has even Hamming weight, while every original nonzero codeword has weight at least three. A weight-three codeword extends to weight four, proving that the minimum Hamming distance is exactly four.
For , extending the Hamming code of length seven gives the familiar linear code. A membership test detects every error of weight at most three, and nearest-word decoding corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the original syndrome: a nonzero original syndrome with odd overall parity indicates a single error in an original coordinate, whereas a nonzero original syndrome with even overall parity detects a double error, under the assumption that at most two bits changed.
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.
The printed question calls the route a path in a graph and writes , without specifying whether repeated vertices are allowed.[ref] Use the computational reachability convention that a permitted route is a directed walk: repeated vertices are allowed and length counts traversed edges with multiplicity. This matters for the integer parity restriction, because deleting a closed portion of odd length can change the integer parity. The proof below establishes the stated NL-completeness for this convention; it does not establish that claim for a simple path in a graph.
For membership of even-length directed reachability in NL, form the conceptual parity graph with vertex set
and directed edges
After a directed walk of length from , the second coordinate equals . Therefore there is an even-length directed walk from to in exactly when is reachable from in this parity graph. It has vertices. Guess successive edges while storing the original current vertex, one parity bit, and a counter bounded by . If the target pair is reachable, it has a simple path in a graph in this enlarged graph of at most edges. This is an NL procedure; the parity graph need not be materialized.
For NL-hardness, reduce directed reachability by subdividing each directed edge with its own new vertex :
Retain as the endpoints and add no other edges. Every original directed walk of length becomes a directed walk of even length . Conversely, a directed walk between original vertices in the new graph must alternate original and subdivision vertices. Compressing each two-edge segment recovers a directed walk in . Hence
A logspace transducer enumerates the original edges, labels each new vertex by its edge endpoints or its position in the input, and emits its two replacement edges. All labels and counters take bits, and the output is of polynomial size. Thus this is a logspace many-one reduction, proving
As in ordinary reachability, a zero-length directed walk is permitted, so is an immediate yes-instance. Both the membership procedure and the subdivision many-one reduction preserve that case.
All the following polynomial coefficients and sums lie in the field with two elements, so . For the constant polynomial,
For the linear polynomial, subtracting the leading multiple means adding it:
For the quadratic polynomial, first cancel using , leaving ; then cancel using . Thus
The requested polynomial quotients and polynomial remainders are therefore
For a general polynomial , write with constant . Since , polynomial evaluation at gives . This is the polynomial remainder theorem with in the field with two elements. Hence
The polynomial remainder is precisely the parity bit obtained by taking the exclusive or of all the polynomial coefficients.
Use one target ancilla qubit initially in . Apply a CNOT gate from each data qubit to that same target, for . Each CNOT gate adds its control bit modulo two without changing the control. After all gates the target contains the parity bit . Thus the required circuit is the -gate parity fan-in:
This is parity computation by CNOT gates. The circuit also satisfies for either target value, and because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.
Pauli-string phase by parity computation Created 2026-10-07 Updated 2026-11-05
The Pauli Z gates give eigenvalue on . Use parity computation by CNOT gates to put the parity bit in a zero ancilla, apply to it, and uncompute. The data acquire exactly , and the ancillary line returns to zero. This compute-phase-uncompute construction needs one- and two-qubit gates. Accumulating parity into the last data line instead uses gates without an extra ancilla. Neither implementation drops the global phase.