Uniformity bridge — a RAM-serializable program family is a uniform resource family
OpenTwoFoldOPI.uniformFamily_of_RAMSerializableLet assign to every instance of Theorem 7.4 (field presentation, matrix, tag, forbidden values, precision) a concrete quantum program (PackedMembershipProgram). Suppose the family is RAM-serializable: some word-RAM algorithm computes, in time polynomial in its input length, a function with
for every instance , where is the public instance encoding, and is the canonical program serialization.
Then there is a UniformResourceFamily over the instances, with encoding and size parameter , whose programs are exactly . That is, there are one public bit program (no coins, no oracle queries) and one polynomial such that, on the bare encoding (cells beyond it read as , with no end marker), the bit program halts successfully with output exactly , using at most steps and visiting at most cells.
This bridge lets the uniformity requirement of Theorem 7.4 be met by programming the classical constructor on the word RAM, where high-level languages with verified compilers are available, instead of on the low-level bit machine.
Formalization Note. The hypothesis is TwoFoldOPI.RAMSerializable construct. The conclusion fixes the family's construct field to be the given function; the constructor program, its correctness and its polynomial bound are existentially quantified. Because the bit machine sees no end marker, the bridge has to find the end of itself.
Retired. Superseded by TwoFoldOPI.uniformFamily_of_RAMSerializableF: uniformity is now reduced through RAM-serializability on raw prefixes (TwoFoldOPI.RAMSerializableF), where the constructor itself recognises when a zero-padded prefix is long enough. This removes the separate parser lemmas.
import Mathlib import Definitions.Def_QAlgorithms_Defs_OPIUniformity import Definitions.Def_TwoFoldOPI_Input import Definitions.Def_TwoFoldOPI_RAMSerializable
namespace TwoFoldOPI
open QAlgorithms.OPI
theorem uniformFamily_of_RAMSerializable (construct : Input → PackedMembershipProgram)
(h : RAMSerializable construct) :
∃ A : UniformResourceFamily Input Input.encode Input.scale, A.construct = construct := by
sorry
end TwoFoldOPI