arxiv: 2604.27482 · v1 · submitted 2026-04-30 · 🪐 quant-ph

Recognition: unknown

Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

Jaehee Kim , Juhyeon Kim , Gwonhak Lee , Kyunghyun Baek , Daniel K. Park , Jeongho Bang , Joonsuk Huh

Authors on Pith no claims yet

Pith reviewed 2026-05-07 10:30 UTC · model grok-4.3

classification 🪐 quant-ph

keywords imaginary-time evolutionlinear combination of unitariesground-state preparationPUBOQUBOquantum optimizationfinite betaPauli-Z Hamiltonian

0 comments

The pith

Commuting Pauli-Z terms in PUBO Hamiltonians produce an exact finite-beta identity equating LCU success probability to ground-subspace fidelity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a finite imaginary-time evolution procedure, FinITE, for preparing ground states of polynomial unconstrained binary optimization problems whose cost functions translate to diagonal Pauli-Z Hamiltonians. Because those operators all commute, the linear-combination-of-unitaries block encoding of the scaled propagator incurs no approximation error from ordering, and the measurement success probability on the ancilla exactly equals the overlap with the ground subspace at any finite beta. This identity, paired with a lower bound on fidelity that depends only on the spectral gap, supplies a closed-form threshold beta-star guaranteeing any chosen target fidelity once the gap and initial overlap are known. The same ancilla flag permits fixed-point amplitude amplification with an explicit query bound, and the construction accepts higher-order terms without first reducing them to quadratic form.

Core claim

For cost Hamiltonians composed solely of commuting diagonal Pauli-Z operators, the LCU realization of the finite imaginary-time propagator yields an exact identity at any finite beta between the probability of obtaining the success ancilla outcome and the fidelity of the post-selected state with the ground subspace; when this identity is combined with a gap-dependent lower bound on the fidelity, it produces a closed-form sufficient threshold beta-star for any prescribed target fidelity that depends only on estimates of the gap and the initial ground-subspace overlap.

What carries the argument

The exact finite-beta identity between LCU success probability and ground-subspace fidelity, which follows directly from the mutual commutation of all Pauli-Z terms in the cost Hamiltonian.

If this is right

A sufficient imaginary-time threshold beta-star can be computed in closed form from gap and overlap estimates to guarantee any target fidelity without iterative tuning.
Higher-order polynomial terms in the objective can be encoded directly without first converting the instance to quadratic form.
Fixed-point amplitude amplification can be applied with a known query-complexity bound because the success event is heralded by a definite ancilla outcome.
The same commuting structure eliminates Trotter or product-formula error when composing the individual term block encodings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The exact identity may extend to other diagonal commuting Hamiltonians outside optimization, allowing similar finite-beta guarantees for non-unitary evolution tasks.
If efficient classical or quantum routines for estimating the gap and initial overlap become available, the method supplies a resource-bounded route to ground-state preparation on near-term hardware.
One could check whether the predicted beta-star remains practical when the gap shrinks polynomially with problem size on larger MaxCut or HUBO instances.

Load-bearing premise

The cost Hamiltonian must be built exclusively from commuting diagonal Pauli-Z operators, and usable numerical estimates of the spectral gap and the initial ground-subspace overlap must be supplied to evaluate the beta-star threshold.

What would settle it

Measuring the LCU success probability on a small, exactly solvable PUBO instance whose Hamiltonian is purely commuting Pauli-Z and finding that it differs from the independently computed ground-subspace fidelity at the chosen finite beta.

Figures

Figures reproduced from arXiv: 2604.27482 by Daniel K. Park, Gwonhak Lee, Jaehee Kim, Jeongho Bang, Joonsuk Huh, Juhyeon Kim, Kyunghyun Baek.

**Figure 1.** Figure 1: Five-vertex MAX-CUT test graph with |E| = 5 edges. The curve indicates one of the three optimal cuts (six ground-state labelings counting partition complements); the graph is non-bipartite, so no cut separates every edge. The five edges {(0, 1),(0, 2),(1, 2),(2, 3),(3, 4)} combine a triangle on {0, 1, 2} with a path 2–3–4. For this graph the Pauli decomposition has W = X (i,j)∈E |xij | = |E| = 5, (22) sinc… view at source ↗

**Figure 2.** Figure 2: Identity validation on the 5-vertex MAX-CUT instance with view at source ↗

**Figure 3.** Figure 3: Simulation results of MAX-CUT without amplitude amplification. (a) LCU success probability view at source ↗

