Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Effective uniform IQP circuits and the relativized IQP class

Definition
IQPForrelation832_SingleQuery_Supplement_Uniform

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexityforrelationiqp-circuitsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

A circuit description is a finite list of diagonal gates from one fixed effective finite gate library, placed on explicit ordered distinct wires, and plain phase-oracle occurrences. It acts on ∣0m⟩|0^m\rangle∣0m⟩ between two outer Hadamard layers. Oracle labels select local black boxes in the product distinguishing task. In the total-oracle interpretation all labels must be empty, and a call applies (−1)O(address)(-1)^{O(\text{address})}(−1)O(address) on its actual selected quantum address wires. No oracle answers enter the classical generator, gate library or accepting decider.

L∈IQPO⟺∃ one uniform family Cx:x∈L⇒Pr⁡[Cx accepts]≥23,x∉L⇒Pr⁡[Cx accepts]≤13.L\in\mathrm{IQP}^O\quad\Longleftrightarrow\quad \exists\text{ one uniform family }C_x:\quad x\in L\Rightarrow\Pr[C_x\text{ accepts}]\ge\tfrac23,\qquad x\notin L\Rightarrow\Pr[C_x\text{ accepts}]\le\tfrac13.L∈IQPO⟺∃ one uniform family Cx​:x∈L⇒Pr[Cx​ accepts]≥32​,x∈/L⇒Pr[Cx​ accepts]≤31​.

Uniformity means that one deterministic finite-machine polynomial-time function generates structurally parsed circuit descriptions, and one polynomial-time machine decides the accepting set from the classical input length and the measured outcome. A uniform polynomial bounds width, outer Hadamards, gate count and encoded query placements. Each fixed library entry has an oracle-free polynomial-time rational approximation machine at every binary precision; gate constants cannot carry uncomputable advice. Every library member is explicitly required to be unitary and diagonal. The same accepting set is used for all classical inputs of the same length. The total Boolean oracle and the full union of relativized polynomial-hierarchy levels are reused from the published OracleSep model, without substituting its exact quantum class for IQP.

For the mmm-fold problem, query labels are exactly the distinct (n,i)(n,i)(n,i) labels, one per pair, and every query register has n+1n+1n+1 wires. The entire list is fixed before quantum outcomes; there are no intermediate measurements or adaptive instructions. Product-law acceptance averages the Born probability of this single circuit. The rational amplification threshold has the integer comparison (192n+1)m≤384n⋅accepted count(192n+1)m\le384n\cdot\text{accepted count}(192n+1)m≤384n⋅accepted count.

Definition code
import Definitions.Def_IQPForrelation832_SingleQuery_Supplement_RazTal
import Definitions.Def_IQPForrelation832_SingleQuery_Programs
import Definitions.Def_ExactForrelationSeparation_OracleSep_Model

set_option autoImplicit false

namespace IQPForrelation832.SingleQuery.Supplement

open QAlgorithms QAlgorithms.Complexity

/-- Only diagonal gates and plain phase queries appear in the middle. The label selects
an input-independent black box; in the total-oracle interpretation it is a fixed label.
There is no measurement, random branch, or answer-dependent address instruction. -/
inductive UniformInstruction where
  | gate (index : ℕ) (wires : List ℕ)
  | query (label : Str) (wires : List ℕ)
  deriving DecidableEq

structure UniformCode where
  wires : ℕ
  body : List UniformInstruction
  deriving DecidableEq

def readNaturals : ℕ → Str → Option (List ℕ × Str)
  | 0, s => some ([], s)
  | k+1, s => do
    let (v, rest) ← readNat s
    let (vs, tail) ← readNaturals k rest
    some (v :: vs, tail)

def readUniformInstruction (s : Str) : Option (UniformInstruction × Str) := do
  let (tag, rest) ← readNat s
  let (j, rest) ← readNat rest
  let (k, rest) ← readNat rest
  let (r, rest) ← readNaturals k rest
  match tag with
  | 0 => some (.gate j r, rest)
  | 1 => if j ≤ rest.length then some (.query (rest.take j) r, rest.drop j) else none
  | _ => none

