AFTD Auto-Formalizing Theoretical Domains

exact_quantum_query_complexity

def

Exact quantum query complexity Q_E(f) of a Boolean function f on N bits, defined as the minimum number of phase queries needed to evaluate f exactly.

Statement

noncomputable def exact_quantum_query_complexity {N : ℕ} (f : (Fin N → Bool) → Bool) : ℕ
Defined in
arXiv:2611.16412 Section 2.1
Verified
13 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a natural number N and a Boolean function f : (Fin N → Bool) → Bool, exact_quantum_query_complexity f is defined as the infimum (in ℕ) of the set of natural numbers q such that there exist: 1. a finite type B with decidable equality (representing the basis states of the quantum system); 2. a query register assignment reg : B → Option (Fin N); 3. an initial state vector ψ0 : B → ℂ satisfying the normalization condition ∑ b : B, Complex.normSq (ψ0 b) = 1; 4. an initial unitary matrix U0 : Matrix B B ℂ belonging to Matrix.unitaryGroup B ℂ; 5. a sequence of q unitary matrices steps : Fin q → Matrix B B ℂ, each belonging to Matrix.unitaryGroup B ℂ; and 6. an output predicate out : B → Bool, such that for every input x : Fin N → Bool: the sum over all b : B with out b = true of Complex.normSq (v b) equals 1 if f x = true and 0 if f x = false, where v : B → ℂ is the state obtained by starting with Matrix.mulVec U0 ψ0 and, for each matrix U in List.ofFn steps from left to right, first applying the phase oracle for x (multiplying the amplitude at b by -1 if reg b = some i and x i = true, and by 1 otherwise) and then applying Matrix.mulVec U.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Exact quantum query complexity Q_E(f) of a Boolean function f in the standard phase query model. -/
noncomputable def exact_quantum_query_complexity {N : ℕ} (f : (Fin N → Bool) → Bool) : ℕ := sInf { q : ℕ | ∃ (B : Type) (_ : Fintype B) (_ : DecidableEq B) (reg : B → Option (Fin N)) (ψ0 : B → ℂ) (_ : ∑ b, Complex.normSq (ψ0 b) = 1) (U0 : Matrix B B ℂ) (_ : U0 ∈ Matrix.unitaryGroup B ℂ) (steps : Fin q → Matrix B B ℂ) (_ : ∀ t, steps t ∈ Matrix.unitaryGroup B ℂ) (out : B → Bool), ∀ x : Fin N → Bool, (∑ b, if out b then Complex.normSq (((List.ofFn steps).foldl (fun v U => Matrix.mulVec U (fun b => (match reg b with | none => (1 : ℂ) | some i => if x i then -1 else 1) * v b)) (Matrix.mulVec U0 ψ0)) b) else 0) = if f x then 1 else 0 }
See it in the graphDiscuss this resultChallenge it