Theorem 1.3 — quantum time for average-case -Subset-Sum at every ,
ProvedF3SubsetSum.theorem_1_3binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let . There are a quantum algorithm and constants (depending on ) such that for all and : given independent and uniform in , the algorithm outputs a nonempty with
with probability at least , and it runs in time
Concretely, one classical generator, on input , writes within that many steps a qutrit circuit over the gate set with at least and at most that many wires and at most that many gates; the circuit is run on , all wires are measured, and is read from the wires after the input. For with fixed this is polynomial time, while the best known classical algorithms need .
Differences from the source:
- reading: a quantum algorithm … runs in time (m/n)^{O_κ(⌈n²/m⌉)} → a Turing-machine generator (Turing.TM2ComputableAux Bool Bool) writes, within ⌊(m/n)^{C⌈n²/m⌉}⌋ steps, the code of a qutrit circuit over the fixed finite gate set G₃ with at most that many gates and wires, run on the input layout and measured on all wires; reason: the paper names no model of quantum computation; any fixed finite universal gate set gives the same theorem at this precision
- reading: for every m ≥ κ·n there is a quantum algorithm …, O_κ, Ω_κ → one generator and constants C, c > 0 chosen before n and m, for every n ≥ 1 and m ≥ κn; no constant factor outside the power; reason: the strongest reading; the proof's algorithm is uniform, and since m/n ≥ κ > 1 a constant factor is absorbed into C
- encoding: n arbitrary → n ≥ 1; reason: m/n is undefined at n = 0
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_SubsetSum import Definitions.Def_HMBinPacking_OutputsWithin import Definitions.Def_F3SubsetSum_MachineCodes import Definitions.Def_F3SubsetSum_QutritCircuit
Formal statement
namespace F3SubsetSum
/-- **Theorem 1.3** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Theorem 1.3,
p.4; restated p.22; proof pp.22–23): "Let κ > log(3) be any constant. For every m ≥ κ · n, there
is a quantum algorithm that solves Problem 1.1 with probability at least 1 − 2^{−Ω_κ(m)} and runs
in time (m/n)^{O_κ(⌈n²/m⌉)}."
For every `κ > log₂ 3` there are one circuit generator `M` and constants `C, c > 0` such that for
all `n ≥ 1` and `m ≥ κn`, on input `1ⁿ 0 1ᵐ` the generator writes, within
`T = (m/n)^{C⌈n²/m⌉}` steps, a qutrit circuit over `G₃` with at least `nm + m` and at most `T`
wires and at most `T` gates; run on `|h⟩ ⊗ |0…0⟩` and measured, it outputs a nonempty `S ⊆ [m]`
with `Σ_{i∈S} h_i = 0` with probability at least `1 − 2^{−cm}`, over uniform `h₁, …, h_m ∈ F₃ⁿ`
and the measurement.
**Formalization Note** The paper names no model of quantum computation. A quantum algorithm is
read as a deterministic multi-stack Turing machine with Boolean alphabets
(`Turing.TM2ComputableAux Bool Bool`, run as in the published `HMBinPacking.OutputsWithin`) that
writes the (injective) code of a circuit over the
fixed finite qutrit gate set `G₃`; the circuit acts on the input layout `inputBasis` and its
output is read from the `m` wires after the input (`successProb`). "Time" is the generator's
step count, which also bounds the number of gates and wires (stated explicitly). `log` is base 2.
`O_κ`, `Ω_κ` are constants depending on `κ` only, chosen with the generator before `n` and `m`.
`⌈·⌉` is the real ceiling and the power is a real power; there is no constant factor outside
the power because `m/n ≥ κ > 1`. `n ≥ 1` because `m/n` is undefined at `n = 0`. -/
theorem theorem_1_3 (κ : ℝ) (hκ : Real.logb 2 3 < κ) :
∃ (M : Turing.TM2ComputableAux Bool Bool) (circ : ℕ → ℕ → Circuit) (C c : ℝ), 0 < C ∧ 0 < c ∧
∀ n m : ℕ, 1 ≤ n → κ * n ≤ m →
HMBinPacking.OutputsWithin M (unaryD n ++ unary m) (encodeCircuit (circ n m))
⌊((m : ℝ) / n) ^ (C * (⌈(n : ℝ) ^ 2 / m⌉ : ℝ))⌋₊ ∧
n * m + m ≤ (circ n m).wires ∧
((circ n m).gates.length : ℝ) ≤ ((m : ℝ) / n) ^ (C * (⌈(n : ℝ) ^ 2 / m⌉ : ℝ)) ∧
((circ n m).wires : ℝ) ≤ ((m : ℝ) / n) ^ (C * (⌈(n : ℝ) ^ 2 / m⌉ : ℝ)) ∧
1 - (2 : ℝ) ^ (-(c * m)) ≤ successProb n m (circ n m) := by sorry
end F3SubsetSum
Source
Kothari, Metger, O'Donnell, Shutty, Wu, Exponential quantum speedup for F_3^n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE, arXiv:2609.40321v1, Theorem 1.3, p.4 (restated p.22; proof pp.22–23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.