Reed–Solomon DQI decoder

The input is the 70 syndromes of a Reed–Solomon code over 𝔽_2¹², one 12-qubit word each, 840 qubits in all. They determine an error word e with at most 35 nonzero symbols. The circuit applies the sign (−1)^⟨c,e⟩ for a fixed mask c and returns every ancilla to zero. The error word has 49,140 bits, but the task needs one bit of it.

Few registers persist. The working discrepancy Dw, the signed counter dW, and three scratch qubits stay held. The locator σ, the template bank, and the history stack belong to BM and take wires only when first touched. The evaluator ω gets no register of its own: it will live in the first 35 syndrome words.

The parity of position j is a field trace, ⟨c_j, e_j⟩ = Tr(μ_je_j). An interpolation polynomial U of degree 70 matches μ_j at 70 positions, and its share of the phase equals Σ_i Tr(u_iS_i), a fixed parity of syndrome bits. Z gates apply it. The residual mask vanishes at 71 positions, so the later scan has 4,024 positions with work to do.

Berlekamp–Massey finds the locator σ, whose roots mark the error positions, by reading one syndrome per round. Each round computes the discrepancy Δ, the amount by which the current σ fails to predict the new syndrome. It then corrects σ with a multiple of an earlier locator τ, the template, shifted by z once per round. bm.run() emits the 70 rounds and records every step in a journal for the later reverse pass.

Each round touches only the coefficients that can already be active. After r syndromes a typical locator has degree near r/2, well below the worst case min(r, 35). Classical simulation over 403 million sampled inputs fixed a coefficient window per round. A rare input crosses a window, at a rate of 3.8 × 10⁻⁵, and can then get a wrong phase; the circuit still restores the syndrome.

monicize divides the locator coefficients σ₁ to σ₃₅ by σ₀. This keeps the roots and leaves the ratio ω/σ′ unchanged. On an approximate path σ₀ can be zero; the stage then scales by one, so it stays reversible on every input.

The relation σS = ω mod z⁷⁰ gives the evaluator. Coefficient i of σS equals S_i+1 plus a function of earlier syndromes, so the map is triangular and runs in place. The first 35 words become ω. On every correct decode the last 35 become zero, 420 qubits of workspace for the next stage.

The blocks are middle products. Each evaluates its two operands at fixed field points with CNOTs, multiplies the values, and interpolates only the requested band. Only products of two data-dependent values cost Toffolis.

Forney's formula recovers an error value as ω(β)/σ′(β) at a root β. A division at every position would dominate the cost. The circuit instead computes, once, a polynomial Ψ with Ψσ′ ≡ 1 mod σ, which equals 1/σ′ at every root.

In characteristic 2 squaring is linear, so σ = E² + zO² with E_i = √σ_2i and O_i = √σ_2i+1. The square roots rewrite the locator words in place, and σ′ = O². If AE + BO = 1, then Ψ = B² + zA². The Euclidean algorithm thus runs on halves of degree 17 that fit in 18 words. A barrel shift by m = ⌊(35 − L)/2⌋ gives every input the same shape; the counter already holds m in bits 2 to 6 after adding two.

The forward pass runs 17 fixed blocks of two eliminations and parks each quotient in the word it clears. The cofactors grow in the zeroed syndrome words: a seed places 1/h for the last pivot h, and build_R replays the forward journal backward while it accumulates the pair. One extra word completes the two 18-word registers. The circuit reaches its peak of 1,837 qubits in these passes.

The scan visits all 4,095 positions and skips the point body at the 71 positions the linear phase removed. At each of the other 4,024 it tests whether the point is a root of σ and, on a root, applies Tr(ν ωΨ) for a fixed per-position constant ν. A position costs 11 Toffolis for the root test and 12 for the pairing, 23 in all, against 80 with a division at every point.

euclid_inv is the literal reverse of euclid: it replays each journal backward, last one first, through the setup. The cofactor words return to zero and the locator halves to σ.

Each evaluator block writes targets disjoint from its operands, so emitting the same block again undoes it. omega_restore runs the blocks in reverse order and recovers all 70 syndromes, on every input. unmonicize then restores the scale of σ that the backward rounds expect.

bm.reverse() replays the round journal from the newest round to the oldest. The forward rounds erased their temporaries by measurement at no Toffoli cost, and the reverse pass recomputes only those erased values. It therefore costs 86,176 Toffolis against 141,071 for the forward rounds.

The cleanup releases the held registers. The syndrome is unchanged.