Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Exact encoded range-two matchgate simulation

Open
QAlgorithms.Papers.Independent.Intakethird100.P77.rangeTwo_encodedUniversality

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Present a uniform circuit family using nearest-neighbour controlled-ZZZ gates and arbitrary one-qubit unitary gates, with one final computational-basis measurement on the first wire. Assume effective finite numerical descriptions of its one-qubit gates. There is an absolute constant C>0C>0C>0 and an effectively uniform target family on four physical wires per logical wire, fixed before the logical input, such that

∣Gs∣≤C∣Cs∣,range⁡(Gs)≤2,pb(Gs,E4ψ,1)=pb(Cs,ψ,1).|G_s|\le C|C_s|,\qquad \operatorname{range}(G_s)\le2,\qquad p_b(G_s,E_4\psi,1)=p_b(C_s,\psi,1).∣Gs​∣≤C∣Cs​∣,range(Gs​)≤2,pb​(Gs​,E4​ψ,1)=pb​(Cs​,ψ,1).

Here sss is the classical family parameter, ∣Cs∣|C_s|∣Cs​∣ is its actual gate count, ψ\psiψ is any normalized logical input, bbb is either outcome, and E4E_4E4​ linearly extends ∣0⟩↦∣0000⟩|0\rangle\mapsto|0000\rangle∣0⟩↦∣0000⟩, ∣1⟩↦∣1001⟩|1\rangle\mapsto|1001\rangle∣1⟩↦∣1001⟩. Every target gate is an allowable equal-determinant matchgate. The constant overhead is relative to the stated source presentation; this is universality with encoding.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P77
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P77

open QAlgorithms

open QAlgorithms.Complexity (Str)

open QAlgorithms.Papers.Independent.Advance50.P19 (Major CARSystem)

open QAlgorithms.Papers.Independent.Information100.P32 (Op)

open scoped BigOperators Matrix ComplexConjugate

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.4--6 Theorem 2: uniform encoded range-two simulation with a universal
constant gate overhead in the source nearest-neighbour CZ/one-qubit normal
form. Printed: any uniform circuit family with constant size increase. Changed:
measure size in the normal form fixed by the source proof on p.4, since
arbitrary-connectivity routing need not have constant cost. The target family is fixed before all logical inputs. Only the first
output distribution is asserted; no unencoded physical universality is used. -/
theorem rangeTwo_encodedUniversality :
    ∃ C : ℕ, 0 < C ∧ ∀ F : SourceFamily, F.Effective →
      (∀ s, 0 < F.width s) →
      ∃ G : (s : Str) → List (ParityApp (4 * F.width s)),
        (ParityFamily.mk (fun s => 4 * F.width s) G).Effective ∧
        (∀ s g, g ∈ G s → g.Allowable) ∧
        (∀ s, RangeBound 2 (G s) ∧ (G s).length ≤ C * (F.gates s).length) ∧
        ∀ s (k : Fin (F.width s)), k.val = 0 →
          ∀ (q : Fin (4 * F.width s)), q.val = 0 →
            ∀ psi : EuclideanSpace ℂ (Qubits (F.width s)), IsState psi →
              ∀ b, singleWireProbability (parityCircuit (G s)).unitary
                  (encodeState encodeFourBits psi) q b =
                singleWireProbability (sourceCircuit (F.gates s)).unitary psi k b := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P77

end
Source
Matchgates and classical simulation of quantum circuits, arXiv:0804.4050v2, PDF p. 4, Theorem 2: encoded universality at range two
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

