Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact compilation of locally simulated quantum query algorithms

Proved
QuantumBipartiteTesting.Bipartiteness.local_oracle_algorithm_compilation

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

quantum-query-complexity

Let III and LLL be finite sets of source and logical query addresses. Fix a source address i0i_0i0​, three source addresses a(l,0),a(l,1),a(l,2)a(l,0),a(l,1),a(l,2)a(l,0),a(l,1),a(l,2) for each logical address lll, and a function ggg mapping their binary answers to a logical binary answer. All of this data is independent of the input function fff.

For every qqq-query logical quantum algorithm with finite workspace and a computational-basis Boolean output event, there is a source quantum algorithm, also with finite workspace, whose query count satisfies

qS≤6q,q_S\leq 6q,qS​≤6q,

and whose acceptance probability on every source function fff equals that of the logical algorithm with oracle

l⟼g(l,f(a(l,0)),f(a(l,1)),f(a(l,2))).l\longmapsto g(l,f(a(l,0)),f(a(l,1)),f(a(l,2))).l⟼g(l,f(a(l,0)),f(a(l,1)),f(a(l,2))).

Both answer registers are full bit-string spaces, including unused encodings. The result applies the constant-query oracle reduction to arbitrary unitary interlayers and arbitrary initial unit vectors.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
open QuantumBipartiteTesting.Bipartiteness
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.local_oracle_algorithm_compilation {I L : Type} [Fintype I] [Fintype L] [DecidableEq I] [DecidableEq L]
    (kS kT w q : ℕ) (i0 : I) (a : L→Fin 3→I)
    (g : L→(Fin 3→Bits kS)→Bits kT) (A : Algorithm L kT w q)
    (out : ((L×Bits kT)×Fin w)→Bool) :
    ∃ wS qS : ℕ, ∃ A' : Algorithm I kS wS qS,
    ∃ out' : ((I×Bits kS)×Fin wS)→Bool, qS ≤ 6*q ∧ ∀ f : I→Bits kS,
      A'.outputProb (QAlgorithms.xorOracle f) out' true =
        A.outputProb (QAlgorithms.xorOracle (fun l => g l (fun j => f (a l j)))) out true := by sorry
Source
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §2.1.2 p. 8 and Lemma 3.16 proof p. 21. Generic circuit-composition interface for an explicit clean six-query implementation of the stated O(1) simulation.

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