**Figure 4.** Figure 4: Simulation results with varying query complexities view at source ↗

**Figure 5.** Figure 5: Identity check on the weighted HUBO instance Eq. view at source ↗

**Figure 6.** Figure 6: Initial-state dependence on the HUBO Hamiltonian Eq. view at source ↗

**Figure 7.** Figure 7: Quantum circuit for performing LCU by a non-deterministic process. We obtain view at source ↗

**Figure 8.** Figure 8: Quantum circuit for fixed-point amplitude amplification. view at source ↗

**Figure 9.** Figure 9: Quantum circuit for a multi-controlled double NOT gate. The gate decomposes into two view at source ↗

read the original 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-beta 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-beta 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 beta-star for a chosen target fidelity. The threshold depends on estimates of the spectral gap and the initial ground-subspace overlap. Because the LCU success event is flagged by a known ancilla outcome, we integrate fixed-point amplitude amplification with an explicit query-complexity bound. Statevector simulations verify the identity on a five-vertex MaxCut (QUBO) and an eight-qubit cubic HUBO instance, and shot-based simulations on the MaxCut instance illustrate the predicted finite-beta threshold and amplification procedure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

FinITE gives a direct LCU route to finite imaginary-time evolution on commuting diagonal PUBO Hamiltonians and claims an exact success-probability identity, but the normalization step appears to break exactness for generic instances.

read the letter

The paper's core move is to exploit the fact that PUBO cost Hamiltonians are sums of commuting Pauli-Z strings, so the imaginary-time operator factors exactly into a product of single-term unitaries that can be block-encoded without Trotter error. They then wrap this in LCU, post-select on the ancilla, and derive what they call an exact relation between the success probability and the ground-subspace fidelity. That relation plus a gap-based lower bound on fidelity is supposed to deliver a closed-form beta-star threshold. They also fold in fixed-point amplitude amplification with an explicit query count and show small statevector and shot simulations on a five-vertex MaxCut and an eight-qubit cubic HUBO instance. Those are the concrete pieces that are new relative to standard imaginary-time or LCU work on optimization problems. The commuting structure really does let them skip product-formula approximations and quadratization, which is useful for higher-order PUBO. The simulations at least confirm the numerical behavior on the tested cases and illustrate the amplification step. The soft spot is the claimed exact identity. The termwise product for the block encodings produces an LCU coefficient alpha equal to exp(beta times sum of absolute coefficients), but the true operator norm of exp(-beta H) is exp(-beta E0). These coincide only when the ground-state energy sits at the absolute lower bound set by the coefficients; for generic PUBO instances it does not. The post-selection probability therefore picks up an extra factor, so the simple p = |a0|^2 / F relation does not hold in general and the gap-based beta-star is no longer guaranteed to be sufficient without separate knowledge of E0. The small simulations may simply land on instances where the mismatch is negligible. The method still requires independent estimates of the gap and initial overlap, which are not free. This work is aimed at people building quantum primitives for combinatorial optimization who already think in LCU or imaginary-time terms. A reader who wants a concrete, non-variational alternative for diagonal Hamiltonians will find usable pieces even if the exactness claim needs repair. I would send it to peer review; the algorithmic idea is clear enough and the simulations exist, but the authors need to resolve the normalization question before the threshold formula can be trusted.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Finite Imaginary-Time Evolution (FinITE), a construction that uses the linear-combination-of-unitaries (LCU) framework to realize a finite-beta imaginary-time propagator for diagonal Pauli-Z Hamiltonians arising from PUBO (including QUBO and HUBO). It claims that the commuting structure yields an exact identity relating the LCU success probability to the ground-subspace fidelity; combined with a gap-based lower bound on fidelity, this produces a closed-form sufficient threshold beta-star depending on gap and initial overlap estimates. Fixed-point amplitude amplification is integrated with an explicit query-complexity bound. Statevector simulations on a 5-vertex MaxCut instance and an 8-qubit cubic HUBO instance are said to verify the identity, while shot-based runs illustrate the threshold.

Significance. If the central identity holds exactly and the beta-star threshold is both sufficient and closed-form without hidden dependence on unknown quantities such as E0, the work would supply a non-variational route to guaranteed-fidelity ground-state preparation for combinatorial optimization problems, together with a concrete complexity bound. This would be a meaningful addition to the toolkit for quantum algorithms targeting PUBO instances.

major comments (2)

