Nearest-neighbour PQP matchgate languages lie in deterministic P
OpenQAlgorithms.Papers.Independent.Intakethird100.P77.nearestPQP_inPLet consist of languages recognized by effectively uniform nearest-neighbour matchgate circuits on computational-basis inputs and zero workspace, with a single designated output. Require symmetric majority gaps of inverse-exponential size: one polynomial is selected before all inputs, with , and acceptance is at least on members and at most on nonmembers. Then
The polynomial exponent makes the source polynomial-padding convention explicit and keeps the condition meaningful at input length zero. The classical characteristic-function machine has worst-case polynomial runtime. This conclusion uses polynomially many strong-simulation accuracy digits to resolve the exponentially small gap.
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.16: nearest-neighbour PQP matchgate languages lie in P. Polynomially
many precision digits suffice for the explicitly padded inverse-exponential
gap; no constant bounded-error gap is substituted. Printed: gap 2^(-n).
Changed: one polynomially padded exponent >=2, chosen before all inputs.
Why: the literal zero-length gap is impossible, and the source's simulation
argument only needs polynomially many precision digits. -/
theorem nearestPQP_inP :
{L : Set Str | InPQPMatchgate 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 of widths , finite gate lists, and output wires , with for every , together with a polynomial with natural-number coefficients satisfying for every . Every gate has unitary Boolean-indexed complex matrices and an injective ordered wire pair ; at each unary string require and . Its local matrix uses on even-parity rows and columns, on odd-parity rows and columns, indexing each block by the first bit, and zero between different parities, while leaving all other wires unchanged. Put and . Assume polynomial-time computability of and , and polynomial-time approximation of the complex gate data as follows: for every valid entry index , precision , and Boolean , input yields a number within of the real part if , or imaginary part if . Entries are listed gate by gate, before , each in order ; an output string denotes its binary tail divided by , negated when its first bit is true, with missing bits zero. Let be the reverse-order product of the embedded gate list at , the empty product being the identity, and let be padded with false to that width. Suppose that, for every , the quantity is at least when , and at most when . Then a polynomial-time Boolean-string function exists which returns exactly [true] on and exactly [false] outside . Polynomial time throughout means computability by a TM2 Turing machine with identity input and output encodings, and every input condition includes the empty string.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.