Effective uniform IQP circuits and the relativized IQP class
DefinitionIQPForrelation832_SingleQuery_Supplement_UniformA 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 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 on its actual selected quantum address wires. No oracle answers enter the classical generator, gate library or accepting decider.
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 -fold problem, query labels are exactly the distinct labels, one per pair, and every query register has 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 .
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