[Abstract and LCU identity derivation] Abstract and the derivation of the LCU identity: the claimed exact relation between LCU success probability p and ground-subspace fidelity F (p = |a0|^2 / F) does not hold for generic PUBO. The product expansion of e^{-beta H} = prod_j (cosh(beta lambda_j) I - sinh(beta lambda_j) P_j) produces an LCU normalization alpha = exp(beta sum |lambda_j|), which equals ||e^{-beta H}|| = e^{-beta E0} only when the ground-state eigenvalue saturates E0 = -sum |lambda_j|. For generic instances this inequality is strict, so the actual success probability satisfies p = |a0|^2 * (e^{-beta E0}/alpha)^2 / F. Consequently the gap-based lower bound on F cannot yield a closed-form sufficient beta-star that is both exact and independent of E0.
[LCU construction] LCU implementation section: while the commuting Pauli-Z structure permits an exact (non-Trotter) product, realizing the propagator via LCU requires expanding the product into 2^m terms where m is the number of Hamiltonian terms. For polynomial-degree PUBO, m is typically polynomial in n, rendering the LCU query cost exponential in m. The manuscript does not address how this expansion is avoided or mitigated while still claiming an efficient block-encoding.

minor comments (2)

The manuscript would benefit from an explicit equation (with all symbols defined) for the LCU success probability p in terms of the fidelity F, the overlap |a0|, and the normalization alpha.
Simulation details (statevector and shot-based) should include the precise values of beta, the estimated gap, and the initial overlap used to compute beta-star, together with error bars on the observed fidelity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive comments on our manuscript. We address each major comment point by point below, with revisions planned where appropriate to enhance accuracy and clarity.

read point-by-point responses

Referee: [Abstract and LCU identity derivation] Abstract and the derivation of the LCU identity: the claimed exact relation between LCU success probability p and ground-subspace fidelity F (p = |a0|^2 / F) does not hold for generic PUBO. The product expansion of e^{-beta H} = prod_j (cosh(beta lambda_j) I - sinh(beta lambda_j) P_j) produces an LCU normalization alpha = exp(beta sum |lambda_j|), which equals ||e^{-beta H}|| = e^{-beta E0} only when the ground-state eigenvalue saturates E0 = -sum |lambda_j|. For generic instances this inequality is strict, so the actual success probability satisfies p = |a0|^2 * (e^{-beta E0}/alpha)^2 / F. Consequently the gap-based lower bound on F cannot yield a closed-form sufficient beta-star that is both exact and independent of E0.

Authors: We thank the referee for identifying this important nuance in the LCU normalization factor. The product expansion indeed yields alpha = exp(beta sum_j |lambda_j|), while ||e^{-beta H}|| = exp(-beta E_0), with equality only when a ground-state configuration simultaneously minimizes all terms. We will revise the abstract and the relevant derivation sections to state the precise identity p = |a0|^2 (e^{-beta E_0}/alpha)^2 / F. However, the gap-based lower bound on the post-evolution ground-subspace fidelity F >= f / (f + (1-f) exp(-2 beta Delta)), with f = |a0|^2 the initial overlap and Delta the spectral gap, remains independent of E_0. This permits a closed-form sufficient threshold beta^* = (1/(2 Delta)) ln( ((1-f)/f) / (1/tau - 1) ) for target fidelity tau that guarantees the desired F without requiring knowledge of E_0. The corrected identity still enables relating the observed success probability to fidelity (with the factor bounded by 1), and we will update the discussion of beta^* to incorporate this. These changes preserve the utility of the threshold while correcting the presentation. revision: yes
Referee: [LCU construction] LCU implementation section: while the commuting Pauli-Z structure permits an exact (non-Trotter) product, realizing the propagator via LCU requires expanding the product into 2^m terms where m is the number of Hamiltonian terms. For polynomial-degree PUBO, m is typically polynomial in n, rendering the LCU query cost exponential in m. The manuscript does not address how this expansion is avoided or mitigated while still claiming an efficient block-encoding.

Authors: We thank the referee for raising this point on implementation efficiency. Although the product expands formally to a sum over 2^m terms, the commuting Pauli-Z structure enables an efficient LCU realization without exponential overhead. The prepare unitary creates a uniform superposition over m ancilla qubits at O(m) cost. The select unitary applies each P_j controlled on the corresponding ancilla bit, requiring only O(m) controlled-Pauli gates (each P_j being a Pauli string implementable in O(n) time). The resulting block-encoding thus has query complexity linear in m, which is polynomial for polynomial-degree PUBO instances. We will revise the LCU implementation section to explicitly describe this efficient construction, clarifying that the 'termwise block-encodings compose' property leverages the commuting structure to avoid any exponential cost in the select and prepare oracles. This supports the claimed explicit query-complexity bound. revision: yes

