Lemma 3.1 — finite-precision reference direction
ProvedQuantumLTF.Membership.lemma_3_1linear-threshold-functionsmembership-queriesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-learning
For there is a probability distribution on vectors whose coordinates are signed fixed-point numbers of bits, with universal, such that for every ,
The distribution is fixed before . A reference direction of this kind makes the height function well conditioned and implementable in reversible fixed-point arithmetic.
Differences from the source:
- reading: a randomized classical preprocessing procedure → its output law, a PMF on strings of n·ℓ bits; reason: the printed lemma claims only the output distribution; its cost is counted in the goal
- encoding: O(log n) bits per coordinate → one format (ℓ, f) with f ≤ ℓ for all coordinates, coordinates fp_{ℓ,f} of sub-registers; reason: a common format costs only padding; bits include the fractional bits
- reading: O(·) in a statement → one universal constant C placed before n and the other parameters; reason: the O(·) of the paper is uniform in all the stated parameters
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QuantumLTF_Membership_addrOf
Formal statement
namespace QuantumLTF.Membership
open QAlgorithms
/-- **Lemma 3.1 (Finite-precision reference direction).** Krivcenko, Nguyen, de Wolf, *Fast Quantum Algorithms for Learning Linear Threshold Functions*,
arXiv:2609.40331, Lemma 3.1, p. 20 (PDF p. 21). For
`n ≥ 2` there is a randomized procedure outputting `p ∈ Rⁿ`, with `O(log n)` bits per coordinate, such
that for every fixed unit `w`, `Pr[1/10 ≤ |⟨w, p⟩| ≤ 3] ≥ 4/5`.
**Formalization Note.** The procedure is its output law `μ`, a `PMF` on the coordinate strings, fixed
before `w`. A string denotes the vector `addrOf n ℓ f` of fixed-point coordinates of its `n`
sub-registers; the `ℓ` here includes the `f` fractional bits. `∃ C` precedes `n`: the constant is
universal. The running cost of the procedure is not part of the printed lemma; it is charged in the
goal's gate count. -/
theorem lemma_3_1 :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n →
∃ ℓ f : ℕ, f ≤ ℓ ∧ (ℓ : ℝ) ≤ C * Real.log n ∧ ∃ μ : PMF (Qubits (n * ℓ)),
∀ w : EuclideanSpace ℝ (Fin n), ‖w‖ = 1 →
(μ.toOuterMeasure {z | 1 / 10 ≤ |inner ℝ w (addrOf n ℓ f z)| ∧
|inner ℝ w (addrOf n ℓ f z)| ≤ 3}).toReal ≥ 4 / 5 := by sorry
end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Lemma 3.1, p. 20 (PDF p. 21)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.