Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.12607 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution

Xin Lee, Hoong Chuin Lau

Published Aug 30, 2025• 1 citation
arXivHTMLPDF

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 groundstate 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 MaxCut. 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.

DOI
10.1109/qce65121.2025.00213

Related papers

An Adaptive Weighted Qite-Vqe Algorithm for Combinatorial Optimization Problems

Ningyi Xie, Xinwei Lee, Tiejin Chen +3 more

The variational quantum eigensolver (VQE) is an algorithm for finding the ground states of a given Hamiltonian. Its application to binary-formulated combinatorial optimization (CO) has been widely studied in recent years. However, typical VQE approaches for CO problems often suffer from local minima or barren plateaus, limiting their ability to achieve optimal solutions. The quantum imaginary time evolution (QITE) offers an alternative approach for effective ground-state preparation but requires large circuits to approximate non-unitary operations. Although compressed QITE (cQITE) reduces circuit depth, accumulated errors eventually cause energy increases. To address these challenges, we propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization. In numerical simulations for MaxCut on unweighted regular graphs, AWQV achieves near-optimal approximation ratios, while for weighted Erdős-Rényi instances, it outperforms the classical Goemans-Williamson algorithm.

arXiv:2504.10651•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Combinatorial optimization with quantum imaginary time evolution

Nora M. Bauer, Rizwanul Alam, George Siopsis +1 more

We use quantum imaginary-time evolution (QITE) to solve polynomial unconstrained binary optimization (PUBO) problems. We show that a linear ansatz yields good results for a wide range of PUBO problems, often outperforming standard classical methods, such as the Goemans-Williamson (GW) algorithm. We obtain numerical results for the low-autocorrelation binary sequences (LABS) and weighted MaxCut combinatorial optimization problems, thus extending an earlier demonstration of successful application of QITE on MaxCut for unweighted graphs. We find the performance of QITE on the LABS problem with a separable ansatz comparable to QAOA at level 10 for up to 18 vertices and do not see a significant advantage with an entangling ansatz. On weighted MaxCut, QITE with a separable ansatz often outperforms the GW algorithm on graphs with up to 150 vertices.

arXiv:2312.16664•Physical Review A•May 21, 2024•8 citations

Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems

Xiaoyang Wang, Yahui Chai, Xu Feng +3 more

Obtaining exact solutions to combinatorial optimization problems using classical computing is computationally expensive. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the Ansatz being of the utmost importance. It is known that popular approaches such as the quantum approximate optimization algorithm (QAOA) and quantum annealing suffer from adiabatic bottlenecks, which lead to either larger circuit depth or evolution time. On the other hand, the evolution time of imaginary-time evolution is bounded by the inverse energy gap of the Hamiltonian, which is constant for most noncritical physical systems. In this work we propose an imaginary Hamiltonian variational Ansatz ($i\mathrm{HVA}$) inspired by quantum imaginary-time evolution to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i\mathrm{HVA}$. For randomly generated $D$-regular graphs, we numerically demonstrate that the $i\mathrm{HVA}$ solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming the QAOA, which requires rounds increasing with the graph size. Furthermore, our Ansatz solves the MaxCut problem exactly for graphs with up to 24 nodes and $D\ensuremath{\le}5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm. We validate our simulated results with hardware demonstrations on a graph with 67 nodes.

arXiv:2408.09083•Physical Review A•Mar 18, 2025•4 citations

Quantum Optimization Algorithms for Industrial Problems

Maximilian Nikolaus Hess

The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.

•Jan 1, 2026•0 citations

Measurement-driven Quantum Approximate Optimization

Tobias Stollenwerk, Stuart Hadfield

Algorithms based on non-unitary evolution have attracted much interest for ground state preparation on quantum computers. One recently proposed method makes use of ancilla qubits and controlled unitary operators to implement weak measurements related to imaginary-time evolution. In this work we specialize and extend this approach to the setting of combinatorial optimization. We first generalize the algorithm from exact to approximate optimization, taking advantage of several properties unique to classical problems. In particular we show how to select parameters such that the success probability of each measurement step is bounded away from $1/2$. We then show how to adapt our paradigm to the setting of constrained optimization for a number of important classes of hard problem constraints. For this we compare and contrast both penalty-based and feasibility-preserving approaches, elucidating the significant advantages of the latter approach. Our approach is general and may be applied to easy-to-prepare initial states as a standalone algorithm, or deployed as a quantum postprocessing stage to improve performance of a given parameterized quantum circuit. We then propose a more sophisticated variant of our algorithm that adaptively applies a mixing operator or not, based on the measurement outcomes seen so far, as to speeds up the algorithm and helps the system evolution avoid slowing down or getting stuck suboptimally. In particular, we show that mixing operators from the quantum alternating operator ansatz can be imported directly, both for the necessary eigenstate scrambling operator and for initial state preparation, and discuss quantum resource tradeoffs.

