Lemma G.4 — amplitude output bound: degree , bit length , normal forms of length
ProvedExactAmpDich.lemma_G_4counting-complexityholantp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-circuits
Let be a unitary library with coordinate tuple and a fixed variable order. There is a constant (depending on and the order) such that for every input whose circuit has gates and whose code has length :
- the real and imaginary parts of are , for polynomials of total degree at most with every coefficient of absolute value at most ;
- their normal forms have total degree at most and code length at most .
The bound controls the oracle answers in the specialization reduction (Lemma G.7).
Differences from the source:
- reading: "coefficient bit length O(m + 1)", "length poly(N)" → |coeff| ≤ 2^{C(m+1)} and code length ≤ C (N + 1)^C for one constant C; reason: the asymptotic notation for a fixed library and variable order
- encoding: inputs and outputs "written in binary" (normal forms as sorted monomial lists; rational coordinates in a basis) → fixed codes encodeInput, encPoly (terms in decreasing degLex order), encRat, coordsOut built from NPBinary.encodeNat; strings that are not input codes map to the empty string; reason: the paper fixes no bit layout; any two reasonable layouts are polynomial-time interconvertible, and the junk value on malformed strings is decidable in polynomial time
- reading: "a fixed variable order" → every variable order e; reason: the statement holds for each order and specializes to the fixed one
- encoding: a circuit is a sequence of gate occurrences on ordered tuples of distinct wires; U_C is the implemented unitary; ⟨a|U_C|b⟩ → Library as an indexed family with arities k_j ≥ 1; a placement is an injective map Fin k_j ↪ Fin n (gate qubit i on wire w i); U_C = U_m ⋯ U_1 (first occurrence applied first); the amplitude is the matrix entry (a, b); reason: Lean representation of the circuit model of §1.1 and App. A.1; same instances
Preamble
import Mathlib import Definitions.Def_ExactAmpDich_AmpNF set_option autoImplicit false
Formal statement
namespace ExactAmpDich
open QAlgorithms
/-- **Lemma G.4 (Amplitude output bound).** Liu–Meng, *A Dichotomy for Exact Quantum Circuit Amplitudes*, STOC 2027 submission (held manuscript, sha256 40ad9c68…), Lemma G.4, p.53 (PDF p.54): "For a circuit with m
gates, the real and imaginary parts of its amplitude have representatives in Z[X] of degree at most
m and coefficient bit length O(m + 1). Their normal forms have length poly(N) and degree at most
m."
Here `N` is the input length (the length of the input code) and the constants depend only on the
fixed library and variable order.
**Formalization Note.** "Coefficient bit length O(m + 1)" is `|coeff| ≤ 2^{C(m+1)}` and
"length poly(N)" is `≤ C (N + 1)^C`, for one constant `C`; the length of a normal form is the
length of its code `encPoly`. -/
theorem lemma_G_4 (L : Library) (hU : L.IsUnitary) {s : ℕ} (e : L.Coord ≃ Fin s) :
∃ C : ℕ, ∀ q : Input L,
(∃ p r : MvPolynomial (Fin s) ℤ,
MvPolynomial.aeval (fun i => L.alpha (e.symm i)) p = q.amp.re ∧
MvPolynomial.aeval (fun i => L.alpha (e.symm i)) r = q.amp.im ∧
p.totalDegree ≤ q.c.length ∧ r.totalDegree ≤ q.c.length ∧
(∀ μ, |p.coeff μ| ≤ 2 ^ (C * (q.c.length + 1))) ∧
(∀ μ, |r.coeff μ| ≤ 2 ^ (C * (q.c.length + 1)))) ∧
(nf L e q.amp.re).totalDegree ≤ q.c.length ∧ (nf L e q.amp.im).totalDegree ≤ q.c.length ∧
(encPoly (nf L e q.amp.re)).length ≤ C * ((encodeInput q).length + 1) ^ C ∧
(encPoly (nf L e q.amp.im)).length ≤ C * ((encodeInput q).length + 1) ^ C := by sorry
end ExactAmpDich
Source
Liu–Meng, A Dichotomy for Exact Quantum Circuit Amplitudes, STOC 2027 submission (held manuscript, sha256 40ad9c68…), Lemma G.4, p.53 (PDF p.54)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.