arXiv:2604.27482

Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

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

quant-phSubmitted Apr 30, 2026• Announced May 1, 2026• 0 citations

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.

Comments: 28 pages, 9 figures, 1 table

Related papers

Pauli Propagation for Imaginary-Time Evolution

Rafael Gómez-Lurbe, Armando Pérez

We extend the Pauli Propagation framework to imaginary-time evolution and introduce imaginary-time Pauli Propagation (ITPP), an operator-based algorithm for approximating thermal and ground-state properties directly in the Pauli basis. We derive explicit imaginary-time propagation rules for Pauli strings and analyze the main approximation errors arising from Trotterization and Pauli-space truncation, including bounds that account for the non-unitary nature of the evolution. Benchmarking ITPP on the one-dimensional transverse field Ising model, we find that the method performs best in the high-temperature regime, where thermal states admit a compressed Pauli-basis approximation, while the required number of Pauli terms grows rapidly as the system approaches the ground-state limit. We further compare with tensor network simulations and study finite-temperature scalability through the number of retained Pauli terms required to reach a fixed target accuracy. These results establish ITPP as a complementary framework for imaginary-time simulation and suggest that combining imaginary-time and real-time Pauli Propagation could provide a pathway toward simulating more general non-unitary and open quantum system dynamics within a unified Pauli-based framework.

quant-pharXiv:2601.14400New Journal of PhysicsJan 22, 20260 citations

Quantum imaginary-time evolution with polynomial resources in evolution time

Lei Zhang, Jizhe Lai, Xian Wu +1 more

Abstract Imaginary-time evolution is fundamental for analyzing quantum many-body systems, with applications spanning quantum chemistry, condensed matter physics, and quantum field theory, yet classical simulation requires exponentially growing resources in both system size and evolution time. While quantum approaches reduce the system-size scaling, existing methods rely on heuristic techniques with measurement precision or success probability that deteriorates as evolution time increases. We present a quantum algorithm that prepares normalized imaginary-time evolved states using an adaptive normalization factor to maintain a stable success probability over long imaginary-time intervals. Our algorithm approximates the target state with error polynomially small in the inverse imaginary time using a polynomial number of elementary quantum gates and a single ancilla qubit, with success probability close to one. When the initial state has reasonable overlap with the ground state, this algorithm also achieves polynomial query complexity in the system size. To our knowledge, this is the first quantum algorithm for imaginary-time evolution with provably polynomial resource scaling in evolution time. Numerical experiments validate our theoretical analysis for evolution time up to 50, demonstrating the algorithm’s effectiveness for long-time evolution. Building on this technique, we further develop imaginary-time-evolution-based algorithms for ground-state-related problems and for simulating open quantum systems. These algorithms can reduce circuit depth in certain regimes compared with existing methods, at the expense of higher total query complexity, advancing the practical feasibility of quantum simulation on early fault-tolerant devices.

arXiv:2507.00908Quantum Science and TechnologyJun 10, 20261 citation

Variationally Optimized Imaginary-time Polynomial Filters for Ground State Projection

Bahman Seifi, Ibsal Assi, J. P. F. LeBlanc

In this work, we develop a variational imaginary-time evolution (ITE) framework based on polynomial filtering, derived from an operator-level action principle, which yields an optimized non-unitary projector expressed as a polynomial in the Hamiltonian. Starting from a single-ancilla, first-order imaginary-time update defined by a Taylor expansion and Trotter-Suzuki (TS) decompositions, we show that replacing these approximations with alternative variational formulas substantially improves both accuracy and stability at larger time steps, leading to up to an order-of-magnitude enhancement in the final success probability. We further derive rigorous error bounds that depend only on static properties of the Hamiltonian, providing practical guidance for selecting the simulation time step. Benchmarks on the transverse-field Ising model demonstrate faster convergence to the ground-state energy and improved robustness compared to standard TS--Taylor ITE, highlighting variational polynomial filtering as a practical route to higher-fidelity ground-state preparation on near-term quantum devices.

quant-pharXiv:2608.28357Aug 31, 20260 citations

Classical optimization with imaginary-time block encoding on quantum computers: The MaxCut problem

Dawei Zhong, Akhil Francis, Ermal Rrapaj

Optimization problems in finance, physics, and computer science are typically very hard to tackle in classical computing; quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat a problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. We develop a method, called imaginary-time evolution block encoding (ITE-BE), based on a recent imaginary-time algorithm, which requires no variational parameter optimization, as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as the quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the postselection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block-encoding scheme to allow for a deterministic application of the first layer of the circuit.

arXiv:2411.10737Physical Review ASep 3, 20252 citations

Probabilistic imaginary-time evolution via compiled diagonal representations

Hengyue Li, Huazhe Lou, Yang Li +5 more

We introduce a probabilistic imaginary-time evolution scheme based on a compiled approximate diagonal representation of the Hamiltonian. A basis transformation is optimized offline. For a fixed compiled representation, the online circuit structure and gate count per attempt are independent of the imaginary time, and the same representation can be reused across different input states and evolution times. We derive a condition for enhanced success probability. Numerical tests show reduced online cost relative to termwise Pauli-based methods at a common accuracy threshold. We also examine how approximation errors and offline preparation costs affect the overall benefit.

quant-pharXiv:2610.39600Oct 30, 20260 citations

A quantum double-bracket algorithm for imaginary-time evolution with exponentially shorter depth

Ioannis Kolotouros, Raul Garcia-Patron

Imaginary-time evolution (ITE) is a widely used technique for preparing the ground state of a target Hamiltonian. Building on the recently proposed framework of Double-Bracket quantum ITE (DB-QITE), we introduce a probabilistic variant (PDBQITE) that achieves an exponential reduction in circuit depth. Our algorithm requires only a single ancilla qubit and a quantum circuit that consists of one controlled real-time evolution and one mid-circuit measurement per iteration. The trade-off is an exponential decay of the total success probability with the number of iterations, for which we derive an analytical lower bound that is independent of system size. Our numerical simulations show that the per-step success probability remains close to unity, making it realistic to execute many iterations, thus providing a substantial improvement over prior constructions. We show that PDBQITE outperforms the near-term probabilistic algorithm PITE for ground-state preparation of molecular Hamiltonians, and that a hybrid QAOA-PDBQITE scheme achieves higher approximation ratios than QAOA at the same circuit depth on random regular graphs for the MaxCut problem.

quant-pharXiv:2609.37095Sep 30, 20260 citations