def readUniformInstructions : ℕ → Str → Option (List UniformInstruction × Str)
  | 0, s => some ([], s)
  | k+1, s => do
    let (g, rest) ← readUniformInstruction s
    let (gs, tail) ← readUniformInstructions k rest
    some (g :: gs, tail)

def decodeUniform (s : Str) : Option UniformCode := do
  let (m, rest) ← readNat s
  let (k, rest) ← readNat rest
  let (gs, tail) ← readUniformInstructions k rest
  if tail = [] then some ⟨m,gs⟩ else none

/-- A register is a list of DISTINCT physical wires; different registers may overlap. -/
noncomputable def placement (m : ℕ) (r : List ℕ) : Option (Fin r.length ↪ Fin m) := by
  classical
  exact if h : (∀ i : Fin r.length, r[i.val] < m) ∧
      Function.Injective (fun i : Fin r.length => r[i.val]) then
    some ⟨fun i => ⟨r[i.val],h.1 i⟩, fun i j e => h.2 (congrArg Fin.val e)⟩ else none

noncomputable def uniformStepValid (G : List Gate) (m : ℕ) : UniformInstruction → Prop
  | .gate j r => ∃ g, G[j]? = some g ∧ g.arity = r.length ∧ (placement m r).isSome
  | .query _ r => (placement m r).isSome

noncomputable def uniformValid (G : List Gate) (c : UniformCode) : Prop :=
  (∀ g ∈ G, DiagonalUnitary g) ∧ ∀ s ∈ c.body, uniformStepValid G c.wires s

/-- Actual matrix of a gate placed on its ordered wires, using the shared embedOp. -/
noncomputable def uniformStepMat (G : List Gate) (m : ℕ) (O : Str → Str → Bool) :
    UniformInstruction → Matrix (Qubits m) (Qubits m) ℂ
  | .gate j r => match G[j]?, placement m r with
    | some g, some w => if h : g.arity = r.length then embedOp (h ▸ g.mat) w else 1
    | _, _ => 1
  | .query label r => match placement m r with
    | some w => embedOp (Matrix.diagonal (fun a : Qubits r.length =>
        (if O label (List.ofFn a) then (-1 : ℂ) else 1))) w
    | none => 1

noncomputable def uniformRun (G : List Gate) (c : UniformCode) (O : Str → Str → Bool) :
    EuclideanSpace ℂ (Qubits c.wires) :=
  act (hadamardN c.wires * (c.body.map (uniformStepMat G c.wires O)).reverse.prod *
    hadamardN c.wires) (zeroKet c.wires)

noncomputable def uniformBorn (G : List Gate) (c : UniformCode) (a : Str → Str)
    (length : ℕ) (O : Str → Str → Bool) : ℝ := by
  classical
  exact probEvent (uniformRun G c O) (fun z =>
    a (encNat length ++ encNat c.wires ++ List.ofFn z) = [true])

/-- Includes label lengths and physical address lists in the resource count. -/
def uniformSize (c : UniformCode) : ℕ :=
  c.wires + 2*c.wires + c.body.length +
    (c.body.map (fun s => match s with
      | .gate j r => j+1 + r.sum + r.length
      | .query label r => label.length + r.sum + r.length)).sum

/-- Binary integers, with a unary bit-count and one sign bit. This is a concrete
rational approximation format, not a semantic decoder chosen with the oracle. -/
def readSignedBinary (s : Str) : Option (ℤ × Str) := do
  let (negative, rest) ← match s with | [] => none | b :: tail => some (b,tail)
  let (k, rest) ← readNat rest
  if k ≤ rest.length then
    let magnitude := (rest.take k).foldl (fun v b => 2*v + if b then 1 else 0) 0
    some ((if negative then -(magnitude : ℤ) else (magnitude : ℤ)), rest.drop k)
  else none

noncomputable def decodeComplexApprox (k : ℕ) (s : Str) : Option ℂ := do
  let (a, rest) ← readSignedBinary s
  let (b, rest) ← readSignedBinary rest
  if rest = [] then some (((a : ℝ) / 2^k : ℂ) + ((b : ℝ) / 2^k : ℂ) * Complex.I) else none

