Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Restrictions and normalized oracle-bit Fourier coefficients

Definition
IQPForrelation832_SingleQuery_Supplement_OracleFourier

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

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

A restriction ρ\rhoρ assigns a fixed sign or a free marker to each of the original N=2nN=2^nN=2n addresses. Write Γ\GammaΓ for its free set and x∈{−1,1}Γx\in\{-1,1\}^{\Gamma}x∈{−1,1}Γ for a free assignment; xρx\rhoxρ denotes its extension. For every S⊆ΓS\subseteq\GammaS⊆Γ, define

χS(x)=∏a∈Sxa,p∣ρ^(S)=2−∣Γ∣∑xp(xρ)χS(x).\chi_S(x)=\prod_{a\in S}x_a,\qquad \widehat{p|\rho}(S)=2^{-|\Gamma|}\sum_x p(x\rho)\chi_S(x).χS​(x)=a∈S∏​xa​,p∣ρ​(S)=2−∣Γ∣x∑​p(xρ)χS​(x).

Total mass sums ∣p∣ρ^(S)∣|\widehat{p|\rho}(S)|∣p∣ρ​(S)∣ over all SSS, including the empty set; level mass L1,ℓL_{1,\ell}L1,ℓ​ sums over ∣S∣=ℓ|S|=\ell∣S∣=ℓ. Multilinear degree at most kkk asserts both reconstruction by these characters and vanishing for ∣S∣>k|S|>k∣S∣>k. The restriction vectors are computed by

ϵA(ρ)=∏a∈A∖Γρa,vCρ=∑A∩Γ=CϵA(ρ)vA.\epsilon_A(\rho)=\prod_{a\in A\setminus\Gamma}\rho_a,\qquad v_C^\rho=\sum_{A\cap\Gamma=C}\epsilon_A(\rho)v_A.ϵA​(ρ)=a∈A∖Γ∏​ρa​,vCρ​=A∩Γ=C∑​ϵA​(ρ)vA​.

The binomial bound is the exact sum, over 0≤a,b≤d0\le a,b\le d0≤a,b≤d with a+b=ℓa+b=\ella+b=ℓ, of min⁡{(da)(Nb),(db)(Na)}\sqrt{\min\{\binom da\binom Nb,\binom db\binom Na\}}min{(ad​)(bN​),(bd​)(aN​)}​. These definitions allow empty free sets, empty accepting sets, zero queries and zero address dimension. Boolean true encodes +1+1+1 and false encodes −1-1−1; the free-coordinate subtype contains exactly Γ\GammaΓ. This normalized average on oracle bits is distinct from the published orthonormal address-space Fourier transform.

Definition code
import Definitions.Def_IQPForrelation832_SingleQuery_Supplement_PhaseCircuits

set_option autoImplicit false

namespace IQPForrelation832.SingleQuery.Supplement

open QAlgorithms

/-- true is +1, false is -1. This finite type avoids adding sign hypotheses to each sum. -/
def signValue (b : Bool) : ℝ := if b then 1 else -1

abbrev Restriction (n : ℕ) := Cube n → Option Bool

noncomputable def freeSet {n : ℕ} (ρ : Restriction n) : Finset (Cube n) := by
  classical
  exact Finset.univ.filter (fun a => ρ a = none)

abbrev FreeAssignment {n : ℕ} (ρ : Restriction n) := {a : Cube n // a ∈ freeSet ρ} → Bool

noncomputable def extendRestriction {n : ℕ} (ρ : Restriction n) (x : FreeAssignment ρ) :
    Cube n → ℝ := fun a =>
  if h : a ∈ freeSet ρ then signValue (x ⟨a,h⟩) else signValue ((ρ a).getD false)

noncomputable def oracleCharacter {n : ℕ} (ρ : Restriction n)
    (S : Finset {a : Cube n // a ∈ freeSet ρ}) (x : FreeAssignment ρ) : ℝ :=
  ∏ a ∈ S, signValue (x a)

/-- Normalized AVERAGE on remaining oracle signs, not the address-space orthonormal transform. -/
noncomputable def oracleHat {n : ℕ} (p : (Cube n → ℝ) → ℝ) (ρ : Restriction n)
    (S : Finset {a : Cube n // a ∈ freeSet ρ}) : ℝ :=
  ((2 : ℝ) ^ (freeSet ρ).card)⁻¹ *
    ∑ x : FreeAssignment ρ, p (extendRestriction ρ x) * oracleCharacter ρ S x

noncomputable def totalMass {n : ℕ} (p : (Cube n → ℝ) → ℝ) (ρ : Restriction n) : ℝ :=
  ∑ S : Finset {a : Cube n // a ∈ freeSet ρ}, |oracleHat p ρ S|

noncomputable def levelMass {n : ℕ} (p : (Cube n → ℝ) → ℝ) (ρ : Restriction n) (ell : ℕ) : ℝ :=
  ∑ S : Finset {a : Cube n // a ∈ freeSet ρ}, if S.card = ell then |oracleHat p ρ S| else 0

/-- The actual multilinear character expansion, AND vanishing above the asserted degree. -/
def MultilinearDegreeLE {n : ℕ} (p : (Cube n → ℝ) → ℝ) (ρ : Restriction n) (k : ℕ) : Prop :=
  (∀ x : FreeAssignment ρ, p (extendRestriction ρ x) =
    ∑ S : Finset {a : Cube n // a ∈ freeSet ρ}, oracleHat p ρ S * oracleCharacter ρ S x) ∧
  ∀ S : Finset {a : Cube n // a ∈ freeSet ρ}, k < S.card → oracleHat p ρ S = 0

noncomputable def fixedSign {n : ℕ} (ρ : Restriction n) (A : Finset (Cube n)) : ℝ :=
  ∏ a ∈ A \ freeSet ρ, signValue ((ρ a).getD false)

noncomputable def restrictedVector {n m : ℕ} (c : PhaseMiddle n m) (ρ : Restriction n)
    (C : Finset {a : Cube n // a ∈ freeSet ρ}) : EuclideanSpace ℂ (Qubits m) := by
  classical
  exact ∑ A : Finset (Cube n), if A ∩ freeSet ρ = C.image Subtype.val then
    (fixedSign ρ A : ℂ) • parityVector c A else 0

noncomputable def binomialBound (d N ell : ℕ) : ℝ :=
  ∑ a ∈ Finset.range (d+1), ∑ b ∈ Finset.range (d+1), if a+b = ell then
    Real.sqrt (min ((Nat.choose d a : ℝ) * Nat.choose N b)
      ((Nat.choose d b : ℝ) * Nat.choose N a)) else 0

end IQPForrelation832.SingleQuery.Supplement
Source
Quentin Buzet, André Chailloux, IQP circuits for 2-Forrelation, STOC 2027 submission #832 (October 2026), p. 12, Definitions 1–2; pp. 25–30, restriction notation, Lemma 5, Theorems 5–6. 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