docs/METHODS.md

Methods

Cost model for all benchmarks: score = Q² × T (Q = peak qubits, T = Toffoli count), computed by the official verifiers.

---

I. Inverse square root (submission/invsqrt.kmb)

Score 684,969.09 (89 qubits × 1,670 Toffolis), baseline 2,076,774.23 → −67.0%. Verifier: PASS, 0 value errors and 0 phase errors over all 65,536 inputs (verification/inv_verify_v2.json, salt u-ai-006).

The reference circuit runs a 4-step Newton iteration. This circuit replaces the last two Newton steps with a finite-difference tail-polynomial evaluated at a doubled Newton root:

1. Two exact small-scale iterations (n_p = 6, 12) seed a doubled root.
2. The tail T(y) ≈ (1/y)^(-1/2) correction is evaluated as a quantized polynomial (optimal shifts 0/4/12, scaled-e₂ recurrence, 4,234 nonzero coefficients), selected by exhaustive screening of shift/recurrence variants against the exact 24-bit rounding boundary — the shipped variant (WC3) is the only one of 27 shift triples that both fits the qubit budget and passes all inputs.
3. Coefficients load through a select network into a fixed-point accumulator; Newton correction uses one multiply by the doubled root.

Classical design validation (builders/model_direct.py) reproduces the exact fixed-point semantics in numpy and confirms all 2¹⁶ inputs before any quantum build. Regenerate with builders/build_invsqrt2.py (previous design retained in builders/build_invsqrt.py).

---

II. DQI — Reed–Solomon decoding (submission/dqi.kmb)

Score 17,673,729,048,937.30 (1,884 qubits × 4,179,942 Toffolis), baseline 24,439,463,583,672.93 → −27.7%. Verifier: PASS with 0 value / 0 phase errors at 102,400 shots (verification/dqi_verify_v6.json, salt dqi-v6-full), confirmed on a second salt at 10,240 shots (verification/dqi_verify_v6_salt2.json), on adversarial maximum-weight full-size inputs, and on small decoders (m=63, n=10) and (m=255, n=20) with exhaustive error patterns (builders/test_dqi.py).

Problem: prepare the DQI state for a [4095, 70] Reed–Solomon-like code — evaluate error-locator polynomials, run the extended Euclidean algorithm (EEA) over GF(2¹²), and apply Chien-search rotations, all reversibly.

The decoder structure follows the reference; the win comes from replacing the field arithmetic:

• Composite-tower GF(2¹²) inverse (79 Toffolis, was 315 built-in). GF(2¹²) = GF(2⁶)[y]/(y²+y+ν), ν = 32 of trace 1; the GF(2⁶) sub-inverse is itself a GF((2³)²) tower (builders/gf_inv12.py: init_inv6/del_inv6). Basis changes are applied in place with Clifford CNOT/SWAP networks (_apply_linear_inplace), so no separate transform registers are paid for.
• Generated bilinear multiplies (builders/gf_mul12.py): GF(2¹²) multiply in 54 products, GF(2⁶) in 18, GF(2³) in 6 (Chudnovsky evaluation form), each exhaustively verified over all input pairs (builders/test_gf_primitives.py). Controlled multiply: 66 Toffolis (was 75). Erasure is Toffoli-free (del_gf2_mul, measurement-style cleanup).
• Narrowed EEA degree counters (m.bit_length() bits) and quotient accumulation directly into the output register — peak qubits 1,914 → 1,884 with no correctness change.
• Chien σ=0 test: an 11-Toffoli AND tree erased measurement-style, replacing two 12-Toffoli flip_if_equal passes.

Explored and rejected (details in DESIGN_NOTES.md): reversible Berlekamp–Massey (a clean reversible core needs a ~840-qubit journal whose Q² penalty exceeds the Toffoli saving; journal-free recovery formulas are singular-prone), EEA support-based swap/shift pruning (packed simulation shows nearly all slots live), and reducing EEA iterations/window (provably near-tight: n=20 fails at 69/72 iterations; window m=n+3 fails outright).

---

III. DFTHC-SOS (submission/dfthcsos/)

Score 2,309,230,123.93, baseline 3,355,599,588.32 → −31.2%. Verifier: PASS (verification/dfthc_verify.json).

Double-factorized tensor hypercontraction with a sum-of-squares (SOS) factorization of the FeMoCo Hamiltonian:

1. The two-electron integrals are factorized by a symmetry-verified SOS decomposition; spectral certificates (eigenvalue bounds, residual norms) are checked classically before any circuit is built (dfthc_source/certificate.json, dfthc_source/numerical_invariants.json).
2. Each Givens rotation word is compiled to Clifford-only circuits from permutation/phase tables (angle_k_0.kmb … angle_k_6.kmb), with submission.npz holding the factorization data.
3. The merged C28_b10_30 candidate was selected over alternative factorizations by full verifier runs; per-circuit qubit/Toffoli costs are in dfthc_source/circuit_costs.json, rationale in dfthc_source/BEST.md.

---

Cross-cutting techniques

• Measurement-style cleanup: ancillas whose values are classically known functions of surviving registers are erased with Clifford-only networks instead of Toffoli uncomputation.
• Shared-product uncomputation: bilinear forms share monomial products between the forward map and its inverse, so erasure reuses computed terms.
• In-place linear algebra: invertible GF(2)-linear maps (basis changes, syndrome transforms) are compiled as CNOT/SWAP networks acting on existing registers rather than allocating image registers.