Theorem 6 — exact asymmetric binomial Fourier-level bound
OpenIQPForrelation832.SingleQuery.Supplement.theorem_6Let be the actual acceptance probability of any -query IQP circuit using a single -wire phase oracle and any accepting subset of the computational basis. Set , the original oracle-table length. For every restriction , the function is multilinear of degree at most . For each natural level ,
and for . The minimum stays inside each square root; no geometric-mean or asymptotic relaxation is made. remains the original table length after every restriction. There is no assumption that , or that are positive. Arbitrary diagonal-unitary middle gates, ancillas, overlapping queries, repeated addresses and all accepting subsets are included. This companion theorem gives the exact level-wise query bound, using the restricted decomposition of Lemma 5.
Differences from the source:
- generalization: polynomial-size IQP middle blocks → arbitrary finite diagonal-unitary middle gate lists; reason: the Section 5 arguments do not use the number of non-oracle gates; every source circuit is included
- encoding: sign assignments on the free set Gamma and its subsets → Boolean signs on the exact free-coordinate subtype; reason: true represents +1 and false represents -1; all assignments and restrictions correspond bijectively, including the empty free set
import Definitions.Def_IQPForrelation832_SingleQuery_Supplement_OracleFourier set_option autoImplicit false
namespace IQPForrelation832.SingleQuery.Supplement
open QAlgorithms QAlgorithms.Complexity
theorem theorem_6 {n m d : ℕ} (c : PhaseMiddle n m)
(hc : PhaseIQP c) (hd : OracleCircuit.queryCount c 0 = d)
(F : Finset (Qubits m)) (ρ : Restriction n) :
MultilinearDegreeLE (phaseBorn c F) ρ (2*d) ∧
(∀ ell : ℕ, ell ≤ 2*d → levelMass (phaseBorn c F) ρ ell ≤ binomialBound d (2^n) ell) ∧
(∀ ell : ℕ, 2*d < ell → levelMass (phaseBorn c F) ρ ell = 0) := by sorry
end IQPForrelation832.SingleQuery.Supplement