Protocol-Conditioned Finite-Time Hitting for Warm-Started QeMCMC-Inspired MIS: Lifted Formulation and Single-Chain Surrogate Theory

AbstractQuantum-enhanced Markov chain Monte Carlo (QeMCMC) was introduced as an exact route to sampling a prescribed Boltzmann law. Warm-started QeMCMC-inspired workflows for maximum independent set (MIS) motivate a different analysis: finite-shot proposal pools, selector bias, and protocol memory make the executed dynamics protocol dependent, so finite-time or finite-budget optimum recovery replaces stationary Gibbs fidelity as the natural observable. At the foundational level this regime is formulated by a protocol-conditioned lifted kernel on an augmented state space. The results proved here concern a selector-controlled single-chain surrogate, not a full exact theory of the replica-coupled workflow. We record the exact accumulated-hazard representation of finite-horizon success and its budgeted counterpart, then prove quantitative finite-shot control of a hard-cutoff selector surrogate for keep-all-ties top-k selection from i.i.d. proposal pools under explicit quantile-gap assumptions, together with a finite-m bridge to exact-k boundary-randomized retention. Specializing to MIS, we calibrate the surrogate exactly on the public 17-node benchmark. Shellwise structure organizes one-step hazard, finite-horizon success, and matched-budget success, while projected Gibbs-defect profiling shows that residual non-Gibbsity is selector-driven rather than inverse-temperature-mismatch driven. A brief 52-node appendix provides only descriptive shellwise support and is not part of the theorem-level validation.