Hermitian DQI decoder

The locator coefficients σ lie in the null space of the symmetric 48 × 48 matrix A_kk′ = S(ψ_kψ_k′), whose entries are sums of one or two syndromes. The circuit never writes A down. It factors a product as Au = Φ^T diag(η) Φu: Φ evaluates u at 123 fixed curve points, the weights η_p are linear in the syndromes, and Φ^T maps the products back.

The loop visits the 123 points p. In each pass it gathers a parity of syndrome bits and a parity of vector bits onto two scratch qubits, with masks read from the tables. Fifteen passes AND the two parities and scatter the result into the 288 output bits. Together they form one 15-Toffoli multiplication in 𝔽₆₄, so one product costs 123 · 15 = 1,845 Toffolis. Φ, η and Φ^T appear only as gather and scatter masks, which cost CNOTs.

To clear a product, emit_matvec_mbu_loop measures the output in the X basis and replays the same gathers with outcome-conditioned CZ gates. This costs no Toffolis.

A round first forms U = Aw for the head w and three scalars g_k = w^TA^kw. In characteristic 2, g₀ is the square of the sum of the symbols of w, so emit_sigma_tap forms it with CNOTs; g₂ comes the same way from U, and _qscan1 forms g₁. Zero tests of these scalars detect the end of the walk, g₀ = g₁ = g₂ = 0. _freeze_fwd then writes the round into the freeze record.

The ordinary update acts under t_nrm: the walk has not ended and g₀ ≠ 0. The round inverts g₀, adds a multiple of w into X, and forms the projection coefficient. It then adds multiples of Aw and w into the mate, which held the previous vector. Symmetry of A makes this three-term recurrence enough. A journal bit records whether the round advanced, and the round ends by exchanging head and mate under it.

Over 𝔽₆₄ a nonzero vector can have g₀ = 0. On such an input no update gate acts, and the walk stays frozen until a scheduled repair round. Rounds in SERVICE (every third, and two extension rounds) can repair at depth two, and those in V3CAP (every sixth, and the same extension rounds) at depth three. Together they make 17 of the 52 rounds. They compute A²w, select depth two when g₁ ≠ 0 and depth three when only g₂ ≠ 0, and advance the walk past the whole block. A deeper block fails.

The round clears its scratch in reverse order, mostly by measurement. A repair round measures V2 and records the outcomes; the reverse walk repairs their phase.

Part of the phase is linear in the syndromes; Z gates on syndrome bits apply it. The remaining constant vanishes at 128 of the 512 points, which leaves 384 points to scan: 24 stripes of 16.

The fill computes the 48 local coefficients of ω that the stripe needs, three per point, by evaluation–interpolation. A fixed fraction h = n/q, with a numerator linear in the syndromes, stands in for the syndrome series. All products σh lie in a fixed 206-dimensional space, so the fill evaluates both factors at 206 points and multiplies them pointwise, 206 · 15 = 3,090 Toffolis per stripe. A fixed linear fold maps the products into the stripe's bank.

The sweep visits each point. CNOTs gather the local coefficients of σ, which are linear in X. Three zero flags test the first three of them: fr marks a zero of σ, and z1 and z2 mark that the next two also vanish, which signals a repeated zero of multiplicity up to three. The flags select which coefficients enter the quotient. The tower core forms the phase bit Tr(μ̃ω/σ′) with an inverse in 𝔽₈, at 33 ANDs per point, and applies it only where σ vanishes. Measurements then clear the per-point values.

The erase measures the bank and corrects the phase with CZ gates, at no Toffoli cost. The 24 stripes cost 102,192 Toffolis; neither an evaluator nor a decoded error word is ever live.