A single fixed wire permutation preserves strong simulability
OpenQAlgorithms.Papers.Independent.Intakethird100.P77.fixedPermutation_strongSimulationLet be an effectively uniform circuit of allowable nearest-neighbour matchgates and let 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 admits deterministic strong simulation to binary digits in polynomial time. A single global reordering restores the complete original circuit:
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.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P77
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let assign to every finite Boolean string a width and a finite ordered list of gates, each specified by two unitary complex matrices , indexed by Boolean values, and an injection . Assume every gate satisfies and . On its two designated wires, its matrix entry from to is zero when the two strings have different Boolean parity, is when both have even parity, and is when both have odd parity; on all other wires it leaves the bits unchanged. Let be the product of these embedded matrices in reverse list order, with the empty product equal to the identity. For each and wire , let have Euclidean norm one, and put . The effectiveness assumptions are as follows. Write and . The function encoding as is polynomial-time computable. The lists of matrix entries, taking then for each gate and the order within each matrix, and the lists , each admit polynomial-time numerical approximation: for every valid list index , precision , and Boolean , a polynomial-time Boolean-string function queried on returns a signed dyadic approximation to the real part when , or the imaginary part when , with absolute error at most . Here a returned string represents its binary tail, with true as one, divided by , 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 be a permutation of the wires such that is polynomial-time computable, and define if , and zero otherwise. Then, writing , there exists a polynomial-time Boolean-string function which, on , returns a dyadic number within of
for every , , wire , and Boolean , using the same signed-dyadic convention; moreover, for every , . Width zero is included: its product input has its sole amplitude equal to one, and there are no wire-probability queries.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.