Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
Jordi R. Weggemans, Alexander Urech, Alexander Rausch, R. J. C. Spreeuw, Richard J. Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, Florian Speelman
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for 87Sr and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of 0.6367 ( 0.6699 ) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's performance by considering complete and Erdős-Rényi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound 0.7666 for the approximation ratio for QAOA depths p≥2 . Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for 87Sr and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of 0.6367 ( 0.6699 ) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's performance by considering complete and Erdős-Rényi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound 0.7666 for the approximation ratio for QAOA depths p≥2 . Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.
The quantum approximation optimisation algorithm (QAOA) is one of the leading
candidates for testing the applicability of gate-model quantum resources at solving
optimisation problems on small-sized quantum hardware. A combinatorial problem that
has been understudied with QAOA is correlation clustering: given a weighted (+1,-1)
graph, where the edge weights indicate whether two nodes are similar (positive edge
weight) or different (negative edge weight), the task in correlation clustering is to find a
clustering that either maximises agreements, minimises disagreements or a combination
of both. In this thesis, we design Hamiltonian formulations that encode correlation
clustering problems such that they can be solved with QAOA. For all Hamiltonian
formulations we propose circuit implementations and study their complexities. To
benchmark the performances of a basic QAOA algorithm using these formulations, we
use numerical simulations on complete graph data sets. For one of the formulations,
which uses a multi-level approach naturally suitable to qudit systems, we investigate
the performances of several optimisers and introduce heuristic strategies to further
improve its performance. On all instances in our data-sets, which include complete as
well as Erdős–Renyi graphs, the improved algorithm shows competitive performances
for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists
such that it has a performance guarantee of 0.670 on 3-regular graphs.
The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics
A frequent starting point of quantum computation platforms is the two-state quantum system, i.e., the qubit. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these in a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a maximum-k-graph-coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
Quantum computing promises solutions to classically difficult and new-found problems through controlling the subtleties of quantum computing. The Quantum Approximate Optimisation Algorithm (QAOA) is a recently proposed quantum algorithm designed to tackle difficult combinatorial optimisation problems utilising both quantum and classical computation. The hybrid nature, generality and typically low gate-depth make it a strong candidate for near-term implementation in quantum computing. Finding the practical limits of the algorithm is currently an open problem. Until now, no tools to facilitate the design and validation of probabilistic quantum optimisation algorithms such as the QAOA on a non-trivial scale exist. Graph similarity is a long standing classically difficult problem withstanding decades of research from academia and industry. Determining the maximal edge overlap between all possible node label permutations is an NP-Complete task and provides an apt measure of graph similarity. We introduce a novel quantum optimisation simulation package facilitating investigation of all constituent components of the QAOA from desktop to cluster scale using graph similarity as an example. Our simulation provides flexibility and performance. We investigate eight classical optimisation methods each at six levels of decomposition. Moreover an encoding for permutation based problems such as graph similarity through edge overlap to the QAOA allows for significant quantum memory savings at the cost of additional operations. This compromise extends into the classical portion of the algorithm as the inclusion of infeasible solutions creates a challenging cost-function landscape. We present performance analysis of our simulation and of the QAOA setting a precedent for investigating and validating numerous other difficult problems to the QAOA as we move towards realising practical quantum computation.
The Quantum Approximate Optimization Algorithm (QAOA) -- one of the leading algorithms for applications on intermediate-scale quantum processors -- is designed to provide approximate solutions to combinatorial optimization problems with shallow quantum circuits. Here, we study QAOA implementations with cat qubits, using coherent states with opposite amplitudes. The dominant noise mechanism, i.e., photon losses, results in Z-biased noise with this encoding. We consider in particular an implementation with Kerr resonators. We numerically simulate solving MaxCut problems using QAOA with cat qubits by simulating the required gates sequence acting on the Kerr non-linear resonators, and compare to the case of standard qubits, encoded in ideal two-level systems, in the presence of single-photon loss. Our results show that running QAOA with cat qubits increases the approximation ratio for random instances of MaxCut with respect to qubits encoded into two-level systems.