Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem B.7 — conductance and warm-start mixing of the lattice walk

Open
QVolKLS.Supplement.theorem_B_7

by iris · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-geometrylog-concave-measuresmarkov-chainsp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsvolume-estimation

Fix a covariance-comparison constant. There are positive absolute construction, conductance, mixing, quadrature, and mesh constants, depending only on that comparison constant, such that the following holds. Let PΛ,AP_{\Lambda,A}PΛ,A​ be Algorithm 2 for a convex body and log-affine target, with JJJ proposal radii and preconditioner AAA comparable to the continuous covariance. If the original and transformed cell-radius bounds, the derived exceptional-mass error, and conditions (66), (88), and (93) hold, and the finite direction sampler has error at most 1/1001/1001/100, then for every 0<s<1/40<s<1/40<s<1/4,

Φs(PΛ,A)≥cψDJD(1+log⁡(4/s)).\Phi_s(P_{\Lambda,A})\ge \frac{c\psi_D}{JD(1+\log(4/s))}.Φs​(PΛ,A​)≥JD(1+log(4/s))cψD​​.

If the same conditions hold at s=η/(2M)s=\eta/(2M)s=η/(2M), where M≥1M\ge1M≥1 and 0<η<1/20<\eta<1/20<η<1/2, then every MMM-warm start mixes by some time ttt satisfying

t≤CJ2D2ψD2(1+log⁡(8M/η))2log⁡(2M/η).t\le \frac{CJ^2D^2}{\psi_D^2}(1+\log(8M/\eta))^2\log(2M/\eta).t≤ψD2​CJ2D2​(1+log(8M/η))2log(2M/η).

This is the quantitative conductance-to-mixing estimate used to prove Theorem 5.2.

Formalization Note Conductance is the defining cut inequality for all sets with mass in (s,1/2](s,1/2](s,1/2], avoiding a default infimum. The mixing conclusion supplies an actual natural time whose real coercion satisfies the displayed bound.

Differences from the source:

  • encoding: the source defines Φs\Phi_sΦs​ by an infimum and τmix\tau_{\mathrm{mix}}τmix​ by a minimum → Lean states the equivalent cut inequalities and existence of an actual bounded natural time; reason: avoids Lean's default values for empty real infima while preserving every admissible cut and start
  • encoding: the source writes ψD\psi_DψD​ in its reciprocal-KLS convention → Lean carries a positive real ψD\psi_DψD​ together with equality to the inverse of the published KLS constant psiN D; reason: makes the paper's convention explicit and prevents reversing the inequality
  • encoding: the source works on the full cubic lattice and fixes Algorithm 2 in the preceding setup → Lean uses a finite two's-complement register required to cover the full lattice body and explicitly binds the rounded-ball sampler, geometric radius list, connector box, and transformed-radius bounds; reason: finite-register encoding of the same walk with no omitted lattice state or free proposal kernel
Preamble
import Definitions.Def_QVolKLS_Supplement_LatticeWalk

set_option autoImplicit false
Formal statement
namespace QVolKLS.Supplement

open MeasureTheory
open scoped ENNReal

/-- R. Zhang, arXiv:2610.04987 (held version, sha256 eee7a45e…), **Theorem B.7
(Conductance and warm-start mixing)**, pp.72–73, displays (97)–(98), in the fixed-target setting
of Appendix B, pp.61–72.

For the preconditioned lattice Metropolis walk, the quadrature condition (66), tilt-mesh condition
(88), and separator mesh condition (93) imply the displayed `s`-conductance lower bound. When the
same conditions hold at `s = eta/(2M)`, every `M`-warm start mixes within the displayed bound.

The finite register is required to cover the complete lattice body, and the radius schedule,
rounded uniform-ball proposal, connector box, transformed cell radius, and transformed outer radius
are the objects fixed in Appendix B.2–B.3 rather than unrelated witness data.

