Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Acceptance polynomial of the actual finite quantum query circuit

Proved
QuantumBipartiteTesting.Bipartiteness.actual_acceptance_polynomial

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-property-testingpolynomial-methodquantum-information

Let III be a finite address set and SSS a finite non-null response alphabet. Fix an injective binary response encoding with zero-encoded null, a qqq-query quantum circuit with an input-independent unit start vector and input-independent complex unitaries, and a fixed Boolean computational-basis output event. The query adds the encoded response by XOR and acts as the identity on the finite workspace.

There is a real polynomial PPP in the response indicators, of total degree at most 2q2q2q, such that for every oracle O:I→S∪{⊥}O:I\to S\cup\{\bot\}O:I→S∪{⊥},

P((1O(a)=z)(a,z)∈I×S)=Pr⁡[AO accepts].P\bigl((\mathbf1_{O(a)=z})_{(a,z)\in I\times S}\bigr) =\Pr[A^O\text{ accepts}].P((1O(a)=z​)(a,z)∈I×S​)=Pr[AO accepts].

The polynomial depends only on the circuit, encoding, and output event. All oracles, binary answer-register states, and finite workspaces remain included. This is the polynomial-existence step of Lemma 2.9; canonical response-table interpolation subsequently preserves its degree and values.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Query
open QuantumBipartiteTesting.Bipartiteness
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.actual_acceptance_polynomial
    {I S : Type} [Fintype I] [Fintype S] [DecidableEq I] [DecidableEq S]
    {k w q : ℕ} (E : Encoding S k) (A : Algorithm I k w q)
    (out : (I × Bits k) × Fin w → Bool) :
    ∃ P : MvPolynomial (I × S) ℝ, P.totalDegree ≤ 2*q ∧
      ∀ O : I → Option S, MvPolynomial.eval (Indicators O) P = Accept E A out O := by sorry
Source
Kayal, Sen, Szabó, Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model, held October 2026 manuscript, §2.4, Lemma 2.9, printed/PDF p. 10 (non-null response indicators and null elimination). https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf The amplitude induction and sum-of-squares proof are Beals, Buhrman, Cleve, Mosca, de Wolf, Quantum Lower Bounds by Polynomials, Lemmas 4.1–4.2, printed p. 9 / PDF p. 9, https://homepages.cwi.nl/~rdewolf/publ/qc/polynomials.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