There exists a positive natural number CCC such that the following holds for every source family FFF. Such a family assigns to every finite Boolean string sss a width nsn_sns​ and a finite ordered list of gates, each either an arbitrary one-qubit unitary on a specified wire or a controlled-ZZZ gate on two specified wires whose indices satisfy i+1=ji+1=ji+1=j. Assume ns>0n_s>0ns​>0 for every sss, and assume the family is effective in this precise sense: write u(r)u(r)u(r) for rrr consecutive true bits and define τ([v1,…,vℓ])\tau([v_1,\ldots,v_\ell])τ([v1​,…,vℓ​]) by concatenating u(∣vj∣)u(|v_j|)u(∣vj​∣), one false bit, and vjv_jvj​ for each jjj; the string τ([u(ns),u(Ls)]+ ⁣ ⁣+gate descriptions)\tau([u(n_s),u(L_s)]\mathbin{+\!\!+}\text{gate descriptions})τ([u(ns​),u(Ls​)]++gate descriptions), where LsL_sLs​ is the gate-list length and a gate description is τ([[false],u(i)])\tau([[{\rm false}],u(i)])τ([[false],u(i)]) for a one-qubit gate or τ([[true],u(i),u(j)])\tau([[{\rm true}],u(i),u(j)])τ([[true],u(i),u(j)]) for controlled-ZZZ, is computable from sss in polynomial time; moreover, the list of numerical data, obtained by listing each one-qubit matrix’s entries in the order (00,01,10,11)(00,01,10,11)(00,01,10,11) and listing no entries for controlled-ZZZ, has a polynomial-time approximation procedure. Specifically, on τ([s,u(j),u(r),[b]])\tau([s,u(j),u(r),[b]])τ([s,u(j),u(r),[b]]), for every valid data index jjj, precision r∈Nr\in\mathbb Nr∈N, and Boolean bbb, that procedure outputs a string interpreted as a signed binary integer divided by 2r2^r2r, with error at most 2−r2^{-r}2−r from the real part of entry jjj when bbb is false and its imaginary part when bbb is true; the first output bit is the sign, true meaning negative, and the remaining bits encode the magnitude in binary, with missing bits defaulting to false. Then there exists a family GsG_sGs​ of ordered gate lists on 4ns4n_s4ns​ wires. Each gate specifies an injection of two local wires into these wires and two Boolean-indexed 2×22\times22×2 unitary matrices A,BA,BA,B; its local matrix has entry 000 between strings of different parity, entry Ax0,y0A_{x_0,y_0}Ax0​,y0​​ when both strings have even parity, and entry Bx0,y0B_{x_0,y_0}Bx0​,y0​​ when both have odd parity. Every such gate in GsG_sGs​ satisfies det⁡A=det⁡B\det A=\det BdetA=detB; its two wire indices differ by at most 222; and ∣Gs∣≤CLs|G_s|\le C L_s∣Gs​∣≤CLs​. This new family is effective: its exact code is τ([u(4ns),u(∣Gs∣)]+ ⁣ ⁣+[τ([u(ig),u(jg)])]g)\tau([u(4n_s),u(|G_s|)]\mathbin{+\!\!+}[\tau([u(i_g),u(j_g)])]_g)τ([u(4ns​),u(∣Gs​∣)]++[τ([u(ig​),u(jg​)])]g​), and its numerical data list concatenates the four entries of AgA_gAg​ followed by the four entries of BgB_gBg​ for every gate, with polynomial-time approximation in the same sense just specified. For every sss, every source wire kkk with index 000, every target wire qqq with index 000, every unit vector ψ\psiψ on length-nsn_sns​ bit strings, and every Boolean bbb, the conclusion is

∑z:zq=b∣(WsE4ψ)z∣2=∑x:xk=b∣(Vsψ)x∣2.\sum_{z:z_q=b}|(W_s E_4\psi)_z|^2 = \sum_{x:x_k=b}|(V_s\psi)_x|^2.z:zq​=b∑​∣(Ws​E4​ψ)z​∣2=x:xk​=b∑​∣(Vs​ψ)x​∣2.

Here VsV_sVs​ and WsW_sWs​ apply the source and target gates, respectively, in their listed order, each gate acting identically on untouched wires, and

E4ψ=∑xψx ∣x0 0 0 x0 x1 0 0 x1⋯ ⟩.E_4\psi=\sum_x\psi_x\,|x_0\,0\,0\,x_0\,x_1\,0\,0\,x_1\cdots\rangle.E4​ψ=x∑​ψx​∣x0​00x0​x1​00x1​⋯⟩.

The assertion covers every finite string sss, including the empty string, and empty source gate lists; the length bound then forces the corresponding target gate list to be empty. The probability equality concerns the specified index-zero wires and all normalized input vectors.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me