Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

A single fixed wire permutation preserves strong simulability

Open
QAlgorithms.Papers.Independent.Intakethird100.P77.fixedPermutation_strongSimulation

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

prove2quantum

Let UsU_sUs​ be an effectively uniform circuit of allowable nearest-neighbour matchgates and let PsP_sPs​ implement one effectively described permutation of its wires. Use that same permutation for every gate in the circuit. For arbitrary effectively described normalized product inputs and any existing single output wire, the conjugated circuit Vs=Ps†UsPsV_s=P_s^\dagger U_sP_sVs​=Ps†​Us​Ps​ admits deterministic strong simulation to mmm binary digits in polynomial time. A single global reordering restores the complete original circuit:

PsVsPs†=Us.P_sV_sP_s^\dagger=U_s.Ps​Vs​Ps†​=Us​.

This permits interactions on the edges of one permuted path, while preserving product inputs and one-wire measurements under relabeling. It does not allow a different permutation for each gate.

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 p.14 Example 1: one fixed permutation per circuit preserves strong
simulation and a single reordering restores the whole nearest-neighbour
circuit. A separate permutation for each gate is not permitted. -/
theorem fixedPermutation_strongSimulation (F : ParityFamily)
    (I : ProductInputs F.width) (hF : F.Effective) (hI : EffectiveNumbers I.data)
    (hmatch : ∀ s g, g ∈ F.gates s → g.Allowable)
    (hpath : ∀ s, RangeBound 1 (F.gates s))
    (p : (s : Str) → Equiv.Perm (Fin (F.width s)))
    (hp : EffectivePermutations F.width p) :
    StrongSimulation F.width (fun s k b =>
      singleWireProbability
        (star (permutationOperator (p s)) * (parityCircuit (F.gates s)).unitary *
          permutationOperator (p s)) (prodState (I.factor s)) k b) ∧
    (∀ s, permutationOperator (p s) *
        (star (permutationOperator (p s)) * (parityCircuit (F.gates s)).unitary *
          permutationOperator (p s)) * star (permutationOperator (p s)) =
      (parityCircuit (F.gates s)).unitary) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P77

end
Source
Matchgates and classical simulation of quantum circuits, arXiv:0804.4050v2, PDF p. 14, Section 6 Example 1: fixed wire permutations preserve a path of simulatable interactions
Read-back

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

Let FFF assign to every finite Boolean string sss a width w(s)∈Nw(s)\in\mathbb Nw(s)∈N and a finite ordered list of gates, each specified by two unitary complex 2×22\times22×2 matrices Ag,BgA_g,B_gAg​,Bg​, indexed by Boolean values, and an injection vg:{0,1}↪{0,…,w(s)−1}v_g:\{0,1\}\hookrightarrow\{0,\ldots,w(s)-1\}vg​:{0,1}↪{0,…,w(s)−1}. Assume every gate satisfies det⁡Ag=det⁡Bg\det A_g=\det B_gdetAg​=detBg​ and ∣vg(0)−vg(1)∣≤1|v_g(0)-v_g(1)|\le1∣vg​(0)−vg​(1)∣≤1. On its two designated wires, its matrix entry from yyy to xxx is zero when the two strings have different Boolean parity, is (Ag)x0,y0(A_g)_{x_0,y_0}(Ag​)x0​,y0​​ when both have even parity, and is (Bg)x0,y0(B_g)_{x_0,y_0}(Bg​)x0​,y0​​ when both have odd parity; on all other wires it leaves the bits unchanged. Let UsU_sUs​ be the product of these embedded matrices in reverse list order, with the empty product equal to the identity. For each sss and wire iii, let ϕs,i∈C2\phi_{s,i}\in\mathbb C^2ϕs,i​∈C2 have Euclidean norm one, and put ψs(x)=∏iϕs,i(xi)\psi_s(x)=\prod_i\phi_{s,i}(x_i)ψs​(x)=∏i​ϕs,i​(xi​). The effectiveness assumptions are as follows. Write u(j)=true ju(j)=\mathrm{true}^{\,j}u(j)=truej and T([a1,…,ak])=∥j(u(∣aj∣) false aj)T([a_1,\ldots,a_k])=\big\Vert_j(u(|a_j|)\,\mathrm{false}\,a_j)T([a1​,…,ak​])=​j​(u(∣aj​∣)falseaj​). The function encoding FFF as T([u(w(s)),u(number of gates)]+ ⁣ ⁣+[T([u(vg(0)),u(vg(1))]):g in list order])T([u(w(s)),u(\text{number of gates})]\mathbin{+\!\!+}[T([u(v_g(0)),u(v_g(1))]):g\text{ in list order}])T([u(w(s)),u(number of gates)]++[T([u(vg​(0)),u(vg​(1))]):g in list order]) is polynomial-time computable. The lists of matrix entries, taking AgA_gAg​ then BgB_gBg​ for each gate and the order (0,0),(0,1),(1,0),(1,1)(0,0),(0,1),(1,0),(1,1)(0,0),(0,1),(1,0),(1,1) within each matrix, and the lists [ϕs,0(0),ϕs,0(1),…][\phi_{s,0}(0),\phi_{s,0}(1),\ldots][ϕs,0​(0),ϕs,0​(1),…], each admit polynomial-time numerical approximation: for every valid list index jjj, precision m∈Nm\in\mathbb Nm∈N, and Boolean bbb, a polynomial-time Boolean-string function queried on T([s,u(j),u(m),[b]])T([s,u(j),u(m),[b]])T([s,u(j),u(m),[b]]) returns a signed dyadic approximation to the real part when b=falseb=\mathrm{false}b=false, or the imaginary part when b=trueb=\mathrm{true}b=true, with absolute error at most 2−m2^{-m}2−m. Here a returned string represents its binary tail, with true as one, divided by 2m2^m2m, negated exactly when its first bit is true; missing bits default to false. All polynomial-time requirements use TM2 machines with identity input and output encodings. Finally, let psp_sps​ be a permutation of the wires such that s↦T([u(ps(0)),…,u(ps(w(s)−1))])s\mapsto T([u(p_s(0)),\ldots,u(p_s(w(s)-1))])s↦T([u(ps​(0)),…,u(ps​(w(s)−1))]) is polynomial-time computable, and define Ps(x,y)=1P_s(x,y)=1Ps​(x,y)=1 if x=y∘psx=y\circ p_sx=y∘ps​, and zero otherwise. Then, writing Vs=Ps†UsPsV_s=P_s^\dagger U_sP_sVs​=Ps†​Us​Ps​, there exists a polynomial-time Boolean-string function which, on T([s,u(m),u(k),[b]])T([s,u(m),u(k),[b]])T([s,u(m),u(k),[b]]), returns a dyadic number within 2−m2^{-m}2−m of

∑x∈{0,1}w(s)xk=b∣(Vsψs)(x)∣2\sum_{\substack{x\in\{0,1\}^{w(s)}\\x_k=b}}|(V_s\psi_s)(x)|^2x∈{0,1}w(s)xk​=b​∑​∣(Vs​ψs​)(x)∣2

for every sss, m∈Nm\in\mathbb Nm∈N, wire k<w(s)k<w(s)k<w(s), and Boolean bbb, using the same signed-dyadic convention; moreover, for every sss, PsVsPs†=UsP_sV_sP_s^\dagger=U_sPs​Vs​Ps†​=Us​. Width zero is included: its product input has its sole amplitude equal to one, and there are no wire-probability queries.

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