A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering

The Quantum Alternating Operator Ansatz (QAOA) is a hybrid quantum-classical variational algorithm for approximately solving combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices. Although it has been successfully applied to a variety of problems, there is only limited work on correlation clustering due to the difficulty of modelling the problem constraints with the ansatz. Motivated by this, we present a generalization of QAOA that is more suitable for this problem. In particular, we modify QAOA in two ways: Firstly, we use nucleus sampling for the computation of the expected cost. Secondly, we split the problem into sub-problems, solving each individually with QAOA. We call this generalization the Sub-Problem Quantum Alternating Operator Ansatz (SQAOA) and show theoretically that optimal solutions for correlation clustering instances can be obtained with certainty when the depth of the ansatz tends to infinity. Further, we show experimentally that SQAOA achieves better approximation ratios than QAOA for correlation clustering, while using only one qubit per node of the respective problem instance and reducing the runtime (of simulations).

The Quantum Alternating Operator Ansatz (QAOA) combines classical and quantum computing to approximately solve combinatorial optimization problems. However, it is difficult to apply QAOA to the widely adopted problem of correlation clustering due to its complex constraints.Motivated by this, we present a generalization that can handle these constraints more effectively. We call this generalization the Sub-Problem Quantum Alternating Operator Ansatz (SQAOA). Two main ideas distinguish SQAOA from QAOA: First, a technique from LLMs called nucleus sampling is employed for training and interference. Second, the given problem is split into sub-problems.Using the correlation clustering problem as an example, we show that our approach retains a theoretical guarantee of optimality, requires only one qubit per element to cluster, and achieves better simulation results more efficiently than the best QAOA-based method currently known.