Uniform circuit for index-two dual certificate flags
ProvedInfoLossLAR.WorstCase.RegevSketch.dual_parity_pool_circuit_pass_flagsdiscrete-gaussianlar-regev-bridgelattices
Let be a uniform quantum polynomial-time sampler with classical output strings. For a nonsingular integer matrix of positive dimension and a positive rational threshold , let double column of . Put , , and . Let be the probability that the output of on the request starts with a coefficient pool that passes both tests. The odd-coordinate count at is at least . For a decoded pool , the covariance test is
There is a uniform quantum polynomial-time decision family such that, on each valid encoded input , there is a probability mass function on Boolean flag vectors of length satisfying
This flag law connects the exact circuit semantics for arbitrary sampler outputs to the finite probability estimate for the decision procedure.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false set_option maxHeartbeats 200000 open QAlgorithms.Complexity open scoped BigOperators Classical
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem dual_parity_pool_circuit_pass_flags :
∀ G : MFamily, IsMQPT G → ∃ A : Family, IsQPT A ∧
∀ n : ℕ, 1 ≤ n → ∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 → ∀ δ : ℚ, 0 < δ →
let m := (n+1)^3
let H (i : Fin n) : Matrix (Fin n) (Fin n) ℤ := fun a b => B a b * (if b = i then 2 else 1)
let D (i : Fin n) := (H i).adjugate.transpose
let r (i : Fin n) : ℚ := (Int.natAbs (H i).det : ℚ) / (100*δ)
let E (i : Fin n) (p : Fin m → Fin n → ℤ) : Prop :=
m ≤ 4 * (Finset.univ.filter (fun j => Odd (p j i))).card ∧
∀ x : Fin n → ℤ,
64 * δ^2 * (∑ j, ((∑ a, x a * ((D i).mulVec (p j)) a : ℤ) : ℚ)^2) ≤
(m : ℚ) * ((H i).det : ℚ)^2 * (∑ a, (x a : ℚ)^2)
∃ weights : (Fin n → Bool) → ℝ,
(∀ flags, 0 ≤ weights flags) ∧
(∑ flags, weights flags) = 1 ∧
(∀ i : Fin n,
(∑ flags, if flags i then weights flags else 0) =
outputProb G (dgsInput (D i) (r i) m (16*(n+1))) (decodedPoolEvent (E i))) ∧
acceptProb A (encGapInstance B δ) =
∑ flags, if ∃ i : Fin n, flags i = false then weights flags else 0 := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Circuit-realization sublemma for Prove2Me theorem InfoLossLAR.WorstCase.RegevSketch.dual_parity_pool_circuit_union (UUID 4fa11364-4184-412e-83a8-fa8693ba4b3e). Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, May 2, 2009, p. 30, Lemma 3.20 (https://cims.nyu.edu/~regev/papers/qcrypto.pdf), for the sampler-and-verifier structure. The exact flag interface is specific to the index-two certificate. De Wolf, Quantum Computing: Lecture Notes, §2.1.2 (https://homepages.cwi.nl/~rdewolf/qcnotes.pdf), for reversible classical evaluation in the quantum circuit model.