Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution
LEE Xin Wei, LAU Hoong Chuin · 2025
Read Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution by LEE Xin Wei, LAU Hoong Chuin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12607.txt.
Introduction
Xin Wei Lee and Hoong Chuin Lau try a quantum method on a packing problem in a 2025 paper. Packing problems, like loading several knapsacks under weight limits, are easy to state and hard to solve. Quantum algorithms promise relief, but the leading one needs deep, costly circuits for such constrained tasks.
The authors instead use a variational form of quantum imaginary time evolution, a method that cools a quantum state toward its lowest energy, which encodes the best packing. They borrow a circuit shape proven on graph cuts. The work is presented as the first attempt at this problem with this method. The authors weigh its chances against the known flaws of rival quantum approaches.
Catalog record
| CREATOR | LEE Xin Wei, LAU Hoong Chuin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12607
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution LEE Xin Wei, LAU Hoong Chuin Abstract Solving combinatorial optimization problems using variational quantum algorithms (VQAs) has emerged as a promising research direction. Since the introduction of the Quantum Approximate Optimization Algorithm (QAOA), numerous variants have been proposed to enhance its performance. QAOA was later extended to the Quantum Alternating Operator Ansatz (QAOA+), which generalizes the initial state, phase-separation operator, and mixer to address constrained problems without relying on the standard Quadratic Unconstrained Binary Optimization (QUBO) formulation. However, QAOA+ often requires additional ancilla qubits and a large number of multi-controlled Toffoli gates to prepare the superposition of feasible states, resulting in deep circuits that are challenging for near-term quantum devices. Furthermore, VQAs are generally hindered by issues such as barren plateaus and suboptimal local minima. Recently, Quantum Imaginary Time Evolution (QITE), a ground-state preparation algorithm, has been explored as an alternative to QAOA and its variants. QITE has demonstrated improved performance in quantum chemistry problems and has been applied to unconstrained combinatorial problems such as Max-Cut. In this work, we apply the variational form of QITE (VarQITE) to solve the Multiple Knapsack Problem (MKP), a constrained problem, using a Max-Cut-tailored ansatz. To the best of our knowledge, this is the first attempt to address constrained optimization using VarQITE. We show that VarQITE achieves significantly lower mean optimality gaps compared to QAOA and other conventional methods. Moreover, we demonstrate that scaling the Hamiltonian coefficients can further reduce optimization costs and accelerate convergence. I Introduction Combinatorial optimization problems (COP) are always of utmost interest among the mathematical optimization community, as most of the COPs are NP-hard to solve using a classical computer. Variational quantum algorithms (VQA) have emerged as promising tools for solving COPs since the introduction of the Quantum Approximate Optimization Algorithm (QAOA) by Farhi et al. [ 1 ] Intensive studies have been conducted showing the advantage of solving the infamous Max-Cut problem (the problem that divides the graph into two partitions such that the number of edges between them is maximized) using QAOA. Some of them showed that QAOA (or its variants) outperforms the Goemans-Williamson algorithm, the best known classical heuristic for Max-Cut, in terms of the approximation ratio [ 2 ] . However, QAOA for constrained problems is not as straightforward as solving Max-Cut, which is an unconstrained problem. For constrained problems, there are other aspects to consider, e.g. the feasibility of the solution, instead of just the approximation ratio. To tackle constrained problems, QAOA was extended to the Quantum Alternating Operator Ansatz (QAOA+) [ 3 ] . QAOA+ allows customized initial states and mixer Hamiltonians that confine the state evolution within the feasible subspace, avoiding the need for a penalty QUBO formulation. However, QAOA+ also has its own drawbacks, mainly in the difficulty in creating the superposition of feasible states, and also the complicated construction of mixers to restrict the transition of the feasible states. These usually result in deep and large circuits that are impractical for noisy quantum devices [ 4 , 5 , 6 , 7 ] . On the other hand, expressive ansatz circuits like the hardware-efficient ansatz (HEA) [ 8 ] , multi-angle QAOA (ma-QAOA) [ 9 ] , and expressive QAOA (XQAOA) [ 2 ] can also be used to solve Max-Cut and beyond. However, the expressivity of the ansatz is also strongly tied to the existence of barren plateaus in the optimization landscape [ 10 , 11 , 12 ] . Barren plateau is a phenomenon that commonly and inherently occurs in deep and expressive quantum circuits, where the gradients in a particular region of the landscape are near to zero. As the problem size scales up, it will be more difficult to get a good solution using expressive ansatzes, along with more occurrences of local (sub-optimal) minima. Having many local minima is also another problem that haunts the optimization of VQA. Due to the oscillatory nature of parameterized unitary gates (consists of sines and cosines), minimization of the Hamiltonian expectation using gradient-based methods is bound to be non-convex. Therefore, heuristics are proposed to determine good parameter initializations, especially for QAOA which exhibits certain patterns in parameters [ 13 , 14 , 15 , 16 , 17 , 18 ] . Other efforts made to improve the quality of the solution for constrained COPs include tampering with the formulation of the problem [ 19 ] , using different ansatz circuits [ 20 , 21 ] , different optimization heuristics [ 22 , 23 ] , etc. Recently, Quantum Imaginary Time Evolution (QITE) has been explored as a possibility to improve performance in solving constrained COPs. In contrast with the quantum time evolution which is used to simulate the evolution of a given Hamiltonian with time, QITE is used to evolve the system such that it converges to the ground state of the given Hamiltonian. The main challenge of QITE lies in the implementation of the non-unitary imaginary time operator e^{-\tau\hat{H}} in a gate-based quantum computer that only allows unitary quantum gates for state evolution. Macroscopically, there are two main paradigms for implementing QITE: 1) the non-variational QITE [ 24 ] that breaks e^{-\tau\hat{H}} into fragments using Trotterization to mimic the imaginary time evolution for each small step \Delta\tau , and 2) the variational QITE (VarQITE) [ 25 ] that utilizes the McLachlan variational principle to update the parameters in the ansatz circuit [ 26 ] . In general, non-variational QITE requires exponentially many gates to be implemented, which is not NISQ-friendly [ 27 ] . Therefore, we will focus on the variational QITE. There are several works on solving COPs using the non-variational QITE framework. Alam et al. proposed a linear ansatz, which essentially contains only single-qubit rotational- Y gates, to solve the Max-Cut problem using QITE [ 28 ] . Due to the lack of entangling gates in the ansatz circuit, it can be efficiently simulated on a classical computer. They solved Max-Cut of up to 50 nodes and obtained an average approximation ratio of 0.89 with QITE on linear ansatz. By applying optimization tricks, the average approximation ratio is increased to 0.97. However, the authors did not compare their method with competitive methods, such as QAOA or the Goemans-Williamson (GW) algorithm for Max-Cut. Instead, they compare their results with the classical greedy algorithm. Bauer et al. extended the previous work to solve the Low Autocorrelation Binary Sequence (LABS) problem using QITE with linear ansatz [ 29 ] . The LABS problem is an unconstrained, higher-order problem compared to Max-Cut. First, the authors compared QITE and the classical GW in solving weighted Max-Cut for up to 150 qubits. In some of the cases, QITE shows better approximation ratios than GW, but GW still outperforms QITE on average. For LABS, the authors solved the problems up to 28 qubits, the results for QITE are on a par with that for QAOA with depth-10. On the other hand, Wang et al. recently proposed the imaginary Hamiltonian variational ansatz (iHVA) to solve the Max-Cut problem [ 30 , 31 ] . This ansatz is inspired by QITE, and is designed based on the bit-flip symmetry of the Max-Cut problem (if b is