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.
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.
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.
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.
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 (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 iHVA. For randomly generated D-regular graphs, we numerically demonstrate that the 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.
Approximate combinatorial optimization is a promising use case for quantum computers. The quantum optimization algorithms often employ a fixed ansatz that evolves an unbiased initial state towards states with better values of the optimand, then samples the states to determine an approximately optimal solution. However, promising alternative approaches have considered ``warm-start" and sampling-based methods that instead begin from the best known solution, which can be directly optimized with the quantum computer and updated as new information becomes available, potentially outperforming the fixed ansätze. Here we use these ideas to design a nonvariational quantum algorithm for combinatorial optimization. At each step the algorithm begins with a state superposed around the best known solution, then drives it to lower energy using quantum imaginary time evolution. These nonvariational, initial-state-dependent circuits are determined using analytic equations that are evaluated using only a conventional computer. After implementing the circuits, the state is sampled, potentially obtaining a new best-known solution to use as the initial state at the next iteration. Using simulations of the algorithm solving MaxCut on 3-regular graphs with 30 or fewer vertices and a shot budget of 100 total shots, the approach obtains median solutions within 95\% of the global optimum and finds optimal solutions in 11\% or more of cases, significantly outperforming random and simplified classical search procedures. We discuss several future directions.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
Abstract Advances in quantum computing with applications in combinatorial optimization have evolved at an increasing rate in recent years. The quadratic unconstrained binary optimization (QUBO) model is at the center of these developments and has become recognized as an effective alternative method for representing a wide variety of combinatorial optimization problems. Additional momentum has resulted from the arrival of quantum computers and their ability to solve the Ising spin glass problem, another form of the QUBO model. This paper highlights advances in solving QUBO models and extensions to more general polynomial unconstrained binary optimization (PUBO) models as important alternatives to traditional approaches. Computational experience is provided that compares the performance of unique quantum‐inspired metaheuristic solvers—the Next Generation Quantum (NGQ) solver for QUBO models and the NGQ‐PUBO solver for PUBO models—with the performance of CPLEX and the Dwave quantum advantage solver. Extensive results, including experiments with a set of large set partitioning problems representing the largest QUBO models reported in the literature to date, along with maximum diversity and max cut problem sets, disclose that our solvers outperform both CPLEX and Dwave by a wide margin in terms of both computational time and solution quality.