Theorem 34 — Uniform preparation from multiplicative marginal estimates
OpenTFIMPhaseDiagram.Classical.Supplement.theorem_34Let , , and let be arbitrary Hermitian matrices on qubits with . Suppose is entrywise real and nonnegative in the computational basis. For every partial pair , including the empty assignments, define the projectors and the marginals exactly as on p.31. Suppose a randomized classical estimator returns nonnegative and satisfies
The estimator has the finite-precision implementation assumed in footnote 14. Then a uniform quantum algorithm prepares a state satisfying
in time polynomial in , the estimator cost and . The Lean compiler depends only on the fixed finite estimator machine and receives , its bit-time and tape bounds, and the requested precision. Its actual circuit generation, gates and ancillas obey a single uniform polynomial before the varying matrices and resource parameters. All quantum registers except the output are traced out. The estimator hypothesis is a finite machine with an executed time bound and a uniform finite random tape, not an assumed good tape; exact-zero marginals require exact-zero estimates on the success event.
Formalization Note The variable bounds the finite-bit implementation's step count. Footnote 14 bounds that count by a polynomial in the source real-arithmetic runtime, and ; composing these polynomials gives exactly the source complexity guarantee.
Differences from the source:
- encoding: a randomized estimator with the finite-precision implementation in footnote 14 → a finite multistack machine, a padded R-bit tape with R at most T, and a time bound for every partial pair and tape; reason: bounded bit computations use at most T coin bits, and polynomial overhead composes with the source runtime
- encoding: partial configurations with 0 unspecified and projector products → Option Bool assignments and their diagonal compatibility projectors; reason: the bit false is spin +1, bit true is spin -1, and the empty assignment gives identity
- encoding: complex trace-ratio marginals and entrywise nonnegative U → the real part of the same ratio, with zero imaginary entries and nonnegative real entries required for U; reason: under the source hypotheses the ratio is already real and nonnegative
- encoding: a quantum algorithm in polynomial time → one uniform finite-bit circuit compiler, actual fixed-gate matrix execution and partial trace with explicit polynomial budget; reason: gates and workspace are charged, while compiler constants may depend only on the fixed estimator machine
- encoding: arbitrary real target tolerance → the same real tolerance with a logarithmic binary precision index; reason: every real target is attained; no rational-only or dyadic-only restriction is imposed
import Definitions.Def_TFIMPhaseDiagram_Classical_Supplement_computation set_option autoImplicit false noncomputable section
namespace TFIMPhaseDiagram.Classical.Supplement
/-- Theorem 34, p.31, including the finite-precision implementation assumption in
footnote 14. A fixed estimator machine is compiled uniformly; the constants may
depend on that finite machine, but not on n,H,R,T,accuracy or its random tape. -/
theorem theorem_34 (f : Word → Word) (M : BitMachine f) :
∃ (g : Word → Word) (G : BitMachine g) (C d : ℕ), 0 < C ∧
∀ (n : ℕ), 0 < n → ∀ (H A : QMat n) (e : ℝ), 0 < e → e < 1 →
H.IsHermitian → A.IsHermitian → euclideanOpNorm A ≤ e/8 →
(∀ x y, (halfExponential H A x y).im = 0 ∧ 0 ≤ (halfExponential H A x y).re) →
∀ T R : ℕ, MarginalEstimator f M T R H A e →
let input := compilerInput n T R (precisionBits e)
let c := circuitDecode (g input)
let B := C*(1+n+T+R+precisionBits e)^d
G.time input.length ≤ B ∧ circuitCost n c ≤ B ∧
schattenOne (circuitDensity n c - gibbsOf H) ≤ e := by sorry
end TFIMPhaseDiagram.Classical.Supplement