quant-pharXiv:2512.21046•Physical Review A•Dec 25, 2025•0 citations

Variational Ansatz preparation to avoid CNOT-gates on noisy quantum devices for combinatorial optimizations

Tsukasa Miki, Ryo Okita, Moe Shimada +2 more

The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.

AIP Advances•Mar 1, 2022•16 citations
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 groundstate 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 MaxCut. 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.
The variational quantum eigensolver (VQE) is an algorithm for finding the ground states of a given Hamiltonian. Its application to binary-formulated combinatorial optimization (CO) has been widely studied in recent years. However, typical VQE approaches for CO problems often suffer from local minima or barren plateaus, limiting their ability to achieve optimal solutions. The quantum imaginary time evolution (QITE) offers an alternative approach for effective ground-state preparation but requires large circuits to approximate non-unitary operations. Although compressed QITE (cQITE) reduces circuit depth, accumulated errors eventually cause energy increases. To address these challenges, we propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization. In numerical simulations for MaxCut on unweighted regular graphs, AWQV achieves near-optimal approximation ratios, while for weighted Erdős-Rényi instances, it outperforms the classical Goemans-Williamson algorithm.
We use quantum imaginary-time evolution (QITE) to solve polynomial unconstrained binary optimization (PUBO) problems. We show that a linear ansatz yields good results for a wide range of PUBO problems, often outperforming standard classical methods, such as the Goemans-Williamson (GW) algorithm. We obtain numerical results for the low-autocorrelation binary sequences (LABS) and weighted MaxCut combinatorial optimization problems, thus extending an earlier demonstration of successful application of QITE on MaxCut for unweighted graphs. We find the performance of QITE on the LABS problem with a separable ansatz comparable to QAOA at level 10 for up to 18 vertices and do not see a significant advantage with an entangling ansatz. On weighted MaxCut, QITE with a separable ansatz often outperforms the GW algorithm on graphs with up to 150 vertices.
Obtaining exact solutions to combinatorial optimization problems using classical computing is computationally expensive. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the Ansatz being of the utmost importance. It is known that popular approaches such as the quantum approximate optimization algorithm (QAOA) and quantum annealing suffer from adiabatic bottlenecks, which lead to either larger circuit depth or evolution time. On the other hand, the evolution time of imaginary-time evolution is bounded by the inverse energy gap of the Hamiltonian, which is constant for most noncritical physical systems. In this work we propose an imaginary Hamiltonian variational Ansatz (iHVAi\mathrm{HVA}iHVA) inspired by quantum imaginary-time evolution to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round iHVAi\mathrm{HVA}iHVA. For randomly generated DDD-regular graphs, we numerically demonstrate that the iHVAi\mathrm{HVA}iHVA solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming the QAOA, which requires rounds increasing with the graph size. Furthermore, our Ansatz solves the MaxCut problem exactly for graphs with up to 24 nodes and $D\ensuremath{\le}5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm. We validate our simulated results with hardware demonstrations on a graph with 67 nodes.
The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.
Algorithms based on non-unitary evolution have attracted much interest for ground state preparation on quantum computers. One recently proposed method makes use of ancilla qubits and controlled unitary operators to implement weak measurements related to imaginary-time evolution. In this work we specialize and extend this approach to the setting of combinatorial optimization. We first generalize the algorithm from exact to approximate optimization, taking advantage of several properties unique to classical problems. In particular we show how to select parameters such that the success probability of each measurement step is bounded away from 1/21/21/2. We then show how to adapt our paradigm to the setting of constrained optimization for a number of important classes of hard problem constraints. For this we compare and contrast both penalty-based and feasibility-preserving approaches, elucidating the significant advantages of the latter approach. Our approach is general and may be applied to easy-to-prepare initial states as a standalone algorithm, or deployed as a quantum postprocessing stage to improve performance of a given parameterized quantum circuit. We then propose a more sophisticated variant of our algorithm that adaptively applies a mixing operator or not, based on the measurement outcomes seen so far, as to speeds up the algorithm and helps the system evolution avoid slowing down or getting stuck suboptimally. In particular, we show that mixing operators from the quantum alternating operator ansatz can be imported directly, both for the necessary eigenstate scrambling operator and for initial state preparation, and discuss quantum resource tradeoffs.
The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.