Bounded-error nearest-neighbour matchgate languages lie in deterministic P
OpenQAlgorithms.Papers.Independent.Intakethird100.P77.nearestBoundedError_inPFor each input length, fix one effectively uniform nearest-neighbour matchgate circuit, with enough wires for the computational-basis input and zero workspace, and one existing output wire. Every local parity block is unitary and the even and odd determinants agree. Suppose the output bit is correct with probability at least on every input. Then the decided language belongs to deterministic polynomial time:
Here the left class is exactly the class of languages admitted by those circuit families, and is defined by a characteristic function computed by an actual polynomial-time finite Turing machine. This is the bounded-error specialization of strong simulation, using only constant precision.
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.3: bounded-error nearest-neighbour matchgate decision languages are
in deterministic P. The class definitions fix one circuit per input length,
computational-basis inputs, uniform finite descriptions and the 2/3 gap. -/
theorem nearestBoundedError_inP :
{L : Set Str | InBoundedMatchgate 1 L} ⊆ {L : Set Str | InP L} := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P77
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every language of finite Boolean strings, suppose there exists a family assigning widths and finite gate lists to all strings , with output wires and for every . Each gate consists of unitary Boolean-indexed complex matrices and an injective ordered pair of wires ; at unary strings, require and . Its local matrix uses on the even-parity block and on the odd-parity block, each indexed by the first bit, is zero between blocks, and leaves other wires unchanged. Require the following effectiveness conditions: putting and , the functions and are polynomial-time computable, and there is a polynomial-time function returning approximations within to each real or imaginary gate-matrix entry at input . Here indexes the list of entries of followed by , in gate order and entry order ; selects the real part and true the imaginary part; and the output is read as its binary tail divided by , negated when its first bit is true, with missing bits zero. Let be the reverse-order product of embedded gates at , with the empty product the identity, and the input padded with false to that width. Suppose, for every , the sum is at least when and at most when . Then there exists a polynomial-time function on Boolean strings returning exactly [true] for members of and exactly [false] for nonmembers. Every polynomial-time requirement here means computability by a TM2 Turing machine with identity input and output encodings; all conditions include the empty input.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.