Theorem 3.1 — quantum reduction from -Subset-Sum to average-case Binary-Error LWE
ProvedF3SubsetSum.theorem_3_1binary-error-lwecommutative-algebraf3-subset-sump2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-systemsquantum-algorithms
Let be a deterministic decoder for Binary-Error LWE over , computed by a machine that runs in time on every -input, and let
be its average-case error. Then there is a quantum algorithm (depending only on the decoder's machine) that, for every , runs in time and solves Problem 1.1 with probability at least
Concretely, a classical generator writes, on input and within steps, a qutrit circuit over with at most that many gates and wires; the circuit is run on and measured. This is the reduction of Chen, Liu and Zhandry through Regev's method, which turns any good decoder into a Subset-Sum solver.
Differences from the source:
- reading: a quantum algorithm … runs in time poly(m, n, T) → a Turing-machine generator (Turing.TM2ComputableAux Bool Bool), given 1ⁿ 0 1ᵐ 0 1ᵀ, writes the code of a G₃ qutrit circuit within ⌊C(n+m+T+1)^C⌋ steps, with at most C(n+m+T+1)^C gates and wires, run on the input layout and measured on all wires; reason: the paper names no model of quantum computation; the + 1 keeps the bound positive at n = m = T = 0
- reading: a decoder Dec that runs in time T → a Turing machine M (Turing.TM2ComputableAux Bool Bool) computing Dec on every (n, m)-input within T steps; the generator depends on M; reason: the paper names no machine model
- encoding: error at most η → η replaced by the exact average-case error avgError Dec n m; reason: the bound for the exact error implies it for every η ≥ the error; same theorem
Preamble
import Mathlib import Definitions.Def_F3SubsetSum_BinaryErrorLWE import Definitions.Def_HMBinPacking_OutputsWithin import Definitions.Def_F3SubsetSum_MachineCodes import Definitions.Def_F3SubsetSum_QutritCircuit
Formal statement
namespace F3SubsetSum
/-- **Theorem 3.1** (Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, Theorem 3.1,
p.13; proof pp.13–16): "Suppose we have a deterministic decoder Dec : F_3^{n×m} × F_3^m → F_3^n
that runs in time T and solves average-case Binary-Error LWE over F_3 with error η, i.e.,
Pr_{A∼F_3^{n×m}, s∼F_3^n, e∼{0,1}^m}[Dec(A, A⊤s + e) ≠ s] ≤ η. Then there is a quantum algorithm
that solves average-case F_3^n-Subset-Sum (Problem 1.1) with probability at least
1 − 2η − 3^n · (2/3)^m and runs in time poly(m, n, T)."
For every machine `M` computing a decoder `Dec`, there are a circuit generator `G` and a
constant `C > 0` such that for all `n`, `m`, `T`: if `M` halts within `T` steps on every
`(n, m)`-input, then on input `1ⁿ 0 1ᵐ 0 1ᵀ` the generator writes, within `C(n + m + T + 1)^C`
steps, a qutrit circuit over `G₃` with at most that many gates and wires, which solves
Problem 1.1 with probability at least `1 − 2η − 3ⁿ(2/3)^m`, where `η = avgError Dec n m` is the
decoder's exact average-case error.
**Formalization Note** The quantum algorithm is a classical multi-stack Turing machine with Boolean
alphabets (`Turing.TM2ComputableAux Bool Bool`) that writes the code of a
qutrit circuit over the fixed gate set `G₃`, which is then run on `|h⟩ ⊗ |0…0⟩` and measured in
the computational basis (`successProb`). The generator depends on the decoder machine, which it
compiles. `poly(m, n, T)` is read as `C(n + m + T + 1)^C`; the `+ 1` keeps the bound positive at
`n = m = T = 0`. `η` is taken to be the error itself (the hypothesis `error ≤ η` then gives the
printed bound for every `η`). -/
theorem theorem_3_1 (M : Turing.TM2ComputableAux Bool Bool) (Dec : DecoderFn 3) :
∃ (G : Turing.TM2ComputableAux Bool Bool) (circ : ℕ → ℕ → ℕ → Circuit) (C : ℝ), 0 < C ∧
∀ n m T : ℕ, ComputesWithin M Dec n m T →
HMBinPacking.OutputsWithin G (unaryD n ++ unaryD m ++ unary T) (encodeCircuit (circ n m T))
⌊C * ((n + m + T + 1 : ℕ) : ℝ) ^ C⌋₊ ∧
n * m + m ≤ (circ n m T).wires ∧
((circ n m T).gates.length : ℝ) ≤ C * ((n + m + T + 1 : ℕ) : ℝ) ^ C ∧
((circ n m T).wires : ℝ) ≤ C * ((n + m + T + 1 : ℕ) : ℝ) ^ C ∧
1 - 2 * avgError Dec n m - (3 : ℝ) ^ n * (2 / 3 : ℝ) ^ m ≤
successProb n m (circ n m T) := 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 3.1, p.13 (proof pp.13–16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.