Theorem G.1 — For v ∈ (0,1): G_v satisfies (T1)–(T4) and GIP_cl(G_v) = PSPACE; L_v ∈ GMA(G_v) via a one-message protocol (|t|^4 copies of W_v, each measured wi
OpenGPTIP632.Classical.Supplement.theorem_G_1The source result is:
Theorem G.1 (One prover message and a noncomputable coordinate). Let and let be the theory of Example B.22. Then: (i) satisfies (T1)–(T4), and . (ii) : there is a one-message protocol in which the prover sends copies of and the verifier measures each copy with . (iii) If is not computable, then is undecidable. Hence contains an undecidable promise problem, strictly contains , and .
For every v ∈ (0,1), with G_v the constructed Theory of Example B.22: (i) (G_v).Standing ∧ GIPcl G_v = PromisePSPACE O₀; (ii) there is a verifier V of G_v witnessing L_v ∈ GMA(G_v) (one nontrivial message, sent by the prover; thresholds 2/3, 1/3) whose message on an input t of length m ≥ 1 is the composite W_v^{⊗m^4} and whose gates on it are only the measurement (f_y, u − f_y) applied once to each copy (plus classical gates); (iii) if ¬ IsComputableReal v: L_v is undecidable, ∃ L ∈ GMA(G_v) undecidable, PSPACE ⊂ GIP(G_v) strictly, GIPcl(G_v) ⊂ GIP(G_v) strictly. Every clause of (i)–(iii).
The concrete systems, gates, class definitions and any conclusion predicates are defined by the supplement interfaces. Completeness is at least 2/3 and soundness is at most 1/3, except for the explicitly quantified 0 < s < c < 1 clause of Lemma F.9. Every fixed message bound means at most k messages, counting both directions. No simulation theorem or class equality is assumed.
Differences from the source:
- encoding: finite-dimensional systems, composites and quantum channels in fixed bases → real coordinate frames, binary-tree register presentations (including a labelled copy of Delta_3), Kraus gate matrices and complete positivity on every ancilla dimension; reason: these represent the same quantum, classical and transported cones; labels and parentheses carry no operational data
- encoding: the explicitly defined QC, classical and triangular theories are valid theories → existential proofs of PreTheory.Ok package the fixed concrete data into the published Theory type; reason: validity is a conclusion, not an added hypothesis; proof irrelevance makes all such proof witnesses describe exactly the same theory
- encoding: one prover message of m^4 copies, each measured with (f_y,u-f_y) → one exchange with empty questions, a replicated triangular register, and exactly m^4 consuming y measurements plus classical gates; y has outcome index zero; reason: valid circuits consume each incoming triangular wire once, and zero-based outcome labels can be classically relabelled
- encoding: adaptive quantum or classical circuits in the source gate sets → published VData circuits and interaction probabilities, with zero-based outcome labels and classical copy as a constant-size circuit macro; reason: wire placements, total completion on malformed records, and recording the decision last preserve every physical interaction; copy is implemented using fixed preparation and reversible classical gates
import Mathlib import Definitions.Def_GPTIP632_Classical_Supplement_Claims set_option autoImplicit false
namespace GPTIP632.Classical.Supplement
open QAlgorithms.Complexity KTUnitary.Synth
theorem theorem_G_1 :
∀ v : Set.Ioo (0 : ℝ) 1,
∃ h : (gvPre v).Ok, G1Conclusion v h := by sorry
end GPTIP632.Classical.Supplement