Restrictions and normalized oracle-bit Fourier coefficients
DefinitionIQPForrelation832_SingleQuery_Supplement_OracleFourierA restriction assigns a fixed sign or a free marker to each of the original addresses. Write for its free set and for a free assignment; denotes its extension. For every , define
Total mass sums over all , including the empty set; level mass sums over . Multilinear degree at most asserts both reconstruction by these characters and vanishing for . The restriction vectors are computed by
The binomial bound is the exact sum, over with , of . These definitions allow empty free sets, empty accepting sets, zero queries and zero address dimension. Boolean true encodes and false encodes ; the free-coordinate subtype contains exactly . This normalized average on oracle bits is distinct from the published orthonormal address-space Fourier transform.
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