The public data of an oracle instance from
DefinitionTwoFoldOPI_Supplement_DLamInputcoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
With , , , , , and , an instance of consists of the public description of , the partition of and the membership circuits, together with oracle access to .
This input type holds the public data: , the explicit field, the generator and the class of each symbol of . The size parameter is .
Formalization Note The membership circuits are produced by the fixed public program of admissibility and are not stored; the partition is stored because need not be computable from real .
Definition code
import Mathlib
import Definitions.Def_TwoFoldOPI_elemBits
namespace TwoFoldOPI
namespace Supplement
open QAlgorithms
/-- **The public part of an oracle-represented instance from `D_λ`.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §11, Definition 11.1, p.57: "Let q = 2^{2⌊log λ⌋}, M = q − 1, s = 2^{⌊log λ⌋} + 1,
n = 2^{⌊log λ⌋}, k = ⌊ρM⌋ for a constant rate parameter ρ ∈ (0, 1), and let γ be an arbitrary
generator of F_q^*. We define C_λ = RS_{F_q,γ,k} ⊆ F_q^M"; Definition 11.2, p.57: "The
corresponding oracle-represented code-intersection instance consists of the public descriptions of
C_λ, the partition, and the truncated-load membership circuits from Definition 10.2, together with
quantum oracle access to the H_i's."
The public data: the security parameter `λ`, the explicit field `F` and the generator `γ` (which
with `λ` and the fixed rate describe `C_λ`), and the partition of `[n] = {0, …, n−1}`,
`n = 2^{⌊log₂ λ⌋}`, as the class map `part : [n] → [R]`. `encode` writes `λ` in self-delimiting
binary, the field (`fieldEncode`), `γ` (`elemBits`) and the classes `part 0, …, part (n−1)` in
self-delimiting binary; `scale = λ`.
**Formalization Note.** The membership circuits are not stored: for admissible load data they are
produced from `m` by one fixed public polynomial-time program (Definition 10.9), which a uniform
algorithm for the fixed load data can run itself. The partition is stored because `⌊α_r n⌋` need
not be computable from real `α_r`. The oracles `H_i` are not part of the input. The module holds
the input type with its encoding and size. -/
structure DLamInput (R : ℕ) where
/-- The security parameter. -/
lam : ℕ
/-- The field. -/
F : AvgCaseTI.FieldPres
/-- The generator of the multiplicative group. -/
γ : F.F
/-- The class of each symbol of `[n]`. -/
part : Fin (2 ^ Nat.log 2 lam) → Fin R
/-- The bit encoding of the public data. -/
noncomputable def DLamInput.encode {R : ℕ} (x : DLamInput R) : List Bool :=
LocalHamiltonian.encBin x.lam ++ fieldEncode x.F ++ List.ofFn (elemBits x.F x.γ) ++
(List.ofFn fun a => LocalHamiltonian.encBin (x.part a).val).flatten
/-- The size parameter `λ`. -/
def DLamInput.scale {R : ℕ} (x : DLamInput R) : ℕ := x.lam
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), §11, Definitions 11.1–11.2, p. 57