Circularity Check

0 steps flagged

No circularity; identity and threshold derived directly from commuting structure with external inputs

full rationale

The paper's central derivation starts from the given commuting diagonal Pauli-Z form of the PUBO Hamiltonian and explicitly constructs the LCU block-encoding via termwise factors. The claimed finite-beta identity between LCU success probability and ground-subspace fidelity follows from this algebraic structure without any parameter fitting or redefinition of inputs. The subsequent closed-form beta-star is obtained by combining that identity with an independent gap-based lower bound on fidelity; the gap and initial overlap appear only as externally supplied estimates, not as quantities fitted or redefined inside the same equations. No self-citation is load-bearing for the identity itself, and no ansatz or renaming reduces the result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard LCU framework and the commuting property of Pauli-Z operators; no explicit free parameters are introduced, but the beta-star threshold requires external gap and overlap estimates that are treated as inputs.

axioms (2)

standard math Linear combination of unitaries can implement a scaled non-unitary propagator when the target operator is a sum of commuting unitaries
Invoked to realize the finite imaginary-time operator without product-formula error.
domain assumption The cost Hamiltonian for PUBO instances is diagonal in the computational basis and consists only of Pauli-Z products
Stated as the structural property that enables termwise block-encoding composition.

invented entities (1)

FinITE no independent evidence
purpose: Finite imaginary-time evolution operator realized via LCU for PUBO Hamiltonians
New algorithmic construction introduced to achieve exact finite-beta behavior.

pith-pipeline@v0.9.0 · 5556 in / 1664 out tokens · 41914 ms · 2026-05-07T10:30:53.610366+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 12 canonical work pages · 2 internal anchors

[1]

The unconstrained binary quadratic programming problem: a survey

Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng L¨ u, Haibo Wang, and Yang Wang. “The unconstrained binary quadratic programming problem: a survey”. Journal of Combinatorial Optimization28, 58–81 (2014)

2014
[2]

Challenges and oppor- tunities in quantum optimization

Amira Abbas, Andris Ambainis, Brandon Augustino, et al. “Challenges and oppor- tunities in quantum optimization”. Nature Reviews Physics6, 718–735 (2024). 18

2024
[3]

Ising formulations of many np problems

Andrew Lucas. “Ising formulations of many np problems”. Frontiers in physics2, 5 (2014)

2014
[4]

Quantum Monte Carlo simulations of solids

W. M. C. Foulkes, L. Mitas, R. J. Needs, and G. Rajagopal. “Quantum Monte Carlo simulations of solids”. Rev. Mod. Phys.73, 33–83 (2001)

2001
[5]

Efficient simulation of one-dimensional quantum many-body systems

Guifr´ e Vidal. “Efficient simulation of one-dimensional quantum many-body systems”. Physical review letters93, 040502 (2004)

2004
[6]

The density-matrix renormalization group in the age of matrix prod- uct states

U. Schollw¨ ock. “The density-matrix renormalization group in the age of matrix prod- uct states”. Ann. Phys.326, 96–192 (2011)

2011
[7]

Variational ansatz-based quantum simulation of imaginary time evolution

Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. “Variational ansatz-based quantum simulation of imaginary time evolution”. npj Quantum Information5, 75 (2019). arXiv:1804.03023

work page arXiv 2019
[8]

Combinato- rial optimization with quantum imaginary time evolution

Nora M. Bauer, Rizwanul Alam, James Ostrowski, and George Siopsis. “Combinato- rial optimization with quantum imaginary time evolution” (2023). arXiv:2312.16664

work page arXiv 2023
[9]

De- termining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution

Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brand˜ ao, and Garnet Kin-Lic Chan. “De- termining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution”. Nature Physics16, 205–210 (2020). arXiv:1901.07653

work page arXiv 2020
[10]

Imaginary-time evolution using forward and backward real-time evolution with a single ancilla: First-quantized eigensolver algorithm for quantum chemistry

Taichi Kosugi, Yusuke Nishiya, Hirofumi Nishi, and Yu-ichiro Matsushita. “Imaginary-time evolution using forward and backward real-time evolution with a single ancilla: First-quantized eigensolver algorithm for quantum chemistry”. Physi- cal Review Research4, 033121 (2022)

2022
[11]

Probabilistic imaginary-time evolution algorithm based on nonunitary quantum circuits

