Exact encoded range-two matchgate simulation
OpenQAlgorithms.Papers.Independent.Intakethird100.P77.rangeTwo_encodedUniversalityPresent a uniform circuit family using nearest-neighbour controlled- 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 and an effectively uniform target family on four physical wires per logical wire, fixed before the logical input, such that
Here is the classical family parameter, is its actual gate count, is any normalized logical input, is either outcome, and linearly extends , . Every target gate is an allowable equal-determinant matchgate. The constant overhead is relative to the stated source presentation; this is universality with encoding.
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 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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a positive natural number such that the following holds for every source family . Such a family assigns to every finite Boolean string a width and a finite ordered list of gates, each either an arbitrary one-qubit unitary on a specified wire or a controlled- gate on two specified wires whose indices satisfy . Assume for every , and assume the family is effective in this precise sense: write for consecutive true bits and define by concatenating , one false bit, and for each ; the string , where is the gate-list length and a gate description is for a one-qubit gate or for controlled-, is computable from in polynomial time; moreover, the list of numerical data, obtained by listing each one-qubit matrix’s entries in the order and listing no entries for controlled-, has a polynomial-time approximation procedure. Specifically, on , for every valid data index , precision , and Boolean , that procedure outputs a string interpreted as a signed binary integer divided by , with error at most from the real part of entry when is false and its imaginary part when 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 of ordered gate lists on wires. Each gate specifies an injection of two local wires into these wires and two Boolean-indexed unitary matrices ; its local matrix has entry between strings of different parity, entry when both strings have even parity, and entry when both have odd parity. Every such gate in satisfies ; its two wire indices differ by at most ; and . This new family is effective: its exact code is , and its numerical data list concatenates the four entries of followed by the four entries of for every gate, with polynomial-time approximation in the same sense just specified. For every , every source wire with index , every target wire with index , every unit vector on length- bit strings, and every Boolean , the conclusion is
Here and apply the source and target gates, respectively, in their listed order, each gate acting identically on untouched wires, and
The assertion covers every finite string , 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.