Theorem 7.4, algorithmic part — uniform poly-time quantum algorithm with failure
ProvedTwoFoldOPI.theorem_7_4_algorithmThis is the algorithmic part of Theorem 7.4 (clauses 1, 2 and 4 of TwoFoldOPI.theorem_7_4), i.e. Theorem 7.4 without its final coding-theoretic estimate.
Let be a finite field, given explicitly as . An instance consists of an matrix over together with a tag saying whether is a generator matrix ( is its row space) or a parity-check matrix (), forbidden values defining , and a precision . Write and
where is the Schur square, the zero set and the shortened code.
There is one quantum algorithm, given by a uniform classical constructor that reads the bit encoding of the instance and outputs, in polynomial time and space, an oracle-free adaptive program over the gate set with output bits ( bits per field symbol), and one polynomial , such that for every finite field, every , every , every and every , the program built for the instance with satisfies, with its probability of outputting a word of :
- it uses at most qubits, classical bits and operations;
- if , then ;
- if , then .
Together with the estimate (TwoFoldOPI.schurFailureSum_le_dist_bound) and , this gives the full Theorem 7.4, including its bound .
Formalization Note. The model is exactly the one of TwoFoldOPI.theorem_7_4: the algorithm is a QAlgorithms.OPI.UniformResourceFamily over TwoFoldOPI.Input (public bit encoding Input.encode, size parameter Input.scale ); charged resources are membershipResources; success is membershipOutputLaw of the event solves x (the decoded output word lies in ; failure leaves count as failure); is Nat.card. The polynomial is chosen after the family and before every input, and all clauses are about the same program.
import Mathlib import Definitions.Def_CodingTheory import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms import Definitions.Def_QAlgorithms_Defs_OPIUniformity import Definitions.Def_TwoFoldOPI_elemBits import Definitions.Def_TwoFoldOPI_Input import Definitions.Def_TwoFoldOPI_codeOf import Definitions.Def_TwoFoldOPI_schurFailureSum import Definitions.Def_TwoFoldOPI_solves
namespace TwoFoldOPI
open QAlgorithms QAlgorithms.OPI
theorem theorem_7_4_algorithm :
∃ A : UniformResourceFamily Input Input.encode Input.scale,
(∀ x, (A.construct x).oracles = 0 ∧
(A.construct x).outputBits = x.m * bitsPerSymbol x.F) ∧
∃ P : Polynomial ℕ,
∀ (F : AvgCaseTI.FieldPres) (m r : ℕ) (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
(β : Fin m → F.F) (ε : ℝ), 0 < ε → ε < 1 / 4 →
let x : Input := ⟨F, m, r, gen, H, β, ⌈Real.logb 2 (1 / ε)⌉₊⟩
let D := CodingTheory.dualCode F.F (Fin m) (codeOf gen H)
let succ := membershipOutputLaw (A.construct x).program (fun _ => 1) (solves x)
membershipResources (A.construct x).program (fun _ => 1) ≤ P.eval x.scale ∧
(D ≠ ⊥ → 1 - succ ≤ 2 * (Nat.card D : ℝ) * schurFailureSum D + ε) ∧
(D = ⊥ → succ = 1) := by sorry
end TwoFoldOPI