Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution

Xin Lee, Hoong Chuin Lau

TL;DR

This paper introduces a novel framework for solving the Multiple Knapsack Problem (MKP) using Variational Quantum Imaginary Time Evolution (VarQITE). By mapping the constrained problem to a Max-Cut instance and leveraging a specialized ansatz, the authors demonstrate that VarQITE significantly outperforms traditional variational algorithms like QAOA in finding near-optimal solutions.

What Problem Does This Paper Address?

Combinatorial Optimization Problems (COPs) are the bread and butter of logistics and resource allocation, but they are notoriously difficult (NP-hard) for classical computers. While Variational Quantum Algorithms (VQAs) like the Quantum Approximate Optimization Algorithm (QAOA) show promise, they face two major hurdles:

  1. Constraints: Most real-world problems have "hard" rules (e.g., you can't put 20kg of gear in a 10kg bag). Standard quantum methods often require "slack variables" that consume precious qubits or complex "mixer" circuits that are too deep for today’s noisy quantum hardware.
  2. The Optimization Landscape: VQAs typically use gradient-based optimizers to find the best parameters. Because quantum circuits are built from oscillatory gates (sines and cosines), the "landscape" they navigate is full of local minima and "barren plateaus" where the algorithm gets stuck or lost.

The authors aim to bypass these issues by using Imaginary Time Evolution, a concept borrowed from physics that naturally "cools" a system into its lowest energy state (the optimal solution).

Methods

The authors propose a multi-step framework called QITE+iHVA:

  • Unbalanced QUBO: Instead of adding extra "slack" qubits to handle inequality constraints, they use an "unbalanced penalization" method. This keeps the qubit count low while still steering the algorithm toward feasible solutions.
  • Mapping to Max-Cut: They convert the resulting Quadratic Unconstrained Binary Optimization (QUBO) problem into a Max-Cut instance. This allows them to use the imaginary Hamiltonian variational ansatz (iHVA), a circuit structure specifically tailored to the symmetries of Max-Cut problems.
  • VarQITE Optimization: Instead of standard gradient descent (VQE), they use the variational form of Quantum Imaginary Time Evolution. This follows McLachlan’s variational principle to update parameters, effectively tracing a path through the landscape that avoids the "traps" of local minima.
  • Hamiltonian Scaling: A key technical contribution is scaling the Hamiltonian coefficients by a factor ($1/d$). This allows the simulation to take larger "time steps," speeding up convergence without sacrificing accuracy.

Datasets

The researchers evaluated their framework on 68 instances of the Multiple Knapsack Problem (MKP).

  • Scale: The instances involved up to 3 knapsacks and 4 items.
  • Qubit Count: After mapping, the problems required between 10 and 13 qubits.
  • Comparison: They benchmarked their results against the Hardware Efficient Ansatz (HEA), multi-angle QAOA (ma-QAOA), and iHVA optimized via standard classical optimizers (VQE).

Key Insights and Ideas

  • VarQITE as a "Global" Navigator: The most significant insight is that VarQITE is much more robust than VQE. While VQE often gets trapped in sub-optimal local minima due to the non-convex nature of the landscape, VarQITE’s step-by-step evolution toward the ground state acts as a more reliable guide to the global optimum.
  • Ansatz Matters: Using the iHVA ansatz (which uses $R_{ZY}$ gates) provides the necessary expressivity to represent the imaginary-time-evolved state more accurately than generic hardware-efficient circuits.
  • The Scaling Trick: Scaling the Hamiltonian is not just a mathematical curiosity; it’s a practical necessity. It reduces the number of iterations (time steps) needed for the algorithm to converge, which is crucial for reducing the computational cost of the classical simulation.

Key Results

  • Superior Optimality: The "rescaled QITE+iHVA" method achieved a mean optimality gap of 0.31, drastically lower than the 4.46 gap seen with the same ansatz using standard VQE. This means the solutions were much closer to the true mathematical optimum.
  • High Feasibility: The framework maintained a high feasibility rate (median of 1.0), meaning it consistently found solutions that obeyed all the knapsack constraints.
  • Efficiency: By scaling the Hamiltonian by a factor of $d=10$, the authors reached the optimal solution in significantly fewer steps (e.g., 50 steps vs. 500 steps for the unscaled version).

Limitations and Future Work

  • Classical Overhead: While VarQITE is powerful, the classical part of the algorithm (solving systems of linear equations at every step) is computationally expensive to simulate as the number of qubits grows.
  • Problem Size: The study focused on small-scale instances (up to 13 qubits). The authors acknowledge that as problems scale, they will need even deeper circuits and more clever heuristics to determine the optimal scaling factor ($d$) for the Hamiltonian.
  • Hardware Implementation: This work was performed using state-vector simulators. Testing this on real, noisy quantum hardware (NISQ devices) remains a critical next step to see how the deep circuits required for VarQITE handle physical noise.

Summary updated

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.
BibTeX
@misc{lee2025solving,
  author = {Xin Lee and Hoong Chuin Lau},
  title = {{Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution}},
  year = {2025},
  eprint = {2504.12607},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.12607},
  howpublished = {arXiv},
}
Figure