Hao-Nan Xie, Shi-Jie Wei, Fan Yang, Zheng-An Wang, Chi-Tong Chen, Heng Fan, and Gui-Lu Long. “Probabilistic imaginary-time evolution algorithm based on nonunitary quantum circuits”. Physical Review A109, 052414 (2024)

2024
[12]

Exact block encoding of imaginary time evolution with universal quantum neural networks

Ermal Rrapaj and Evan Rule. “Exact block encoding of imaginary time evolution with universal quantum neural networks”. Physical Review Research7, 013306 (2025)

2025
[13]

Classical optimization with imag- inary time block encoding on quantum computers: The maxcut problem

Dawei Zhong, Akhil Francis, and Ermal Rrapaj. “Classical optimization with imag- inary time block encoding on quantum computers: The maxcut problem”. Physical Review A112, 042420 (2025)

2025
[14]

A proba- bilistic quantum algorithm for imaginary-time evolution based on Taylor expansion

Xin Yi, Jiacheng Huo, Guanhua Liu, Ling Fan, Ru Zhang, and Cong Cao. “A proba- bilistic quantum algorithm for imaginary-time evolution based on Taylor expansion”. EPJ Quantum Technology12, 43 (2025)

2025
[15]

Hamiltonian Simulation Using Linear Com- binations of Unitary Operations

Andrew M Childs and Nathan Wiebe. “Hamiltonian Simulation Using Linear Com- binations of Unitary Operations” (2012). arXiv:1202.5822

work page arXiv 2012
[16]

Fixed-Point Quantum Search

Lov K. Grover. “Fixed-Point Quantum Search”. Physical Review Letters95, 150501 (2005). arXiv:quant-ph/0503205

work page arXiv 2005
[17]

Fixed-Point Quan- tum Search with an Optimal Number of Queries

Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. “Fixed-Point Quan- tum Search with an Optimal Number of Queries”. Physical Review Letters113, 210501 (2014). arXiv:1409.3305

work page arXiv 2014
[18]

Reduction of bivalent maximization to the quadratic case

Ivo G. Rosenberg. “Reduction of bivalent maximization to the quadratic case”. Cahiers du Centre d’ ´Etudes de Recherche Op´ erationnelle17, 71–74 (1975)

1975
[19]

Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics

Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. “Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics”. In Proceedings of the 51st Annual ACM SIGACT Symposium on The- ory of Computing. Pages 193–204. (2019). 19

2019
[20]

Quantum amplitude amplification and estimation.Contemporary Mathematics, 305:53–74, 2002

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. “Quantum ampli- tude amplification and estimation”. Contemporary Mathematics305, 53–74 (2002). arXiv:quant-ph/0005055

work page arXiv 2002
[21]

On the Representation of Boolean and Real Functions as Hamil- tonians for Quantum Computing

Stuart Hadfield. “On the Representation of Boolean and Real Functions as Hamil- tonians for Quantum Computing”. ACM Transactions on Quantum Computing2, 1–21 (2021). arXiv:1804.09130

work page arXiv 2021
[22]

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028

work page internal anchor Pith review arXiv 2014
[23]

Training a quantum optimizer

Dave Wecker, Matthew B. Hastings, and Matthias Troyer. “Training a quantum optimizer”. Physical Review A94, 022309 (2016). arXiv:1605.05370

work page arXiv 2016
[24]

Quantum computing with Qiskit

Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. “Quantum computing with Qiskit” (2024). arXiv:2405.08810

work page internal anchor Pith review arXiv 2024
[25]

Integration of the schr¨ odinger equation in imaginary time

Abraham Goldberg and Judah L Schwartz. “Integration of the schr¨ odinger equation in imaginary time”. Journal of Computational Physics1, 433–447 (1967)

1967
[26]

Solving the Schr¨ odinger eigen- value problem by the imaginary time propagation technique using splitting methods with complex coefficients

Philipp Bader, Sergio Blanes, and Fernando Casas. “Solving the Schr¨ odinger eigen- value problem by the imaginary time propagation technique using splitting methods with complex coefficients”. The Journal of Chemical Physics139, 124117 (2013)

2013
[27]

Linear-depth quantum circuits for mul- tiqubit controlled gates

Adenilton J. da Silva and Daniel K. Park. “Linear-depth quantum circuits for mul- tiqubit controlled gates”. Physical Review A106, 042602 (2022). arXiv:2203.11882. A Notation Table 1 collects the symbols used throughout the paper, with the section or equation where each is first introduced. B Imaginary-Time Evolution Formally replacing real time by imagin...

work page arXiv 2022