Reading the first bits of an output string
DefinitionTwoFoldOPI_Supplement_readBitscoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
The string of length whose -th bit is the -th output bit, padded with beyond the output length. Outputs are read as words of field symbols this way.
Formalization Note Statements fix the number of output bits to the expected length, so the padding never applies.
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **Reading the first `L` bits of an output string.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.2, "Computational conventions", p.26 (outputs as words over an explicitly represented
field); the published `TwoFoldOPI.solves` reads outputs the same way.
`readBits bits` is the string of length `L` whose bit `i` is `bits i` for `i < out` and `0`
otherwise.
**Formalization Note.** Statements fix the program's number of output bits to the expected length,
so the padding never applies; the function only makes the types agree. -/
def readBits {out L : ℕ} (bits : Fin out → Bool) : Fin L → Bool :=
fun i => if h : i.val < out then bits ⟨i.val, h⟩ else false
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), §5.2, Computational conventions, p. 26