Buckets:
| # 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. | |
Xet Storage Details
- Size:
- 5.41 kB
- Xet hash:
- 6ce67a5dd6e8056b7f8e1e3dfb9a30128b75a8396f4ad0a341c9cc7e7075f2e5
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.