Quantum Algorithms Now Solve Complex Problems with Added Restrictions

David Bucher and colleagues at Delft University present a new approach to the Quantum Approximate Optimisation Algorithm (QAOA) that combines the benefits of constraint handling and informed search strategies. Their research introduces Iterative Warm-Starting (IWS) with XY-mixers, a technique that accelerates the process of finding solutions to combinatorial problems like Max-$k$-Cut and the Travelling Salesperson Problem. The method was validated on the ibm_boston quantum processing unit, successfully identifying optimal solutions even with hardware noise, representing a key step towards practical quantum optimisation.

Warm-started XY-mixer Hamiltonian enhances quantum optimisation on a 144-qubit processor

A 144-qubit quantum processor demonstrated a significant increase in the probability of sampling optimal solutions, exceeding standard XY-QAOA methods by orders of magnitude. The Quantum Approximate Optimisation Algorithm (QAOA) is a prominent hybrid quantum-classical algorithm designed for tackling combinatorial optimisation problems, which are ubiquitous in fields like logistics, finance, and machine learning. However, effectively incorporating hard constraints into QAOA has proven challenging, often leading to reduced performance and difficulty in finding feasible solutions. The new warm-started XY-mixer guarantees a stable starting point, enabling efficient searches and surpassing previous limitations regarding alignment of initial states with mixer Hamiltonians. The XY-mixer, a specific type of quantum mixer, operates by promoting transitions between states with differing Hamming weights, effectively exploring the solution space. Traditional XY-QAOA can struggle when the initial state is poorly aligned with the mixer’s dynamics, hindering its ability to efficiently converge towards optimal solutions.

IBM’s team formulated a specialised ‘warm-started XY-mixer’ Hamiltonian for one-hot constraints, proving its ground-state properties and allowing for shallow circuit implementation suitable for near-term quantum devices. One-hot constraints dictate that only one variable in a set can be active or ‘on’ at any given time, a common restriction in many optimisation problems. The warm-starting process involves biasing the initial quantum state towards promising regions of the solution space, informed by preliminary classical solutions. This is achieved by designing the XY-mixer Hamiltonian such that its ground state corresponds to a good initial guess for the optimisation problem. The resulting Hamiltonian allows for the construction of relatively shallow quantum circuits, circuits with a limited number of quantum gates, which are crucial for execution on current noisy intermediate-scale quantum (NISQ) devices. Shallower circuits are less susceptible to the accumulation of errors caused by decoherence and gate imperfections.

This technique, coupled with an Iterative Warm-Starting (IWS) classical heuristic, represents a sharp advance in tackling complex combinatorial optimisation problems, such as the Max-$k$-Cut and the Travelling Salesperson Problem. The Max-$k$-Cut problem involves partitioning the nodes of a graph into $k$ sets to maximise the number of edges crossing between the sets, while the Travelling Salesperson Problem seeks the shortest possible route that visits each city exactly once and returns to the origin. IBM’s team validated their approach on the ibm_boston QPU, utilising hardware-tailored 144-qubit instances, a substantial increase in scale compared to prior demonstrations of XY-mixer technology. A greedy steepest-descent post-processing strategy successfully repaired infeasible measurements stemming from hardware noise, allowing the team to identify optimal solutions in three of the five tested instances and achieve approximation ratios exceeding 99% for the remaining two. The post-processing step is essential for mitigating the effects of errors inherent in quantum measurements, ensuring that the reported solutions are valid and meaningful.

The success hinged on the development of a shallow circuit implementation, key for compatibility with current noisy intermediate-scale quantum (NISQ) devices, as the circuits required fewer quantum resources than previous methods. IWS dynamically adjusts the search bias based on prior samples, avoiding reliance on complex problem-specific classical solvers. In IWS, the classical heuristic iteratively refines the warm-starting parameters based on the outcomes of previous quantum computations, effectively learning the structure of the problem and guiding the search towards better solutions. While these results demonstrate a sharp advance in large-scale quantum optimisation, consistently identifying optimal solutions remains elusive, indicating a gap between current performance and the reliable solution of truly complex, real-world problems. Further research is needed to improve the robustness and scalability of the algorithm, and to explore its potential for tackling even more challenging optimisation tasks.

Efficiently solving one-hot constraints advances quantum optimisation algorithms

Scientists are devising increasingly sophisticated methods to use quantum computers for solving complex optimisation problems, important for fields ranging from logistics to materials science. The latest work introduces a refined approach to the Quantum Approximate Optimisation Algorithm, or QAOA, by embedding a ‘warm-start’ directly into the quantum mixer itself, a technique designed to focus the computer’s search for solutions. The motivation behind this approach is to overcome the limitations of traditional QAOA, which often requires extensive parameter tuning and can be sensitive to the choice of initial state. Currently, the team’s success is limited to ‘one-hot constraints’, a specific type of problem restriction, and extending this methodology to more general constraints presents a significant hurdle for future work. One-hot constraints, while simplifying the initial demonstration, serve as a valuable testbed for validating the core principles of the warm-started XY-mixer approach.

These constraints represent a common building block in larger, more complex optimisation challenges, and successfully tackling them efficiently is a vital step forward, paving the way for addressing more intricate scenarios. For example, resource allocation problems, scheduling tasks, and portfolio optimisation often involve one-hot constraints as a means of ensuring mutually exclusive choices. The method offers a new way to guide the computer’s search, potentially accelerating solutions across a wider range of applications, and differs from prior approaches that struggled to maintain performance when combining initial state biasing with mixer design. Previous attempts to combine warm-starting with XY-mixers often suffered from instability or reduced performance due to the conflicting effects of the bias and the mixer dynamics. This work establishes a new approach to quantum optimisation by directly embedding a search bias into the quantum mixer itself. Successfully demonstrated for one-hot constraints, a common component of more complex problems, the resulting Iterative Warm-Starting QAOA significantly accelerates the identification of optimal solutions compared to standard methods, as validated on a 144-qubit quantum processor. The integration of the warm-start into the mixer Hamiltonian allows for a more coherent and efficient exploration of the solution space, leading to improved performance and scalability.

The researchers successfully developed a new method, Iterative Warm-Starting QAOA, which speeds up the process of finding optimal solutions to complex optimisation problems. This approach combines a technique to limit the quantum computer’s search space with a method for biasing the search towards promising solutions, maintaining performance where previous attempts failed. Numerical simulations on instances of Max-$k$-Cut and the Traveling Salesperson Problem demonstrated that this new method increases the probability of finding optimal solutions significantly. The authors note that future work will focus on extending this methodology beyond one-hot constraints, a specific type of problem restriction.