Lemma G.6 (first sentence) — hard algebraic specialization
ProvedExactAmpDich.lemma_G_6counting-complexityholantp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-circuits
Let be a unitary library with coordinate tuple and . There is a real algebraic tuple , indexed by the same coordinate positions, such that every rational polynomial vanishing at vanishes at , the specialized library is unitary, and .
Together with Lemma G.7 this transfers #P-hardness from the algebraic case to arbitrary complex entries.
Differences from the source:
- reading: "Such a tuple can be found effectively from a finite generating set of I." → not stated in this item (its title names the part formalized); reason: effectivity of a fixed-library preprocessing step; the title says "first sentence"
- encoding: β satisfies every polynomial in I ⊆ ℚ[X₁, …, X_s] → every p ∈ ℚ[coordinate positions] with p(α) = 0 has p(β) = 0; reason: the variables are the coordinate positions themselves; no variable order is needed
- encoding: FP, polynomial-time Turing reductions, #P; Clifford = normalizer of the Pauli group with arbitrary global phases → CookLevin.IsPolyTimeComputable; oracle machines of ConsModCount.OracleMachine with one step per oracle call; NQueensComp.NPC.InSharpP; QAlgorithms.Clifford.normalizer; reason: published platform models of these notions; they add no condition
Preamble
import Mathlib import Definitions.Def_ExactAmpDich_QTract import Definitions.Def_ExactAmpDich_AmpNF set_option autoImplicit false
Formal statement
namespace ExactAmpDich
open QAlgorithms
/-- **Lemma G.6 (Hard algebraic specialization), first sentence.** Liu–Meng, *A Dichotomy for Exact Quantum Circuit Amplitudes*, STOC 2027 submission (held manuscript, sha256 40ad9c68…), Lemma G.6, p.54 (PDF p.55):
"If ¬QTract(G), there is a fixed β ∈Rs alg satisfying every polynomial in I such that the
specialized library Gβ is unitary and satisfies ¬QTract(Gβ)."
**Formalization Note.** The relation ideal is written over the coordinate positions themselves
(`MvPolynomial L.Coord ℚ`), which needs no variable order. The second sentence (effectivity) is not
formalized. -/
theorem lemma_G_6 (L : Library) (hU : L.IsUnitary) (hhard : ¬ QTract L) :
∃ β : L.Coord → ℝ, (∀ c, IsAlgebraic ℚ (β c)) ∧
(∀ p : MvPolynomial L.Coord ℚ, MvPolynomial.aeval L.alpha p = 0 →
MvPolynomial.aeval β p = 0) ∧
(L.specialize β).IsUnitary ∧ ¬ QTract (L.specialize β) := by sorry
end ExactAmpDich
Source
Liu–Meng, A Dichotomy for Exact Quantum Circuit Amplitudes, STOC 2027 submission (held manuscript, sha256 40ad9c68…), Lemma G.6, p.54 (PDF p.55)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.