/-- The finite gate library has one effective, oracle-free, polynomial-time approximation
machine for every entry, to any requested binary precision. Arbitrary real constants
carrying uncomputable advice are excluded by this standard uniformity convention. -/
def EffectiveLibrary (G : List Gate) : Prop :=
  ∃ approx : Str → Str, PolyTimeComputable approx ∧
    ∀ (j : ℕ) (g : Gate), G[j]? = some g → ∀ (u v : Qubits g.arity) (k : ℕ),
      ∃ z : ℂ, decodeComplexApprox k
        (approx (encNat j ++ List.ofFn u ++ List.ofFn v ++ encNat k)) = some z ∧
        ‖z - g.mat u v‖ ≤ (2 : ℝ)^(-(k : ℤ))

/-- A single deterministic generator and a single polynomial-time outcome test, neither
receiving the oracle or its truth tables. The gate library is fixed and finite. -/
def UniformFamily (G : List Gate) (code : Str → UniformCode) (a : Str → Str) : Prop :=
  EffectiveLibrary G ∧ PolyTimeComputable a ∧ ∃ gen : Str → Str, PolyTimeComputable gen ∧
    ∃ C k : ℕ, ∀ x, decodeUniform (gen x) = some (code x) ∧
      uniformValid G (code x) ∧ uniformSize (code x) ≤ C*(x.length+1)^k

abbrev TotalOracle := BQPNotInIP.OracleSep.Oracle
abbrev PHO := ExactForrelationSeparation.OracleSep.PHO

/-- Definition 4: a single IQP circuit, generated from the classical input; one accepting
set for each input length. A fixed effective finite library is the standard circuit-description convention.
Every total-oracle call has an EMPTY label: it applies the actual O to the selected
quantum address register, without a free classical-prefix oracle facility. -/
def IQPO (O : TotalOracle) : Set (Language Bool) :=
  {L | ∃ (G : List Gate) (code : Str → UniformCode) (a : Str → Str),
    UniformFamily G code a ∧
    (∀ x, ∀ s ∈ (code x).body, match s with | .gate _ _ => True | .query label _ => label = []) ∧
    ∀ x,
      (x ∈ L → 2/3 ≤ uniformBorn G (code x) a x.length (fun label addr => O (label ++ addr))) ∧
      (x ∉ L → uniformBorn G (code x) a x.length (fun label addr => O (label ++ addr)) ≤ 1/3)}

def queryDescriptions (c : UniformCode) : List (Str × List ℕ) :=
  c.body.filterMap (fun s => match s with | .gate _ _ => none | .query label r => some (label,r))

/-- Exactly one local joint-oracle occurrence per independent pair, all placed before
any measurement and with the entire query list fixed by the classical generator. -/
def UsesIndependentBlocks (n m : ℕ) (c : UniformCode) : Prop :=
  List.Perm ((queryDescriptions c).map Prod.fst) (List.ofFn (fun i : Fin m => blockPrefix n i.val)) ∧
  ∀ q ∈ queryDescriptions c, q.2.length = n+1

/-- Labelled local joint oracles, queried on n+1 selected wires. Invalid labels/lengths
have a fixed value, but UsesIndependentBlocks and validity exclude them on every call. -/
noncomputable def pairOracles {n m : ℕ} (z : Fin m → SignPair n) (label addr : Str) : Bool :=
  if h : ∃ i : Fin m, label = blockPrefix n i.val then
    let i := Classical.choose h
    let u : Qubits n := fun j => addr[j.val+1]?.getD false
    !(if addr.headD false then (z i).2 else (z i).1) (cubeEquiv n u)
  else false

noncomputable def distinguishingBorn {n m : ℕ} (G : List Gate) (c : UniformCode)
    (a : Str → Str) (z : Fin m → SignPair n) : ℝ :=
  uniformBorn G c a n (pairOracles z)

/-- Integer version of the proof's amplification threshold; no floating-point test. -/
def thresholdAccepts (n m accepted : ℕ) : Prop :=
  (192*n+1)*m ≤ 384*n*accepted

end IQPForrelation832.SingleQuery.Supplement
Source
Quentin Buzet, André Chailloux, IQP circuits for 2-Forrelation, STOC 2027 submission #832 (October 2026), p. 13, Definitions 3–4; pp. 21–24, Definitions 7–8 and Proposition 10. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/832.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me