Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

Kim, Kim, Lee, Baek, Park, Bang, Huh · arXiv:2604.27482 · 2026-05-01 (new submission, quant-ph) · score 8/10 (HIGH) · ← Back to digest

Abstract

Imaginary-time evolution is a standard primitive for ground-state preparation but is nonunitary, precluding direct quantum implementation. We develop Finite Imaginary-Time Evolution (FinITE), a finite-β construction for diagonal Pauli-Z cost Hamiltonians arising from polynomial unconstrained binary optimization (PUBO) instances, including QUBO and HUBO cases. FinITE uses the linear-combination-of-unitaries (LCU) framework to implement a scaled imaginary-time propagator. The commuting Pauli-Z structure makes termwise block-encodings compose without product-formula error, and higher-order Pauli-Z terms are handled directly without quadratization. The structure yields an exact finite-β identity between the LCU success probability and the ground-subspace fidelity. Combined with a gap-based fidelity lower bound, the identity yields a closed-form sufficient imaginary-time threshold β* for a chosen target fidelity. Statevector simulations verify the identity on a five-vertex MaxCut (QUBO) and an eight-qubit cubic HUBO instance.

Executive summary

FinITE is a clean, analytically-tight LCU+amplitude-amplification implementation of imaginary-time evolution specifically for the diagonal commuting-Pauli Hamiltonians of (P/QUBO/HUBO) optimisation. The headline analytic result — Proposition 1 — is an exact identity P_LCU(β)·F_g(β) = γ₀·e^{−2β(W+E₀)} linking LCU success probability and ground-subspace fidelity to a single exponential envelope, given the initial-state overlap γ₀ and the Pauli-decomposition ℓ₁-norm W. From this they derive a closed-form sufficient β*(F̄) for any target fidelity F̄. The benchmark numerical demonstration uses MaxCut (Y1's testbed) and a cubic HUBO (Y2/Y4-flavoured higher-order constrained) instance — overlap with Yuan's portfolio is on the conclusion side: another quantum end-to-end primitive for the same QUBO/HUBO Hamiltonians Y3 cares about, but bypassing the QAOA optimisation loop entirely.

Main contribution

For commuting diagonal Pauli-Z Hamiltonians H = Σ x_μσ_μ, FinITE implements a finite-β block-encoding of m(β)·e^−βH with subnormalisation m(β) = e^−βW. Each Pauli term gets its own LCU block; commutativity makes the joint product exact (no Trotter error) and avoids quadratization for ≥3-local terms. The exact spectral identity (Eqs. 5–7) gives both a state-dependent expression for P_LCU(β) tighter than the textbook Childs–Wiebe bound and a corollary β*(F̄) for sufficient imaginary time. Fixed-point amplitude amplification is then applied to the LCU-success subspace (which is known a priori — the all-zero ancilla outcome) with explicit query bound L = O(log(2/δ)·e^β*(W+E₀)/√γ₀).

Key theorems and corollaries

Proposition 1 (Exact identity, Sec. III.A): for any commuting diagonal-Z Hamiltonian and any initial state, P_LCU(β) F_g(β) = γ₀ e^{−2β(W+E₀)}, with individual spectral expressions P_LCU(β) = e^−2βW Σ |c_k|² e^−2βE_k and F_g(β) = γ₀·e^−2βE₀/(Σ |c_k|² e^−2βE_k).
Corollary 1 (Gap bound on fidelity): F_g(β) ≥ γ₀/(γ₀+(1−γ₀)e^−2βΔ), with Δ = first-excited gap.
Corollary 2 (Sufficient β*): β*(F̄) = (1/2Δ)·log(F̄(1−γ₀)/(γ₀(1−F̄))) suffices for F_g(β) ≥ F̄.
FPAA query bound (Eq. 13): L = O(log(2/δ)·e^β*(W+E₀)/√γ₀) at the fidelity threshold.
MaxCut benchmark (Sec. IV.A): on the 5-vertex non-bipartite test graph, P_LCU·F_g = (3/16)e^−4β matches simulation to relative error 1.3×10⁻¹⁴; with FPAA at L=15, P_g^(L) approaches unity for β > β*(0.98) ≈ 1.34.
HUBO benchmark (Sec. IV.B): 8-qubit cubic Pauli-Z instance with W=11.4, E₀=−6.6, |G|=8, Δ=1.2; identity verified across three γ₀ regimes (uniform 0.031, warm-start p=0.6 0.041, warm-start p=0.85 0.29) to relative error 1.2×10⁻¹².

Detailed walkthrough

Imaginary-time evolution e^−βH is the canonical ground-state-preparation primitive but is nonunitary; the standard quantum implementations are VITE (variational), QITE (local-unitary patching), and PITE (probabilistic via ancilla measurement). FinITE belongs to the LCU/block-encoding family but specialises hard to the commuting-Pauli case. Section II reviews the LCU primitive and FPAA basics. Section III is the analytic core.

The construction (Sec. III.A) writes e^−βH as a product of single-Pauli factors e^{−βx_μσ_μ}; commutativity means the product is exact. Each factor is block-encoded as a two-term LCU with κ_μ=coth(β|x_μ|), U_a=I, U_b=−sgn(x_μ)σ_μ. The subnormalisation per term is e^β|x_μ|, so the total subnormalisation is α_LCU(β) = e^βW, with W the Pauli ℓ₁-norm. The β→∞ limit (Eq. 9) collapses to a projector onto states satisfying every individual Pauli-eigenvalue sign constraint — useful only for bipartite-MaxCut-like instances where the ground state saturates the triangle inequality E₀=−W. For generic instances E₀ > −W, the limiting subspace is empty or exponentially small, motivating the finite-β construction.

The exact identity Proposition 1 is the paper's central analytic statement. Its derivation (Appendix C) is short — eigenbasis expansion of P_LCU = ‖M̂(β)|ψ₀⟩‖² and F_g(β) = ‖Π_Ge^−βH|ψ₀⟩‖²/‖e^−βH|ψ₀⟩‖² — but the consequences are substantial. The product P_LCU·F_g decays purely exponentially in β with a single rate 2(W+E₀); the prefactor γ₀ is the initial overlap. Crucially, the paper cleanly separates the two cost factors: the exponent W+E₀ is set by the Hamiltonian, while γ₀ is controllable by the initial state. This separation is exactly the warm-start lever Y1 exploits.

Corollary 2 gives a closed-form β*(F̄) for any target fidelity, depending only on the spectral gap Δ and γ₀. The β* rule is operationally honest: it requires lower bounds on both, which the authors note generally need classical preprocessing or auxiliary quantum subroutines. The "warm-start regime γ₀ ≳ 1/2" remark (Sec. III.B, regime (i)) is precisely the regime Y1's iterative warm-starting targets — small β* with large fidelity. The "adversarial regime γ₀→0" matches the worst-case for any post-selection ITE, and is presented as an information-theoretic barrier rather than a methodological deficiency.

The MaxCut benchmark (Sec. IV.A) uses a 5-vertex non-bipartite graph with E₀=−3, |G|=6, Δ=2, γ₀=3/16, predicting P_LCU·F_g = (3/16)e^−4β. Statevector simulation confirms the prediction to relative error ~10⁻¹⁴. Shot-based qasm-simulator runs (10³–10⁵ shots/β) demonstrate the trade-off: P_LCU falls and F_g rises along the predicted single envelope. Turning on FPAA at L ∈ {0,5,9,15} produces the expected Chebyshev oscillations in P_amp, with L=15 widening the β-range over which P_g^(L) ≈ 1 to include β*(0.98) ≈ 1.34.

The HUBO benchmark (Sec. IV.B) is the more interesting test for Yuan's purposes. The 8-qubit cubic Pauli-Z Hamiltonian (Eq. 14) has 4 cubic Z-Z-Z parity terms and 4 quadratic Z-Z bridges, structurally similar to Max-3-XORSAT / Max-3-SAT instances and to the kinds of higher-order interactions that arise in cardinality-constrained portfolio formulations after auxiliary-variable elimination. The identity envelope (1/32)e^−9.6β matches simulation to ~10⁻¹². Crucially, the warm-start sweep (Fig. 8) shows that boosting γ₀ from 0.031 to 0.29 raises the entire envelope by an order of magnitude — directly visualising Y1's mantra that warm-starting is the cheap lever.

The discussion (Sec. V) flags two follow-on directions: (i) proof-of-concept on real QPUs at small problem size (the M-ancilla LCU plus FPAA overhead is a real cost on current hardware); (ii) problem-specific warm-start strategies — exactly Yuan's research programme. The HUBO direct treatment without quadratization is a non-trivial advantage: Y2's quasi-binary encoding for portfolio uses higher-order interactions, and FinITE could in principle handle those without the auxiliary-variable explosion.

Figures

The 5-vertex non-bipartite MaxCut test graph with |E|=5 (triangle on {0,1,2} plus path 2–3–4). Three optimal cuts (six labelings counting Z₂ complement); E₀=−3, Δ=2, γ₀=3/16 with uniform initial state.

LCU circuit primitive — Quantum circuit for the two-term LCU primitive: Hadamard rotation on the ancilla, controlled application of U_a/U_b, post-selection on |0⟩ realises (κU_a+U_b)/(κ+1) up to subnormalisation κ+1.

Multi-controlled diagonal-Z gadget used by FinITE to block-encode higher-order Pauli-Z products without quadratization.

FPAA circuit — Fixed-point amplitude amplification circuit (Yoder et al. 2014). The marked subspace is the LCU-success event (all ancillae in |0⟩), so FPAA boosts P_LCU without requiring an estimate of the ground-subspace overlap.

MaxCut identity verification — Statevector identity check on the MaxCut instance: simulated P_LCU·F_g matches the prediction (3/16)e^−4β to relative error 1.3×10⁻¹⁴ across β ∈ [0, 2].

MaxCut without amplification — Shot-based MaxCut simulation without amplitude amplification: panel (a) shows P_LCU(β) decaying; panel (b) shows F_g(β) rising. Their product follows the single envelope (3/16)e^−4β.

MaxCut with FPAA at varying query depth L ∈ {0,5,9,15}. Panel (a): amplified success probability oscillates as a Chebyshev response. Panel (b): joint ground-subspace preparation probability P_g^(L) approaches unity for β > β*(0.98) ≈ 1.34 at L=15.

HUBO identity — HUBO (8-qubit cubic Pauli-Z) identity check with uniform initial state |+⟩⊗⁸: simulated P_LCU·F_g matches the closed-form prediction (1/32)e^−9.6β across β ∈ [0,3] to relative error 1.2×10⁻¹².

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1 (iterative warm-started QAOA, MaxCut, DGMVP scaling): Strong overlap on the warm-start mechanism. The HUBO benchmark sweep over γ₀ ∈ {0.031, 0.041, 0.29} directly demonstrates that initial-state overlap is the dominant cost lever — the same observation that motivates Y1's measurement-based iterative warm-starting. MaxCut is a shared testbed.
Y2 (quasi-binary portfolio, hard mixer): Y2's quasi-binary encoding produces higher-order Pauli-Z interactions; FinITE's direct treatment of HUBO without quadratization is exactly the primitive Y2's encoding needs to avoid the auxiliary-variable explosion of Rosenberg's gadget. Mid-overlap on method.
Y3 (DGMVP portfolio, layerwise QAOA, NISQ noise): FinITE is an alternative end-to-end primitive for the same QUBO/HUBO Hamiltonians Y3 targets via QAOA. The closed-form β*(F̄) is the FinITE analogue of Y3's layerwise-optimisation parameter rule.

Recommended action for Yuan

Implement FinITE for DGMVP (Y3) on a small instance: Y3's DGMVP QUBO is a perfect benchmark — directly compare the FPAA query cost L = O(log(2/δ)·e^β*(W+E₀)/√γ₀) against Y3's QAOA shot-noise scaling. If γ₀ can be lifted by Y3's classical-preprocessing warm starts, FinITE could match or beat layerwise QAOA at small problem sizes.
Test on Y2's HUBO portfolio formulation: Y2's quasi-binary encoding produces higher-order terms; FinITE handles them natively. Quantify the W and E₀ for a 6–8 asset DGMVP instance under quasi-binary encoding to estimate the FinITE FPAA query cost.
Email the authors: Park (Yonsei) and Huh (Yonsei Chemistry) work on quantum chemistry / optimisation primitives; this is a clean hook for collaboration. The explicit decomposition β*(F̄) + warm-start γ₀ structure invites a Yuan-style measurement-based iterative warm-start extension.