Admissible load data with mean load and tilt
DefinitionTwoFoldOPI_Supplement_Admissiblecoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Nonempty sets and weights with are admissible with mean load and tilt if:
- given , membership circuits for are constructible in time and decide every in time, uniformly in ;
- under the load has mean : ;
- the additive subgroup of generated by is .
The witness of condition 2 is the tilt used by every tilted-Poisson quantity.
Formalization Note Condition 1 is one public bit program (no coins, no oracle) and one polynomial : on input in binary it halts within steps with a well-formed Boolean circuit of size at most on input bits deciding .
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Basic
import Definitions.Def_QAlgorithms_Defs_Classical
import Definitions.Def_QAlgorithms_ClassicalBinaryEncoding
import Definitions.Def_QAlgorithms_Defs_LearningSeparation
import Definitions.Def_QAlgorithms_Defs_OPIBitPrograms
import Definitions.Def_TwoFoldOPI_Supplement_tiltPoiss
namespace TwoFoldOPI
namespace Supplement
open QAlgorithms QAlgorithms.OPI
open Classical in
/-- **Admissible load data (with mean load `η` and tilt `ν`).**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §10.2, Definition 10.9, p.56: "Let η > 0 be a constant parameter; it will be the limit of
m/n. Fix nonempty sets B_1, …, B_R ⊆ Z_{≥0} and constants α_1, …, α_R ∈ R_{>0} summing to 1. We
say that these are admissible if all of the following hold: • Given m, membership circuits for
B_r ∩ {0, …, m} are constructible in poly(m) time and decide every input 0 ≤ k ≤ m in poly(m)
time, uniformly in r. • There exists ν > 0 such that the second coordinate K of
(I, K) ∼ TiltPoiss_{ν,{B_r},{α_r}} has mean η: E_{(I,K)←TiltPoiss_{ν,{B_r},{α_r}}}[K] = η.
• The additive subgroup generated by ⋃_{r∈[R]} (B_r − B_r) is all of Z. Whenever these data are
admissible, we fix one such witnessing value of ν".
`Admissible B α η ν` says that `(B_r)_{r<R}`, `(α_r)_{r<R}` are admissible with mean load `η`, and
that `ν` is a witness of the second condition:
1. every `B_r ⊆ ℕ` is nonempty, every `α_r > 0`, `Σ_r α_r = 1`, `η > 0`, `ν > 0`;
2. (membership circuits) one deterministic bit program `prog` (no coins, no oracle) and one
polynomial `P`: for every `r` and `m`, `prog` on input `(r, m)` (binary) halts within `P(m)`
steps and outputs the encoding of a well-formed Boolean circuit `C` of size at most `P(m)`
on `⌈log₂(m+1)⌉` input bits such that `C(k) = 1 ⇔ k ∈ B_r` for every `0 ≤ k ≤ m`
(`k` written in binary, most significant bit first);
3. (mean) `Σ_r α_r Σ_k k · p^{(r)}_k = η` with `p^{(r)} = TiltPoiss_{ν,B_r}`;
4. (aperiodicity) the additive subgroup of `ℤ` generated by `⋃_r (B_r − B_r)` is `ℤ`.
**Formalization Note.** "Constructible in poly(m) time … uniformly in r" is a public bit program
(`QAlgorithms.OPI.BitOracleProgram`, `IsPublicPreprocessor`: no coin, no oracle query) writing the
circuit as `QAlgorithms.Learning.encBoolCircuit`; "decide every input in poly(m) time" is the size
bound on the circuit. `R` is the number of classes (`Fin R`). The witness `ν` is a parameter, as
in the paper ("we fix one such witnessing value of ν"). -/
structure Admissible {R : ℕ} (B : Fin R → Set ℕ) (α : Fin R → ℝ) (η ν : ℝ) : Prop where
nonempty : ∀ r, (B r).Nonempty
alpha_pos : ∀ r, 0 < α r
alpha_sum : ∑ r, α r = 1
eta_pos : 0 < η
nu_pos : 0 < ν
membership : ∃ (P : Polynomial ℕ) (prog : BitOracleProgram), IsPublicPreprocessor prog ∧
∀ (r : Fin R) (m : ℕ), ∃ fuel : ℕ, fuel ≤ P.eval m ∧
∃ C : BoolCircuit (Nat.clog 2 (m + 1)) 1, C.WellFormed ∧ C.size ≤ P.eval m ∧
(bitProgramExecution prog
(LocalHamiltonian.encBin r.val ++ LocalHamiltonian.encBin m)
(fun _ => false) (fun _ => false) fuel).status = some true ∧
(bitProgramExecution prog
(LocalHamiltonian.encBin r.val ++ LocalHamiltonian.encBin m)
(fun _ => false) (fun _ => false) fuel).output = Learning.encBoolCircuit C ∧
∀ k : ℕ, k ≤ m → (C.eval (natToBits (Nat.clog 2 (m + 1)) k) 0 = true ↔ k ∈ B r)
mean : ∑ r, α r * ∑' k : ℕ, (k : ℝ) * tiltPoiss ν (B r) k = η
aperiodic :
AddSubgroup.closure (⋃ r, {d : ℤ | ∃ a ∈ B r, ∃ b ∈ B r, d = (a : ℤ) - (b : ℤ)}) = ⊤
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §10.2, Definition 10.9, p. 56