exact_quantum_query_complexity
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
- recursive_nae_contractive_normalized_recurrence_implies_upper_boundIf a positive fixed depth b and constants 0 ≤ θ < 1 and K ≥ 0 give a recurrence u(k+b) ≤ θu(k)+K for every k, where u(k) is the exact…
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 }