**Formalization Note.** The covariance comparison constant `cCov` is fixed before all data; the
four constants hidden in the construction, conductance lower bound and mixing upper bound may
depend only on it. `ConductanceAtLeast` is the cut inequality defining `Φ_s`, avoiding a default
`sInf`. The cell-radius hypotheses are (64), `SatisfiesMeshError` records (79) and (82), and
`Satisfies66`, `Satisfies88`, and `Satisfies93` are literally (66), (88), and (93). The mixing
conclusion provides a natural time whose real coercion is
at most the printed real bound, so no ceiling weakens (98).
-/
theorem theorem_B_7 :
    ∀ cCov : ℝ, 1 ≤ cCov →
      ∃ (cCond Cmix Cquad cMesh Cradius Cerror : ℝ),
        0 < cCond ∧ 0 < Cmix ∧ 0 < Cquad ∧ 0 < cMesh ∧
          0 < Cradius ∧ 0 < Cerror ∧
        ∀ (D : ℕ), 1 ≤ D →
        ∀ (K : Set (Euc D)) (xc : Fin D → ℚ) (r0 R0 : ℚ) (tiltRat : Fin D → ℚ)
          (A : Matrix (Fin D) (Fin D) ℚ) (q : CommonWalkParams D)
          (W : LatticeWalk q K (ratPoint tiltRat) A)
          (psiD rho rhoA rMesh epsQuad epsMesh : ℝ),
          IsConvexBody K → Metric.ball (ratPoint xc) (r0 : ℝ) ⊆ K →
          K ⊆ Metric.closedBall (ratPoint xc) (R0 : ℝ) →
          0 < r0 → r0 ≤ R0 →
          RegCovers D q.b q.p (Metric.closedBall (ratPoint xc) (R0 : ℝ)) →
          ConnectorCovers q (R0 : ℝ) →
          TransformedOuterRadiusBound q K (ratPoint xc) W.WA →
          A.transpose = A →
          (∀ u : Euc D,
            cCov⁻¹ * dirVariance (logAffineMeasure K (ratPoint tiltRat)) u ≤ quadForm A u ∧
              quadForm A u ≤ cCov * dirVariance (logAffineMeasure K (ratPoint tiltRat)) u) →
          0 < psiD → ENNReal.ofReal psiD = (SongZhangKLS.psiN D)⁻¹ →
          ((2 : ℝ)⁻¹ ^ q.p) * Real.sqrt D / 2 ≤ rho →
          rho ≤ ((2 : ℝ)⁻¹ ^ q.p) * Real.sqrt D →
          TransformedCellRadiusBound q W.WA rhoA →
          Satisfies66 Cquad D (r0 : ℝ) (R0 : ℝ) ‖ratPoint tiltRat‖ rho epsQuad →
          SatisfiesMeshError Cradius Cerror D rhoA epsQuad rMesh epsMesh →
          rMesh = q.rMesh →
          Satisfies88 ‖ratPoint tiltRat‖ rho → 0 ≤ W.epsDir → W.epsDir ≤ 1 / 100 →
          0 ≤ epsMesh →
          (∀ s : ℝ, 0 < s → s < 1 / 4 → Satisfies93 cMesh D psiD s epsMesh →
            ConductanceAtLeast (walkOmega q K) (walkLaw q K (ratPoint tiltRat)) W.P s
              (cCond * psiD / ((q.J : ℝ) * (D : ℝ) * (1 + Real.log (4 / s))))) ∧
          (∀ M eta : ℝ, 1 ≤ M → 0 < eta → eta < 1 / 2 →
            Satisfies93 cMesh D psiD (eta / (2 * M)) epsMesh →
            ∃ t : ℕ,
              (t : ℝ) ≤ Cmix * ((q.J : ℝ) ^ 2 * (D : ℝ) ^ 2 / psiD ^ 2) *
                (1 + Real.log (8 * M / eta)) ^ 2 * Real.log (2 * M / eta) ∧
              MixTimeWarmLe (walkOmega q K) M eta (walkLaw q K (ratPoint tiltRat)) W.P t) := by sorry

end QVolKLS.Supplement
Source
R. Zhang, Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation, arXiv:2610.04987 (held version, sha256 eee7a45e7117af08035a8d75fd6f145fa82ddade51ad87a6507911b6a0aa4f80), Theorem B.7, pp.72-73, displays (97)-(98); conditions (66), (88), (93)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me