A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Authors: Lucas Fabian Naumann
Jannik Irmai
Bjoern Andres
Venue: ICML 2025 poster (2025)
Keywords: Quantum Computing
QAOA
Correlation Clustering
Primary area: optimization->everything_else
TL;DR: A generalization of the Quanutm Alternating Operator Ansatz suitable for correlation clustering.

Abstract: 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).

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Lucas Fabian Naumann
Jannik Irmai! Bjoern Andres
12
Abstract
computers, as these are limited both by their number of qubits and the number of operations that can be performed on a qubit before its state is too corrupted by noise (circuit depth). These current quantum computers are also referred to as Noisy Intermediate- Quantum (NISQ) devices (Preskill, 2018).
The Quantum Alternatnn Operator Ansatz (QAOA) a hybrid quantum-classical variational algorithm for approximately solving combinato- rial optimization problems on Noisy Intermediate- Scale Quantum (NISQ) devices. Although it has been successfully applied to variety of problems, there is only limited work on correlation cluster- ing 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 mod- ify 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 Al- ternating Operator Ansatz (SQAOA) and show theoretically that optimal solutions to correlation clustering instances can be obtained with certainty when the depth of the ansatz tends infinity. Further, show experimentally that SQAOA achieves better approximation ratios than QAOA for correlation clustering, while using only one qubit per node the respective problem instance and reducing the runtime (of simulations).
Variational quantum algorithms (Cerezo al., 2021) have emerged as promising paradigm to achieve quantum supremacy for practical problems on NISQ devices. These algorithms combine quantum and classical computing by using parameterized quantum circuits with few qubits and low depth, whose parameters are learned in a classical opti- mization loop. The Quantum Alternating Operator Ansatz (QAOA) (Hadfield al., 2019) is such variational algo- rithm designed for approximately solving combinatorial optimization problems. In particular, it alternately applies parameterized phase-separation operator, which changes the phase of states depending on their cost, and a mixing operator, which enables transitions between states and thus constructive or destructive interference based on their phase difference. The number of times p these operators are ap- plied alternately is called the ansatz depth. For co, and under the conditions given by Binkowski et al. (2024), there exist parameters for each problem instance such that QAOA returns an optimal solution with certainty. QAOA has been applied to a variety of problems (Cook et al., 2020; Saleem, 2020; Tabi et al., 2020; Fuchs et al., 2021), including cor- relation clustering (Weggemans, 2020; Weggemans et al., 2022).
1. Introduction
The term "quantum supremacy" (Preskill, 2012) refers to the ability of quantum computers to perform tasks efficiently that classical computers cannot. From a theoretical point of view, algorithms achieving this supremacy for problems of practical interest have long been established. However, applying these algorithms to problem instances of classi- cally intractable sizes is not possible on current quantum
Correlation clustering (Bansal et al., 2004) is special clus- tering formulation in which objects are represented by the nodes of graph, (dis-)similaritiee between them by edges with corresponding costs, and the goal to cluster the nodes of the graph such that cost function is optimized. In promi- nent difference to other formulations, the number of clusters is not fixed in advance, but learned from the data. This unsupervised clustering of objects based solely on pairwise ddiilasimilarities finds application in various domains, such as computational biology (D haeseleer, 2005; Erola et al., 2020), data analysis (Benjelloun et al., 2009; Abbas & Swo- boda, 2023) and image segmentation (Yarkony et al., 2012: Beier et al., 2015; Keuper et al., 2015).
'Faully of Computer Science, TU Dresden "Center for Scal- able Data Analyties and AI, Dresden/Lcipzig. Correspondence to: Bjoem Andres abjoerm.nndres @tu www.duudddddddd........
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
There are different variants of correlation clustering with respect to the associated costs and the cost. function. In this article, we consider unweighted ((+1--1) costs) max- imum agreement correlation clustering and will assume that, unless otherwise specified, the term "correlation clustering" refers to this variant. However, our approach can easily be adapted to weighted correlation clustering and other cost functions.
is associated with qudit and the cluster of that element is
given by the state of the qudit. We will use this formulation as reference to benchmark SQAOA against. Using tech- niques from Farhi et al. (2014) and Wurtz & Love (2021), 1), it is further shown for this multi-level QAOA formulation (including looping over the cluster number) that, for p = 1, there exist parameters achieving an approximation ratio of at least 0.6367 on all 3-regular graphs. Weggemans et al. (2022) build on this work by extending the evaluation of the multi-level formulation and describing how to realize it on Rydberg system. However, the described implementation is restricted to 4-1evel qudits, i.c., qudits with four states, such that only solutions involving at most 4 clusters can be considered.
We introduce the Sub- hab-Problem Quantum Alternating Opera- tor Ansatz (SQAOA), a generalization of QAOA motivated by the application to correlation clustering and based on the idea of nucleus sampling (Holtzman et al., 2020) and the concept of splitting a problem into several dependent sub- problems. For a specific SQAOA formulation of correlation clustering we show that:
There is variety of generalizations and variations of QAOA; recent survey is by Blekos et al. (2024). However, to our knowledge, there exists no work on using different sampling strategies to compute the expected cost. And although there are approaches that apply QAOA to sub- problems (Tomesh et al., 2022; Esposito & Danzig, 2024), these split problem instance into smaller instances of the same problem that are solved independently, In contrast, we solve instances of dependent sub-problems that are different from the original problem.
For each instance, there exist parameters such that an optimal solution obtained with certainty for p + oo.
Only many qubits are required to solve an instance as there are elements to cluster.
It experimentally outperforms existing approaches in terms of approximation ratios and runtimes on com- plete and Frrdös-Rény graphs with up to 10 nodes.
2. Related Work
3. Preliminaries
Unweighted maximum agreement correlation clustering on general graphs is known to be APX-hard. In particular, it is NP-hard for every > 0 to approximate the problem within a factor of 80/79- - (Tan, 2008). The best known clas- sical algorithm for approximating unweighted maximum agreement correlation clustering is given by Swamy (2004) and achieves approximation ratio of 0.7666 (Swamy bound). However, there exists polynomial time approxi- mation scheme when restricting the considered graphs to be complete (Bansal et al., 2004).
We begin this section with brief review of the notation and the fundamentals of quantum computing to the extent neces- sary for understanding the article. A thorough introduction can be found, e.g., in Nielsen & Chuang (2010). We then formally describe the Quantum Alternating Operator Ansatz and the correlation clustering problem before introducing our SQAOA formulation for correlation clustering in the next section.
Notation and Fundamentals of Quantum Computing We use the Dirac notation, i.e., we denote elements of C" by I-), their conjugate transpose by (-l and write (æly) := (xl (y) |x) (y) for the inner product of (x)). lv) E C".
The only other work applying QAOA to a correlation cluster- ing variant is by Weggemans (2020) and Weggemans al. (2022). Weggemans (2020) reviews different QAOA formu- lations for correlation clustering with respect to the number of used qubits, circuit complexities and approximation ra- tios obtained by simulations. Furthermore, improvement strategies for the standard QAOA algorithm are evaluated, like the choice of the classical optimizer, the choice of initial parameters and the number of restarts. Most importantly, is found that the achieved approximation ratios can be significantly increased by looping over the cluster number, i.e. by applying QAOA repeatedly, varying the number of allowed clusters from 1 to the number of nodes in the graph and returning only the best result.
We denote the standard unit vectors of C2 by
10) ! and
0
[1) = i
Consequently, the standard unit vectors of C are given by
X f C2
(x))
where
|x) E (101), (1))
for which we introduce the abbreviation
From these studies, a "multi-level" formulation emerges as the best approach, in which each element to be clustered
(x) where x E (0,1)*'
2

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
The state of an n-qubit system is given by normalized vector (statevector) in the Hilbert space C² which can be written
where
C2,
j=1
[s} is an initial state in the feasible space S, which is given by the set of all superpositions of classically feasible states, i.c. by
(1b) = Σ az (x) with ||0) =
Σ =E{0,1}"
ag =
xE{0,1)"
When measuring such a system (with respect to the compu- tational basis), collapses to one of the computational basis states (z)) The coefficients a, are called probability ampli- tudes and their squared absolutes |aæl" give the probability of collapsing into state (zz).
Σ Xo (o)
EMP=
Uc(1) = = -it is phase-separation operator such
that
In gase- quantum computing, algorithms are realized by manipulating qubits with quantum gates. Quantum gates acting on n qubits can be represented by unitary matrices of size 2". Another way of characterizing quantum gates is by Hermitian matrices. For any unitary matrix U, there exists Hermitian matrix Hl such that U e-iH and vice versa. In the remainder of this article, we will assume that matrices denoted by U are unitary and that matrices denoted by H are Hermitian. An overview of the gates used in this article is given in Appendix A. We use the following notation for applying a unitary U operating on a single qubit to the j-th qubit of an n-qubit system:
Hc (z) C(x) (z)
(2)
and He is called cost Hamiltonian;
UM((3 = e BH is mixing operator that preserves
feasible states
VI E S4B E R:
(x)
(3)
and allows for full mixing of solutions
Va, y E S 33 E R N:
(3)
(4)
U=: (0==(1)) S
81). k=j+1
X
The parameters 3,, y are learned in a classical optimization loop such that the expectation value of the cost function is minimized
Quantum states differ from probability distributions as their probability amplitudes can take complex values. This means that, in addition to their absolute value, quantum states have a phase. This fact enables constructive and destructive interference between them, i.e., applying an operation a quantum state different from just applying all of its basis states separately.
(B, o0DA He |3, 7) 000A
The intuition behind this ansatz is that the phase-separation operator modifies the phase of basis states (which corre- spond to feasible solutions) depending on their cost, while the mixing operator realizes transitions between feasible states, resulting in constructive and destructive interference. Since the parameters of the operators respect to the expectation value of the cost function, states with low cost are amplified by constructive interference, while states with high cost are erased by destructive inter- ference.
Quantum Alternating Operator Ansatz The Quantum Alternating Operator Ansatz (QADA) (Hadfield et al., 2019) a variational algorithm for approximately solving combi- natorial optimization problems. generalizes the Quantum Approximate Optimization Algorithm (Farhi al., 2014) which is, on the other hand, translation of the Quantum Adiabatic Algorithm (Farhi et al., 2001) from adiabatic quan- tum computing to gate-based quantum computing.
optimized with
In order to apply QAOA a specific problem, the operators and the initial state need to be defined and implemented. The main challenge lies in constructing the initial state and the mixing operator. Conversely, the phase-separation operator is easy to construct. If the problem is formulated as an integer program with binary variables, it is sufficient to choose the cost Hamiltonian Hc such that variables x; in the cost function C(x) are replaced by the term (1-22) This
generic combinatorial optimization problem size n with feasible space S C {0, 13" and cost function C' + IR can be written as
min C(x)
FES
2
Applying QAOA of depth for solving this problem, we first compute
due the fact that if x; 0, then (1-2,) (xx) = 0 (222), and
if x; = 1, then (1-Z,) (m,) = 1 |.,). Thus, (2) is fulfilled for the Hamiltonian constructed in this way. Implementing the corresponding unitary operator only requires the application of RZ. gates to individual qubits.
||8, 7) QAOA
(II
(I(())UUC(s) (1)
3

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
QAOA is considered promising variational quantum algo- rithm for the following reasons:
For p + oc and under the conditions given in (Binkowski et al., 2024), there exist parameters for each problem instance such that an optimal solution is obtained with certainty.
Under reasonable complexity theoretic conjectures, it is not possible efficiently sample from the gener- ated distributions classically, even for (Farhi & Harrow, 2019).
Figure 1. Depicted above is example of instance of the weighted maximum agreement correlation clustering problem, along with corresponding optimal solution. The problem in- stance is given by the graph and the costs written along its edges. The clustering indicated by the coloring of the nodes has agrec- ments and is optimal.
The parameters are concentrated for different instances of the same problem (Brandao et al., 2018; Akshay et al., 2021), allowing us to learn them for one instance and reuse them, or use them an initial point for others.
In this formulation, the variable assignment Ta,1 = 1 and Tv.2 = 1 for nodes u and v indicates that node u in Cluster and that node is in Cluster 2. Thus, the nodes are in different clusters. In this case, a value of is contributed to the cost if and only if Cur -1
The approximation ratios are expected to increase with larger ansatz depth p and are guaranteed to improve with optimal parameters. However, the depth limited for two reasons. Firstly, the number of applied operators increases, resulting in problems with computational resources for the simulation classical computers and the introduction of noise for the execution on quantum computers. Secondly, the number of learnable parameters increases with p, and gradients cannot be easily computed on quantum computers.
Note that when using QAOA for maximum agreement cor- relation clustering, we need to take the negative of the above cost function, since the expected cost (5) is minimized.
4. Sub-Problem Quantum Alternating Operator Ansatz
In this section, we introduce the Sub-Problem Quantum Al- ternating Operator Ansatz, a generalization of QAOA that, as we will show in Section 5, leads to better results when solving the correlation clustering problem regarding both the approximation ratio and the used resources while main- taining the optimality guarantee for -> xx. In comparison to QAOA, we make two significant changes: Firstly, we employ nucleus sampling (Holtzman et al., 2020) for the computation of the expected cost. Secondly, we alter the ansatz itself by splitting the problem into sub-problems and applying QAOA to each of them.
Correlation Clustering Let G = (V, E) be undirected graph, let n |V] be the number of nodes in G and let CE {+1,-1} be costs associated with the edges of the graph. The problem of unweighted maximum agreement correlation clustering consists in finding a clustering (or partition) of the node set V such that the number of pairs of nodes connected by edges with cost +1 that are in the same cluster, and the number of pairs of nodes connected by edges with cost 1 that are in different clusters, is maximized. Figure shows example of problem instance.
We can formulate unweighted maximum agreement corre- lation clustering as an integer quadratic program in which binary variables & E {0, 1) nxn indicate a node v is as- signed to cluster i, Z.ya = 1, or not, Zezy =0:
Nucleus Sampling As is typical for variational algorithms, QAOA minimizes the expectation value of the classical cost function, which is represented by a cost Hamiltonian (5). Since the expectation value acts as an upper bound on the ground state energy, i.e., the optimal cost, this minimization approximates ground states of the cost Hamiltonian, and thus optimal solutions.
Σ
Σ
max
Tu,i Teis +
B cvn=1 1 seK
Σ
(6)
E: Cun 1-1 KJEK: H*
The upper diagram of Figure shows the agreements of the basis states of the multi-level QAOA formulation of Weggemans et al. (2022) with 1 for a correlation clus- tering problem instance and the corresponding probabilities of these basis states. As expected, the algorithm shifts prob- ability mass solutions of low cost (i.e., high agreement).
subject to
Σ
Lu.i 1 for all u V,
kEK
where K = (1,.... n and we use ue, vu for denoting an
edge {u, w) F.

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
to rescale the remaining states accordingly, i.e., we set (E/") such that
0.06
0.05
Agrements
3-
0.04
Probability
(x (x
(1r ()) / if E X(1)
0.03
0
otherwise
0.02
For the case 1, it holds 1 specializes regular sampling. Moreover, since ( is also normalized quantum state, the obtained cost function still acts as an upper bound on the ground state energy.
= l and our approach
0.01
0.00
0.06
The lower diagram of Figure 2 shows the probabilities ob- tained when using multi-level QAOA with nucleus sampling and a threshold of / = 0.5 for training parameters and infer- ence. Clearly, reducing the threshold from 1 leads to better solutions.
4-
0.05
Agreenents
Probabilits
3
0.04
0.03
0.02
0.01
Sub-Problems Instead of solving the whole correlation clustering problem at once by applying QAOA (1), we split it into I sub-problems, solving each with QAOA, and intro- duce transition operators Ur, for i E (1....,1] preparing their initial state:
0.00
States
Figure 2. Depicted are two diagrams showing the probahility of measuring basis states when applying the multi-level QAOA for- mulation Weggemans et al. (2022) with p to the correlation clustering problem instance given in Figure 1. Shown in addition are the agreements these basis states, i.e., the value of the cost function in (6). The probabilities of the diagram at the top are obtained directly from the QAOA results. The probabilities of the diagram at the bottom obtained by nucleus sampling with threshold of = 0.5.
P (B,)) 10)
|8, SQA0A
1=1
Clearly, for / 1, UT, 10) - [s) and operators UM, Uc, satisfying properties (2-4), this specializes to QAOA, so we are again considering a proper generalization.
However, solutions of high cost are not completely erased and, due to their number, increase the expectation value sig- nificantly. The problem of this "unreliable tail" also occurs in decoding strategies for large language models and was approached by Holtzman et al. (2020) using technique called nucleus sampling (sometimes called top-p sampling).
In order apply this ansatz to an instance of the (un- weighted maximum agreement) correlation clustering prob- lem given by an undirected graph G = (V, E)) with n = [V] nodes and costs c E (+1,-1) E we need to choose the number of sub-problens I and the corresponding operators appropriately. We do so by modelling correlation clustering as an iterated application of max-cut. In each of = n 1 iterations, we solve a max-cut problem restricted to those nodes that have not been assigned to a cluster in a previous iteration. The nodes that are labeled 0 by the solution to the max-cut problem are assigned to a new cluster. The nodes labeled 1 remain unassigned (or are assigned cluster if it is the last iteration).
The main idea of nucleus sampling is that, instead of sam- pling directly from a given probability distribution, we sam- ple from the most probable states whose cumulative proba- bility surpasses a previously defined threshold. The set of those states is called the nucleus. Hence, in our case, we do not compute the expected cost with respect to the n-qubit state (e5) obtained from the quantum algorithm, but with respect to (ı²") obtained in the following way. Firstly, we set a threshold E (0, 1] and compute nucleus, i.e., a smallest set (1) C {0, 13" such that
"final"
Realizing this directly within the framework of (7) is pos- sible but requires complicated operators and, since at least one qubit per node needed for the decision in each sub- problem, 2(n²) qubits which worse than the approaches presented by Weggemans (2020) and Weggemans al. (2022). However, since the qubits associated with sub- problem are only manipulated by its operators, there is no interference between states that differ in one of those qubits once the sub-problem is processed. Consequently, we can measure all qubits of a sub- sub-problem after applying its op- erators and evaluate the following sub-problem only on
Σ (0)
(x (x|n))2
Secondly, we set the probability amplitudes of the basis states not in (t) to zero and use
Σ Ko| 2 OEX
5

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
the classical probability distribution estimated from these measurements instead of further performing operations the whole quantum system. This fact allows for more efficient implementation described in the following and in more detail in Algorithm 1.
M
UM
U Ma
Ma
We choose = n - 1. For any sub-problem E (I,...,'} and any solution (z) of the previous sub-pr boob-prollm, we com- pute
[ (B. Un (0) Figure 3. Depicted is are basis state of the multi-level QAOA for- mulation of Weggemans et al. (2022) (left) and SQAOA (right) correpoonding to the same solution of a correlation clustering prob- lem instance with four nodes. In the presented solution, the first node is assigned to the first cluster, the second node to the fourth cluster, and the remaining nodes to the second cluster. For QAOA, (8) each column represents a qudit and cach node a qudit state. For SQAOA, each node represents a qubit. Nodes colored black corre- spond to qudit states qubits set to [1), and white nodes to qudit (9) states or qubits set to J0). The arrows indicate transitions realized by the mixing operator. For SQAOA, the colors indicate the three sub-problems where, due to the measurements, the same physical (10) qubits can be used for all sub uub-problems.
P (II 1=1
|..
SQADA 7/,
where
UT = Hu, uE Vi,
UM,, (B) = e -B8 V
Vi,a
Uc Ve,,,11 (2) = -in Euve Ei,x Cur ZuZ
(11)
E - Euevi wuZu
Gi = (Vi,e, Exx)) is the graph obtained from G by re- moving nodes decided, i.e., labeled O, in solution (z) of the previous sub-problem and w E IRY are weights ful- filling = * w for all distinct nodes u, v E V. For the first sub-problem we need to consider the whole graph G; therefore, we set (z) to [1), i.c., all nodes are yet undecided.
sub-problem. Since there can be exponentially many of these for dense probability distributions, this may constitute performance bottleneck. However, since apply nucleus sampling, as discussed previously, we only need to evaluate the next problem on the states in the nucleus. Although this does not guarantee a sub-exponential number of evaluations, we show experimenaally in Section 5 that this number re- mains almost constant for the considered problem sizes and low nucleus sampling thresholds.
After preparing the state 13. 7,,,), SQADA, we estimate the cor- responding probability distribution by sampling repeatedly from it and continue evaluating the next sub-problem on all states with non-zero probability. Once all sub-problems are processed, the expected costs are computed from the measured probability distributions. Figure 3 illustrates the described procedure compared to the multi-level approach of Weggemans et al. (2022).
Note that, besides the sum over V1,z in UC,.. the ansatz for sub-problem corresponds to the one used for solving max-cut with the Quantum Approximate Optimization Al- gorithm (Farhi et al., 2014). Without this second term in the phase-separation operator, only pairwise interactions between nodes weighted by the costs would be considered for the phase-separation. Including it allows also take individual nodes with weights into account. Note further that, while all other terms are permutation invariant, and we thus expect the parameters 3 and 712 to be reusable across instances as for QAOA, the newly introduced term with parameter "/2 is not, leading to the necessity of relearning it for different problem instances, or even the same instance when permuting nodes.
The transition operator Ur,.. uses Hadamard gates to con- struct an equal superposition of all feasible states of the sub- problem. The mixing operator UM. enables transitions between the feasible states of a sub-problem by flipping qubits, i.e., by changing if the corresponding nodes remain in the current cluster, or are assigned to new cluster that is further split in the next sub-problem. The phase-separation operator UC.. incorporates the cost function into the first exponent, as described in Section 3, but drops constant terms since they affect all states in the same way and can be neglected. Additionally, the Hamiltonian given by the second exponent allows cost-independent separation of phases based on individual nodes. The motivation behind introducing this second term with weights as well as the reason for restricting those, will be discussed in Section 5.
As shown by Weggemans (2020), operators (9-11) can be implemented using only Hadamard, RX, RZ and CX gates without requiring additional ancilla qubits. Moreover, since we measure after processing a sub- sub-problem, qubits can be reused, and thus only a total of n qubits are needed for the whole algorithm.
As described, we evaluate each sub ao--problem with respect to all solutions having a non-zero probability in the previous
6

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Algorithm 1 SQAOA Correlation Clustering
globally optimal solution for p - co. However, when including the term for individual nodes, have been able to show this by adapting the universality proof for the Quan- tum Approximate Optimization Algorithm from Morales et al. (2020) as shown in the following. The proofs of the upcoming lemmata are deferred to Appendix B.
probabililiees empty dictionary current_states empty set
add 1 to current for i to do nezt states = empty set
for r in wwrrent_statee do
Definition 5.1. Given a set of Hamiltonians (H1 ....... Hgl, we call the smallest real Lie algebra L with the commutator the Lie bracket containing the elements of P the generated Lie algebra of P.
for shot 1 to 1000 do
(v) UT,.. 10)
for j = 1 to do
(b)) = U... (5t,g) CC, (Ti,)) lx)
Proposition 5.2. (D D'Alessandro, 2021) Let P be set of Hamiltonians and let L be the generated Lie algebra of P. The set of unitaries that can be approximated to arbitrary precision by iterated application of the elements in P given by
measure (16) and update pr probabilitiesiile
add nucleus prohabilities to next states current_states = next states
costs empty dictionary for i to 1 do
{E iA A L}.
for in probubilities(]] do costs(i][b] 0
Lemma 5.3. Let = (V, be an undirected graph, let R. and R.V. Let further
for p, x: in nucleus of probabilitiess(llyy do for u, v in E.g Cuo
HM Ex.:
Hc
Σ WOE
Coo Zy Σ Wazua
then
nEV
costs|illy] += p11 Iu) (1 -2--))) xw)
if i 1 then
and let L be the generated Lie algebra of {HM. Hc}. It holds that
costs[i][b] += p.u. V.
if then costs|i][y]
He == Σ
w Un E C.
+- p - Fn) De
+ p Iu (1 - x3x)
WEV
if * then
) be an undirected graph and Lemma 5.4. Let G - (V,E) let w E RV. Let further
costs p costli + [][r]]
return costs
1]
HM ΣxE, WEV
Ho Σ NEV
W. Zo
and let L be the generated Lie algebra of (HM: Ho }. If w., + we² for all distinct u, E V, holds for all E V
5. Evaluation
that
In this section, we evaluate our SQAOA formulation for correlation clustering. Firstly, we show that for > 0o, there exist parameters for each problem instance such that an optimal solution is obtained with certainty. Secondly, we experimentally compare our approach to the one of Wegge- mans et al. (2022) in terms of approximation ratios and runtimes.
Hw, X.. E L.
Theorem 5.5. Let G (V,E) be an undirected graph, let c R and E RV with w. # we 2 for all distinct u, v E V. Let further
UT = X H
aEV
Theoretical Analysis QAOA yields an optimal solution under conditions given by Binkowski et al. (2024), con- taining especially p + and that the optimal solution is an cigenvector of the phase-separation operator with the small- est cigenvalue. Although the given operators fulfill these conditions, this argument only guarantees to reach optimal solutions on the individual sub-problems but not globally optimal solution. Considering only pairwise interactions for the mixing operator, we have not been able to prove or disprove that there exist parameters such that (8) yields
(M( = E -i Enev X.
and
Uc(m.72) i1(71 Enses cur 2, 2, t22 Euey 2n.)
For any basis state (x) with x E (0, 13 there exist pa- rameters Bis 7j E for j (1,..., P) and phuse shift such that it holds for p oo:
P [II j=1
-10 (o))
(B (2))) 10)

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Proof. Let & be the generated Lie algebra of (Har Hc). After applying Ur, the qubits are in state Ur 0)) Since Hu E C by Lemma 5.3 and Lemma 5.4, we can revert this state to 0) (modulo phase shift of (-i)IVl) by applying Te e /2HH. = (-i) BuEv Hu- Next, we can (mod- ulo phase shift of -i) flip individual qubits associated with nodes u E by applying e - -ix., since X2 E C by Lemma 5.3 and Lemma 5.4. This allows to con- struct arbitrary basis states (a)) (modulo potential phase shift e e-())
Table I. Mean approximation ratios and runtimes for solving 50 correlation clustering problem instances on Srdōö--Rény Graph graphs with n 3, 4, 5 nodes using the multi-level QAOA formu- lation of Weggemans et al. (2022) and SQAOA with a depth of p = 1 and thresholds for nucleus sampling t = 1.0.1
Erdös-Rényí Graphs Approximation Ratio
== 3
n =
5
QAOA t = 1
0.97 = 0.04
0.92 = 0.07
0.92 I 0.07
QAOA 0.1
1.00 0.00
1.00 + 0.00
1.00 + 0.00
According to Theorem 5.5, arbitrary basis states can be constructed in each sub-problem when approaches infin- ity. Therefore, for each instance of the correlation cluster- ing problem, there clearly exist parameters such that our SQAOA formulation (8) obtains optimal solutions with cer- tainty.
SQAOA =
0.94 :: 0.08
0.88 + 0.09
0.85 + 0.10
SQAOA = 0.1
1.00 0.00
1.00 + 0.02
1.00 + 0.02
Erdös-Réng Graphs Runtime [s]
n =
n 4
1 =
QAOA t 1
121 +
221 + 30
316 1 44
Empirical Analysis To demonstrate the advancements of SQAOA and nucleus sampling in general, we conduct experiments on instances of the correlation clustering prob- lem involving complete graphs and Brdöö-Rééyí graphs where the probability of an edge being present is 0.5. We then compare these results with those of the multi- level QAOA formulation presented by Weggemans et al. (2022). The code for the SQADA experiments is available at https//ggthuub.comfabbiaaae http:/aaabiannna//AAA....
QAOA t 0.1
5
15
109 1 32
SQAOA 1 23 12
161 + 45
799 256
SQAOA = 0.1
2+1
6+
10+5
Table shows approximation ratios and runtimes obtained for multi-level QAOA and SQAOA with depth p on correlation clustering instances of Erdös-Rényí graphs with 3, 4, 5 nodes and two thresholds t 1 and t = 0.1 for nucleus sampling. An extended version of this table containing results for complete graphs, depths p 2, 3 and threshold = 0.5 is given in Appendix C. As can be seen from the table, both QAOA and SQAOA perform, even for 1, significantly better than the Swamy bound of 0.7666 (Swamy, 2004) with SQAOA achieving slightly worse ap- proximation ratios. Setting the threshold to t 0.1 greatly improves the approximation ratios, leading to optimal re- sults for QAOA and near optimal results for SQAOA. While improving the approximation ratios, reducing the threshold also leads to an overall reduction of the runtime for the given experiments. However, this does not hold in general. As shown in the appendix, solving QAOA with / 0.5 takes significantly longer than solving QAOA with t 1 for the dataset with 5 nodes. For SQAOA, we do not observe such behavior; in fact, the runtimes seem to scale much better than for the QAOA approach when using a low threshold for nucleus sampling.
For the experimental setup, we mainly follow Weggemans et al. (2022). In particular, for fixed graph size, we eval- uate the performance on datasets consisting of 50 problem instances with edge weights {+1, -1]. where the probabil- ity of an edge having weight +1 is uniformly increased from 0 to 1 to represent all weight configurations. Mean values and standard deviations given in this section always refer to the results obtained for a dataset, i.e., mean approximation ratio of 1.0 with standard deviation of 0.0 indicates that all 50 instances are solved to optimality.
For the classical optimization procedure, we use the Pow- ell optimizer, which has proven to be efficient for solving other problems with QAOA (Pellow-Jarman al., 2021; Fernández-Pendáás et al., 2022). Further, for each dataset, we first learn parameters for the instance with all edges hav- ing weight- -1 1 and then use these parameters as an initial point for the remaining instances in that dataset. The only exception are the parameters 72 used the phase-separation operator of SQAOA. Those are, due to their permutation dependence, always initialized to The corresponding weights are chosen by enumerating all nodes by integers ranging from 1 to n. With this choice, the phase-separation operator remains 2p-periodic with respect to each of its parameters. We set the number of shots used to estimate probability distributions to 1000 and restart each optimiza- tion procedure 5 times, taking only the best overall result.
Since the threshold alters only the computation of the cost function for QAOA and not the quantum algorithm itself, the difference in runtimes must be caused by an increased number of function evaluations during the optimization pro- cedure. This might be due to the fact that discontinuities get introduced to the cost function when states enter or leave the nucleus. For SQAOA on the other hand, reducing t has always resulted in lower runtimes for the experiments we
8

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
10
1000
6. Conclusion
t=1
0-5
800
Function Evaluations
We introduce the Sub-Problem Quantum Alternating Opera- tor Ansatz (SQAOA), generalization of the Quantum Alter- nating Operator Ansatz (QAOA) based on nucleus sampling and splitting problems into sub-problems. In a theoretical analysis, we show that for each instance of the correlation clustering problem, there exist parameters such that a spe- cific SQAOA formulation of the problem obtains an optimal solution with certainty. Further, we show experimentally that this SQAOA formulation outperforms existing QAOA approaches for correlation clustering in terms of approxima- tion ratios and runtime while using only as many qubits as there are elements to cluster.
t=0.1
Nucleus Size
600
400
200
3
Number of Nodes
Figure 4. Depicted is a diagram showing the mean nucleus size and the mean number of function evaluations when solving the dataset of Erdös-Ro Erdös-Rényi graphs with 5 nodes using SQAOA with depth p 1 for nucleus sampling thresholds of 1, 0.5, 0.1.
We see two possible directions for future research: Further analyzing SQAOA for correlation clustering and extending its application to other problems. Regarding the first direc- tion, we have not yet given lower bound on the achieved approximation ratio, as it is done by Weggemans (2020) for the multi-level formulation. One could also consider mod- elling correlation clustering with different sub-problems since we do not exploit the full expressiveness of SQAOA with the current formulation, which uses the same operators for each sub- nub-problem. Regarding the second direction, split- ting a problem into sub-problems is a universal approach, and similar improvements may be possible for problems beyond correlation clustering. Of partieular interest are thereby problems in which elements are assigned one of multiple labels. For example, one could consider the Max- imum k-Colorable Subgraph Problem with sub-problems coloring parts of the graph that have not yet been considered using a fixed number of colors smaller than k.
1.00
2000
Apprxciaation Ratio
0.98
1500
0.96
SQAOA
Ronfine
QAOA
0.94
1000
0.92
500
0.90
3
10
Number of Nodes
Figure 5. Depicted is a diagram showing the mean approximation ratios and runtimes of SQAOA (1 0.1) and the multi-level QAOA approach of Weggemans et al. (2022) (1 = 1) with ansatz depth p = when applicd to datasets Frdös-Rényi graphs with up to 10 nodes for SQAOA and nodes for QAOA.
A Acknowledgements
We thank Jordi Weggemans for providing the source code of Weggemans et al. (2022), which we use to perform the QAOA experiments. This work is partly supported by the Federal Ministry of Education and Research of Germany through DAAD Project 57616814 (SECAI) and Project 16KIS2332K (AL.utt-lmmune).
have conducted. This is due to the fact that, even as the num- ber of function evaluations increases, each evaluation takes less time since fewer elements are in the nucleus. This is illustrated in Figure 4 for the dataset of Erdōs-Rény' graphs with 5 nodes and p- 1. In particular, one can see that the number of elements in the nucleus is almost constant for the considered problem sizes and low thresholds.
Impact Statement
This theoretical article presents work whose goal is to ad- vance the field of machine learning, more specifically clus- tering. As for all advances in this field, there are many potential societal consequences of our work. However, we do not feel that the implications of this article differ from those of other contributions to that field and must be specifi- cally highlighted here.
Weggemans et al. (2022) consider instances of the correla- tion clustering problem with up to 7 nodes. In Figure 5, we give approximation ratios and runtimes for SQAOA with t = 0.1 and p on instances with up to 10 nodes. As can be seen from the figure, the runtime increases expo- nentially, as expected, although slower than for the QAOA formulation. The approximation ratio, however, seems to remain almost constant, further corroborating the potential of SQAOA and variational algorithms in general.
9

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
References
D'haeseleer, How does gene expression clustering work? Nature Biotechnology, 23(12):1499-150) 2005. doi: 10. 10.1038/nb112051101 1499.
Abbas, A. and Swoboda, P.
ClusterFuG: Cluster- ing Fully connected Graphs by Multicut. In ICML,
2023. URLhttps: seettp::/ppoceednnng wtw.ediiinn...m...pp....m.... www.m.r.pp... press/ abo2/abbbs..a..
Erola, P., Björkegren, J. L. M., and Michoel, T. Model- based clustering of multi-tissue gene expression data. Bioinformatics, 36(6):1807-188) 2020. doi: 10.1093/ bioinformaticssbrz800..
Akshay, V., Rabinovich, D., Campos, E., and Biamonte, J. Parameter concentrations in quantum approximate optimization. Phys. Rev. A, 104:L010401, 2021. doi: 10. 1LL.SPPhyyRRAAA04411000000
Esposito, A. and Danzig, T. Hybrid classical-quantum sim- ulation MaxCut using QAOA-in-QAOA, In Interna- tional Parallel and Distributed Processing Symposium Workshops, 2024. doi: 10. N0.100//PDPSW63119.200 00180.
Bansal, N., Blum, A., and Chawla, S. Correlation clustering. Machine Learning,
2004. doi: 10.1023/B:
MACHL.000003116.555744499
Farhi, E. and Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm, 2019, URL https://aaaae org
Beier. T., Hamprecht, F. A., and Kappes, J. H. Fusion moves for correlation clustering. In CVPR, 2015. doi: 10.1109CCVRR.2015779888
/ /abs//b///////// /ta.b///e 100.2.60.000 07674.
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lund- gren, A., and Preda, D. A quantum adiabatic evolu- tion algorithm applied to random instances of an np- complete problem. Science, 292(5516):442-4755 2001. doi: 10. 111//sciencc.00577266
Benjelloun, O., Garcia-Molina H., Menestrina, D., Su, Q., Whang, S. E., and Widom, Swoosh: a generic approach to entity resolution. The VLDB Journal, 18(1):255-276, 2009. doi: 00.1007/500778-00-00000
Binkowski, I.., Koßmann, G., Ziegler T., and Schwonnek, R. Elementary proof of QAOA convergence. New Journal of Physics, 26(7):073001, 2024. doi: 10.1068/136--2630 ad59bb.
Farhi, E., Goldstone, J., and Gutmann, S. A quantum ap- proximate optimization algorithm, 2014. URL https: / / //arxii.org//aaaalaa./aa httpa/////ll...... //1///1111.44 4028.
Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., and Rúa, I. F. study of the perfor- mance of classical minimizers in the quantum approx- imate optimization algorithm. Journal of Computa- tional and Applied Mathematics, 404:113388,, 2022. doi: 10. 10.1016/j.cam/ cam..221.mmm...1.1mm 113388.
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.- H., Pandya, K., and Summer, A. A review on quan- tum approximate optimization algorithm and its vari- ants. Physics Reports, 1068:1-66, 2024. doi: 10.1016/j. physrep.2024. 200.00000.
Brandao, G. S. L., Broughton, M., Farhi, E., Gutmann, S., and Neven, H. For fixed control parameters the quan- tum approximate optimization algorithm's 's objective func- tion value concentrates for typical instances, 2018. URL ht attpp:: / //tx/aiivvv./////////aaa//a.aavl wwwxivv.ogg/aae 1812.11 04170.
Fuchs, F. G., Kolden, H. Ø., Aase, N. H., and Sartor, G. Ef- ficient encoding of the weighted max k-cut on a quantum computer using QAOA. SN Computer Science, 2(2):89, 2021. doi: 10. 10.10077/42299--22-0004777
Hadfield, S., Wang, Z., O' O'Gorman, B., Rieffel, E. G., Venturelli, D., and Biswas, R. From the quantum ap- proximate optimization algorithm to quantum alter- nating operator ansatz. Algorithms, 12(2), 2019. doi: 10.3390/a
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., and Coles, P. J. Variational quantum algorithms. Nature Reviews Physics, 3()):225 -644, 2021.
doi: 10. 1038//42254-021-0004444
Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y. The curious case of neural text degeneration. In ICLR, 2020. URL https: http:::///pppeeeeeee oppnrevieeeeeeeeeeee net forum?? i id=rygGdyrFvi:
Cook, J., Eidenbenz, S., and Bärtschi, A. The quantum al- ternating operator ansatz on maximum k-vertex cover. In International Conference on Quantum Computing and En- gineering, 2020. doi: 10. N,.110//QCA49297.20000 20w.:///..99....2..0000 2020.000...
Keuper, M., Levinkov, E., Bonneel, N., Lavoué, G., Brox, T., and Andres, B. Efficient decomposition of image and mesh graphs by lifted multicuts. In ICCV, 2015. doi: 10. 2.1100///.22205.220
D' Alessandro, D. Introduction to quantum control and dynamics. Chapman & Hall/CRC. Taylor & Francis Ltd, 2nd edition, 2021. doi: 10.120 268.
10

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Morales, M. E. S., Biamonte, J. D., and Zimborás, Z. On the universality of the quantum approximate optimization algorithm. Quantum Information Processing, 19(9):291, 2020. doi: 10.1007/s1 0150://s111110100 0088-020-0274--9
Wurtz, and Love, P. MaxCut quantum approximate op- timization algorithm performance guarantees for 1. Phys. Rev. A. 103:042612, 2021. doi: 10.1103/PhysRev. 103.042612.
Nielsen, M. A. and Chuang. I. L. Quantum Computa- tion and Quantum Information: 10th Anniversary Edi- tion. Cambridge University Press, 2010. doi: 10.1017/ CB0978051197667..
Yarkony, J., Ihler, A., and Fowlkes, C. C. Fast planar corre- lation clustering for image segmentation. In ECCV, 2012. doi: 10.
Pellow-Jarman, A., Sinayskiy, I., Pillay, A., and Petruc- cione, F. comparison of various classical optimizers for variational quantum linear solver. Quantum In- formation Processing, 20(6):202, 2021. doi: 10.1007/ s1 02-0011---
Preskill, Quantum computing and the entanglement fron- tier, 2012. hRLps http::://axxvvvv/aa/eeeo abs 1203. 5813.
Preskill, Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018. doi: 10.22331/g-22 (0----001-------0
Saleem, Z. H. Max-independent set and the quantum alter- nating operator ansatz. International Journal of Quan- lum Information, 1 18(44)2200001, 2020. doi: 10.1 142/ $0219749920500112
Swamy, C. Correlation clustering; maximizing agreements via semidefinite programming. In SODA, 2004.
Tabi, 7., El-Safty, K. H., Kallus, 7., Haga, P., Kozsik, T., Glos, A., and Zimboras, Z. Quantum Optimization for the Graph Coloring Problem with Space-Efficient Em- bedding. In International Conference on Quantum Com- puting and Engineering, 2020. doi: 10.1 109/QCE4999 2020.00018.
Tan, A note on the inapproximability correlation clus- tering. Information Processing Letters, 108333333--33, 2008. doi: 00.10166j.p1.2008.000 .0..000.004......
Tomesh, T., Saleem, Z. H., and Suchara, M. Quan- tum local search with the quantum alternating opera- tor ansatz. Quantum, 6:781, 2022. doi: 10.22331/ g-2022-08-22-781
Weggemans. J. Solving correlation clustering with the quan- tum approximate optimisation algorithm, 2020. URL http:///esay..uveeeee.n..l
Weggemans, J. R., Urech, A., Rausch, A., Spreeuw, R., Boucherie, R., Schreck, F. Schoutens, K., Minář, J., and Speelman, F. Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach. Quan- tum, 6:687, 2022, doi: 10.22331/q-200 04-13-687

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
A. Quantum Gates
X = T 1 1 0
Pauli-X:
x x = (1)
Rotational X:
(x) e e-00 cos(0)1 sssn (0)
2 2: 0
Pauli-Z:
Z - 11)
-1
Rotational RZ
-07 cos(0)1 Z
1
Hadamard:
11
-1]
H
10)
(10) (1))
v2
V2
1 0 0
0
100)
0 1
001)
Conditional X:
CX: =
0
0 0
10)
0
0
1
0
111)
12

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
B. Additional Proofs
Proof of Lemma 5.3. We want to show that Ho -uev Wn Wn is in the generated lie algebra of { Hc). where HM- Emey Xu and Hc Enver Curtutu + Euev W.Za. For notational convenience, we define Hc, = EuvcR Cuvluty.
In analogy to Morales et al. (2020), we define series of commutators in L, showing finally that He E C:
Hyz == Hcc, [Hc, HM] = (Hc,, HM] + [Hor, HMll)
1
1
2i
2i
= ΣE
Cuo (Zu Y. + Σ W WyyuEr EL,
uvEE
wEV
1
[yyz, HM1
Σ Guv ZaY, + YuZos
Σ
Xv/ + Σ
Wn Ya,
WulYa:
X
2i
uEEE
w'eV
NEV
WEV
Σ
Cuv (Y,Y, - -uZi -ZuZ. + YuY.)
Zu
WEER
NEV
2 Σ
Cuv (YaY, - -uTto)
Σ
Wr Zu E
W
NEV
H() == 2i
Hyz, HM] + Hc = Σ
Cun (2Y,Y, - -Zuz,) E
auEE
H22) 2i
1 (1))) HM]
1
[aa) Har
Σ
Guv (2 ΣXul
Xw/
[Zu Σ xxr))
2i
uvEE
W/EV
W'EV
Σ
Cuv (2( (2(-ZuY, YuZo)
.Yy + ZuYo))
WEER
3
Σ auEE
Cuv (ZaY, + +YuZ,) E c,,
1
(1lly HM] + 1 H1, HMl)
lHz + H(g HM]
2i
3
2i
Σ WyZu +2 Σ Cur (Y,Ye - -zuZz)
uEV
WHEF
Σ
Cuv (YuY, -u-Z. - Z.Zr + YoYu)
arEE
Σ WyZy
WEV
- Ho E C.
It follows directly from -H L that Ho E L.
13

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Proof of Lemma 5.4. We show that He and X are for all v' E V in the generated lie algebra L of (HM, Hoy ) where H Evey Xu and He Luev Zu with w,, 2 + w. for all u, v E V.
Assume we have already shown X L. It follows directly that Y.' [ w. and thus H.r 2 (Z + X) E L. Consequently, only remains to show Xa E
Xarl E L, further Zu = z ( E
Define n = IV For proving X E L, we first show that if HM = Euevi wy L with V VV, and w/ # w¹, for all u, V' we can for any x E V" construct Enevi(()) wxX, E C such that whi & wh for all u V \ {z). In particular, follows from
Hy = Hc. H = Σ
w. wa Yu E C
2i
wEV
and
Hx == Hy,, He] = Σ
w Xu E E,,
21
uEV()
that it holds for every x V that
w H
Hx
(w
" Xu E C.
(EV
Setting w/ll" (w² w w/y" yields the desired result.
only remains to show that we can initially construct such an HM Therefore, consider first
Hy = 2i Hc. HM] =
Σ
W.Ya.
WEV
We then get
1
[ly Hcl Σ
w H
2i
NEV
with V' V.aan and w' = w.
14

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
C. Additional Tables
Table 2. Mean approximation ratios and runtimes with standard deviations for solving 50 correlation clustering problem instances on complete and Erdös-Rényi graphs with n = 3, 4, nodes using the multi-level QAOA formulation Weggemans et al. (2022) and SQAOA, ansatz depths of 2,3 and thresholds for nucleus sampling of 1, 0.5, 0.1.
Complete Graphs Approximation Ratio
QAOA
QAOA = 0.5
QAOA = 0.1
SQAOA
SQAOA = 0.5
SQAOA t 0.1
0.97 + 0.04
1.00 0.00
1.00 + 0.00
0.96 0.05
1.00 + 0.00
1.00 + 0.00
1.00 + 0.00
1.00 0.00
1.00 + 0.00
0.97 0.05
1.00 0.00
1.00 + 0.00
1.00 0.00
1.00 0.00
1.00 + 0.00
0.91 + 0.07
0.99 0.02
100
0.98 0.02
1.00 = 0.02
4
0.98 1 0.02
1.00 0.00
1.00
0.83 0.06
1.00
1.00 + 0.00
1.00 0.00
1.00 + 0.00
0.99 0.03
0.99 + 0.04
0.90 + 0.08
0.97 0.04
0.98 0.04
0.86
0.97 0.03
0.99 - 0.03
5
0.95 0.00
0.98 0.04
0.98 - 0.05
0.86 0.08
0.98 0.03
0.99 - 0.03
0.98 0.04
0.98 + 0.05
0.99
0.99 + 0.03
Complete Graphs Runtime [s]
QAOA
QAOA 0.5
QAOA 0.1
SQAOA L
SQADA 0.5
SQADA t 0.1
173 = 33
+ 1
5 =
0
44 =
14 5
2
n=
315 + 59
16 + 2
15 + 2
100 = 21
15 7
4 2
30 + 1
21 + 5
27
7 4
272 1 23
40 1 8
15 1
207 + 50
41 15
9
4
691 + 58
85 + 17
35 +
422 + 77
78 + 27
15 15
102 + 36
55 + 16
85 + 22
18 15
488 + 60
716 + 302
109 + 32
1268 + 450
155 + 78
15 15
11 =
1012 + 101
1140 + 190
216 + 35
2438 + 836
265 + 118
26 + 9
2361 1: 641
349 1 73
384 1 175
50 1 15
Frdós-Rényí Graphs Approximation Ratio
QAOA 1=
QAOA = 0.5
QAOA = 0.1
SQAOA /
SQAOA = 0.5
SQAOA L 0.1
0.97 + 0.04
1.00 + 0.00
1.00 = 0.00
0.94 0.08
1.00 + 0.00
1.00 + 0.00
n = 3
1.00 0.01
1.00 0.00
1.00 + 0.00
0.94 - 0.08
1.00 + 0.00
1.00 + 0.00
0.00
1.00 0.00
1.00 0.00
1.00 0.00
0.92 0.07
1.00
1.00
0.88 = 0.09
0.99 0.03
1.00 - 0.02
n 4
0.97 + 0.03
0.00
1.00
0.88 0.09
1.00 0.02
1.00 0.00
0.00
1.00
1.00 0.00
1.00 0.00
0.92 + 0.07
0.98 0.08
1.00
0.85 = 0.10
0.98 - 0.03
1.00 0.02
5
0.96 + 0.04
1.00 0.01
1.00
0.85 = 0.10
0.99 0.03
1.00 - 0.00
1.00 0.01
1.00 0.00
1.00 1 0.01
1.00 - 0.00
15

---

A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Table (Continuation)
Erdös-Rényí Graphs
Runtime [s]
QAOA = 1
QAOA = 0.5
QAOA t = 0.1
SQAOA t =
SQAOA = 0.5
SQAOA t = 0.1
121 + 40
1
5 +
0
23 - 12
8 8 4
2 = 1
Y1 == 3
272 + 84
12 + 2
15 - 2
53 = 27
15 + 8
4 + 2
26 + 3
21 + 5
23 + 12
7 3
221 + 30
38 1 9
15 + 2
161 + 45
38 + 18
6 6 2
Y= 4
501 + 98
54 1 9
35 + 7
338 102
52 25
12 + 4
139 + 26
55 + 16
97 + 37
19 + 7
316 1 44
809 148
109 1 32
799
256
127 1 61
10 1 5
71 = 5
748 + 125
1285 304
216 + 35
2155 789
193 + 94
22 + 7
1860 386
349 - 73
256 + 116
28 - 9
16


Reviews:
[{"review_id": "wHnhQBP5y3", "reviewer": "Reviewer_fb8D", "summary": "The paper explores the power of the Quantum Alternating Operator Ansatz algorithm. In particular, the focus is on the optimization problem called correlation clustering and provides a way to solve it by dividing the Quantum Alternating Operator Ansatz algorithm in subproblems. They show that by iterating to infinity the optimal solution is found and provide experiments in specific topologies that show good performance.\n\n## Update after rebuttal\n\nThank you to the authors for the answers to my questions. I think with the changes proposed the manuscript will improve.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all reviewers for their constructive feedback.\nThere seems to be consensus that our experimental and theoretical claims are correct and that the proposed approach surpasses previous QAOA methods for correlation clustering. Here, we gladly address remaining questions and concerns of Reviewer fb8D:\n\n**QAOA**\n\nThe Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm that was established after it. The acronym \"QAOA\" is used for both approaches in their original papers and in further literature.\n\nDifferences between the two approaches concern the incorporation of constraints and the use of problem-dependent mixing operators and initial states: On the one hand, the Quantum Approximate Optimization Algorithm first transforms the given optimization problem into an equivalent one in which the constraints are replaced by penalty terms in the objective function. Then, fixed mixing and problem-dependent phase-separation operators are applied alternatingly to the initial state that is an equal\nsuperposition of all possible states. On the other hand, the Quantum Alternating Operator Ansatz works directly on the original problem by incorporating the constraints in problem-dependent mixing operators and by choosing an initial state that is a superposition of feasible states.\n\n**Applications beyond Correlation Clustering**\n\nDue to the character limit, we kindly refer the reviewer to the answer given in the rebuttal to reviewer L5UV.\n\n**$\\mathbf{p}$ in the Abstract**\n\nWe agree that our use of the symbol $p$ in the abstract needs clarification and suggest to replace \"if $p \\rightarrow \\infty$\" with \"if the depth of the ansatz tends to infinity\".\n\n**More Detailed Explanation of Correlation Clustering**\n\nTo further illustrate the ILP formulation of the correlation clustering problem, we propose to insert the following paragraph after Line 178 and to also include a figure with a simple example.\n\n\"In this formulation, the variable assignment $x_{u,1}=1$ and $x_{v,2}=1$ for nodes $u,v$ indicates that node $u$ is in Cluster $1$ and that node $v$ is in Cluster $2$. Thus, the nodes are in different clusters. A value of $1$ is contributed to the objective value if and only if $c_{uv}=-1$.\"\n\n**Translation of Correlation Clustering to SQAOA**\n\nTo comment further on the construction of the phase-separation operator, we propose to insert the following paragraph after Line 138:\n\n\"In order to apply QAOA to a specific problem, one needs to define and implement the operators and the initial state. The main challenge here lies in the construction of the initial state and mixing operator. Given a binary ILP formulation of the problem, as in (6), the phase-separation operator can be constructed easily by replacing a variable $x$ in the cost function $C(x)$ by the term $\\frac{(1-Z)}{2}$ in the phase-separation Hamiltonian $H_C$. This is due to the fact that if $x = 0$ then $\\frac{(1-Z)}{2} |x\\rangle =\n0 |x\\rangle$, and if $x = 1$ then $\\frac{(1-Z)}{2} |x\\rangle = 1 |x\\rangle$, and thus, (2) is fulfilled for the Hamiltonian constructed\nin this way. Implementing the corresponding unitary operator, then only requires the application of rotational Pauli-Z gates to individual qubits.\"\n\nTo explain in more detail the specific operators used in our SQAOA formulation of correlation clustering, we suggest to insert the following paragraph after Line 248:\n\n\"The transition operator $U_{T_i,x}$ uses Hadamard gates to construct an equal superposition of all feasible states of the sub-problem. The mixing operator $U_{M_i,x}$ enables transitions between the feasible states of a sub-problem by flipping qubits, i.e. by changing if the corresponding nodes remain in the current cluster, or are assigned to a new cluster that is further split-up in the next sub-problem. The phase-separation operator $U_{C_i,x}$ incorporates in the first sum of the exponent the cost function as described in Section 3 but drops constant terms. Additionally, the Hamiltonian given by the second sum of the exponent allows a cost-independent separation of phases based on individual vertices.\"\n\n**Sub-Problem Decomposition**\n\nThe decomposition we define is specific to the correlation clustering problem. Other decompositions are conceivable and might yield further improvements. In general, the main challenge in applying the Quantum Alternating Operator Ansatz lies in the definition and implementation of mixing operators and initial states appropriate for the specific optimization problem. For applying SQAOA, in addition, the sub-problems need to be chosen carefully.\n\nBeyond correlation clustering, candidates for our sub-problem approach are ones in which elements are assigned one of multiple labels. E.g., one could consider the Maximum $k$-Colorable Subgraph Problem with sub-problems coloring so-far-unconsidered parts of the graph by a fixed number of colors smaller than $k$.", "claims_and_evidence": "The claim is that Quantum Alternating Operator Ansatz algorithm can be adapted to find the optimal solution to the correlation clustering. This is shown analytically and empirically.", "methods_and_evaluation_criteria": "The analysis seems to be correct. The empirical evaluation is restricted to some specific topologies, but they are general enough for a first study.", "theoretical_claims": "I did not check the proofs in detail, but the results and claims are intuitively correct.", "experimental_designs_or_analyses": "I looked at the empirical results and they seem fine.", "relation_to_broader_scientific_literature": "QAOA is usually the acronym for Quantum Approximate Optimization Algorithm. I think this has to be mentioned in the introduction.", "essential_references_not_discussed": "I did not find anything missing, but I would like to see a discussion on the difference between Quantum Approximate Optimization Algorithm and Quantum Alternating Operator Ansatz, and how one generalizes the other.", "other_strengths_and_weaknesses": "The proposed approach for the Quantum Alternating Operator Ansatz can possibly be used for other problems. However, for now the application is only for correlation clustering, making it limited.", "other_comments_or_suggestions": "Say what is p in the abstract.\n\nI feel that the correlation clustering problem statement was a bit underexplained (lines 165-178), and I did not quite understand how the original problem is transformed into the SQAOA, and how the max-cut problem is used to construct that definition, I think a bit more detail on the construction of equation 11, and the use of the gate of equation 9 could be useful.", "questions_for_authors": "What is the difference between Quantum Alternating Operator Ansatz and Quantum Approximate Optimization Algorithm? Wy is the same acronym used for both?\n\nHow specific is your subproblem decomposition for the correlation clustering problem? Can it be applied to other problems? Which are good candidates? (You say \"splitting a problem in sub-problems is a universal approach, and similar improvements might be possible on other problems suitable for QAOA.\")", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZS5dFkFdvl", "reviewer": "Reviewer_JUTn", "summary": "The paper presents a new quantum optimization approach called the Sub-Problem Quantum Alternating Operator Ansatz (SQAOA) aimed at solving correlation clustering problems. The approach modifies the Quantum Alternating Operator Ansatz (QAOA) by introducing two key modifications: 1) it uses nucleus sampling to compute the cost function and 2) it divides the problem into sub-problems, solving each one individually with QAOA. The authors argue that these changes lead to a method that is more suitable for the specific challenges posed by correlation clustering. Theoretical guarantees are provided, showing that SQAOA can obtain optimal solutions as the depth of the quantum circuit approaches infinity (p → ∞). Experimental results demonstrate that SQAOA outperforms standard QAOA in terms of approximation ratios and runtimes on various graphs, such as complete and Erdős-Rényi graphs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all reviewers for their constructive feedback.\nThere seems to be consensus that our experimental and theoretical claims are correct and that the proposed approach surpasses previous QAOA methods for correlation clustering. Here, we gladly address remaining questions and concerns of Reviewer JUTn:\n\n**Quantum Supremacy**\n\nWe agree that the presented approach does not solve existing problems of QAOA for achieving quantum supremacy, such as the number of shots or the gradient update for increasing ansatz depths, and we do not intend to make this claim.\nWe also see that the introductory statement \"QAOA is considered a promising candidate for achieving quantum supremacy for the following reasons:\" does not account for the problems with QAOA that need yet to be solved, and propose to replace it by \"QAOA is considered a promising variational quantum algorithm for the following reasons:\".\n\n**QAOA**\n\nThe Quantum Alternating Operator Ansatz is a generalization that was established after the Quantum Approximate Optimization Algorithm. The main difference between the two concerns the problem constraints. While the Quantum Approximate Optimization Algorithm incorporates them through penalty terms in the objective function, the Quantum Alternating Operator Ansatz incorporates them directly in the mixing operators and the initial state. The acronym \"QAOA\" is used for both approaches in their original papers and in further literature. Often it is not clearly distinguished between the two and Quantum Alternating Operator Ansatz is used as an umbrella term.\nWe use QAOA as an acronym for the Quantum Alternating Operator Ansatz and explicitly distinguish the Quantum Approximate Optimization Algorithm when necessary.\n\n**More Detailed Explanation of Correlation Clustering**\n\nDue to the character limit, we kindly refer the reviewer to the answer given in the rebuttal to reviewer fb8D.\n\n\n**Translation of Correlation Clustering to SQAOA**\n\nDue to the character limit, we kindly refer the reviewer to the answer given in the rebuttal to reviewer fb8D.\n\n**Applications beyond Correlation Clustering**\n\nDue to the character limit, we kindly refer the reviewer to the answer given in the rebuttal to reviewer L5UV.\n\n**Modelling with Qubits instead of Qudits**\n\nThe reviewer states that qudits are a perfect fit for clustering multiple labels (and thus for correlation clustering) and sees no motivation for our formulation of the problem in terms of qubits. We agree that qudits are a natural choice for correlation clustering. At the same time, our SQAOA formulation based on qubits outperforms the qudit-formulation in terms of approximation ratios and runtimes, while requiring less advanced and less specialized hardware. We consider this contribution relevant also because it is not obvious.\n\n**Figure 1**\n\nTo clarify the terms \"agreement\" and \"probability\" in Figure 1, we\nsuggest to replace the caption of this figure by the following one:\n\n\"Depicted are two diagrams showing the probability of measuring basis states when applying the multi-level QAOA formulation of Weggemans et al. (2022) with $p = 1$ to a correlation clustering problem instance on a complete graph with 4 nodes. Shown in addition are the agreements of these basis states, i.e. the value of the objective function in (6). The probabilities of the diagram at the top are obtained directly from the QAOA results. The probabilities of the diagram at the bottom are obtained by nucleus sampling with a threshold of $t = 0.5$.\n\n**Hyperparameter $t$**\n\nThe nucleus size $t$ used for nucleus sampling is indeed a hyperparameter whose choice could be further evaluated. \nThere is a trade-off between low probability states (for small t) and high sampling noise (for large t).\nDue to sampling noise, we expect the optimal parameter to decrease with increasing number of shots.\nHowever, even our ad hoc choice of t, without a systematic study, results in the greatly improved approximation ratios that we show in Table 1 and Appendix C.\n\n**Convergence to an Optimal Solution**\n\nThe reviewer states that, while our theoretical claim of reaching an optimal solution when the ansatz depth tends to infinity is legit, it is of no surprise.\nAll in all, we agree with this statement, especially taking into account the newly introduced term separating phases of individual qubits.\nAt the same time, the convergence guarantee we establish is necessary, we think, to put our approach on the same theoretical foundation as the Quantum Alternating Operator Ansatz.\n\n**Comparison with Wegemanns et al.**\n\nDue to the character limit, we kindly refer the reviewer to the answer given in the rebuttal for reviewer L5UV.", "claims_and_evidence": "The main contributions of this paper is clear and well supported. However, the claim that QAOA (quantum alternating operator ansatz) is considered a promising candidate for achieving quantum supremacy is not convincing to me. There are obviously other issues such as the number of shots to achieve desired accuracy, gradient update when $p\\rightarrow \\infty$, and etc. Without discussing all the aspects, it is not convincing to claim that QAOA is a promising candidate for quantum supremacy.", "methods_and_evaluation_criteria": "First of all, there is a mixup in quantum alternating operator ansatz and quantum approximation optimization algorithm, and the abbreviation QAOA requires a more specific assignment to which one of the above (or the multilevel QAOA in Weggemans et al., 2022). Besides, there are a few other issues.\n1. The correlation clustering (CC) problem requires more explanation. As the only testbed for the proposed algorithm, we need more information including how the authors convert the classical cost function to Hamiltonian, etc. The authors have also to convince the readers why we should focus on this specific type of Combinatorial Optimization problems instead of targeting general COs. The whole paper depends so much on a previous one (Weggemans et al., 2022).  I've quickly gone through this reference paper and I believe the reason why (Weggemans et al., 2022) choose to solve CC problem is because they would like to demonstrate the design of qudit instead of qubit on neutral atom quantum computers. And qudit is a perfect fit for clustering multiple labels. However, in this paper the authors are trying to translate the algorithm back to qubits, which seems not a good motivation.\n2. The definitions of Aggreements and Probability in Figure 1 are vague and need further clarification. The introduction of nucleus sampling also introduced a hyperparameter $t$, which seems deciding the value of $t$ is non-trivial and will be hard to determine with larger problem scales.", "theoretical_claims": "The theoretical claims are legit, but the main problem is it is not surprise for me. The authors can refer to [1] for the details of overparameterization theorem and I think as long as the alternating layers do not commute with each other and generate enough Lie Algebra dimension, they are guaranteed to achieve the desired state.\n\n[1] Larocca, Martin, et al. \"Theory of overparametrization in quantum neural networks.\" Nature Computational Science 3.6 (2023): 542-551.", "experimental_designs_or_analyses": "With only one baseline method and most of the experiments are conducted on graphs with less than 6 nodes, the experiments can only illustrate that the proposed method surpass Weggemans et al., 2022.", "relation_to_broader_scientific_literature": "The authors translate a previous literature for correlation clustering problem with qudits to qubits and proposed a sampling method to accelerate the convergence.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2TH2BnQd6b", "reviewer": "Reviewer_L5UV", "summary": "The paper constructs a new variant of QAOA (rather) specifically for the correlation clustering problem and shows improved performance over QAOA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all reviewers for their constructive feedback. There seems to be consensus that our experimental and theoretical claims are correct and that the proposed approach surpasses previous QAOA methods for correlation clustering. Here, we gladly address remaining questions and concerns of Reviewer L5UV:\n\n**Applications beyond Correlation Clustering**\n\nThe reviewer is concerned that we apply our approach only to correlation clustering. We agree that our article focuses on correlation clustering and have stated clearly in the title and abstract that it is about a generalization of QAOA for correlation clustering. Given the wide range of applications of correlation clustering and numerous papers, especially in recent years, focusing on this problem specifically, we think that this problem is interesting enough to be considered on its own. Furthermore, the constraints have made it particularly hard to apply QAOA to correlation clustering in the past, allowing us to demonstrate the effectiveness of our proposed generalization.\n\nBeyond correlation clustering, candidates for our sub-problem approach are ones in which elements are assigned one of multiple labels. E.g., one could consider the Maximum $k$-Colorable Subgraph Problem with sub-problems coloring so-far-unconsidered parts of the graph by a fixed number of colors smaller than $k$.\n\n**Comparison with Wegemanns et al.**\n\nThe reviewer is concerned that we compare our work only with that of Wegemanns et al. 2022.\nWe emphasize that the work of Wegemanns et al. is the only work that applies QAOA to the correlation clustering problem. In an article from 2020 different QAOA formulations are analyzed, the multi-level formulation is found to perform best and is further evaluated in an article from 2022. We have chosen to compare our approach with this best-performing method because it is the state of the art.\n\n\n**Ablation Study**\n\nThe reviewer notes that our empirical evaluation lacks an ablation study. \nThe presented approach consists of two main parts, nucleus sampling and the splitting of the given problem into sub-problems. \nWe evaluate both independently and in combination, in Table 1 and Appendix C, showing that nucleus sampling improves the approximation ratio while splitting into sub-problems reduces the runtime. \nWe agree with the reviewer that especially the splitting could be analyzed further. \nWe have in fact done this (not shown in the article) for a preliminary version of SQAOA that also parametrizes the transition operators. \nWe have found that this parametrization does not improve the approximation ratio, so we have decided not to report this negative result. Of course, we are prepared to do so in the supplement, should the reviewer recommend it.\n\n**Additional, Minor Corrections**\n\nWe understand the reviewer's comment that the introduction is rather long. To strike a balance between conciseness and accessibility, we propose to remove the sentence \"For example, Shor’s factoring algorithm (Shor, 1997) provides an exponential speed-up over the best-known classical factoring algorithm.\" from the first paragraph. We are\nprepared to shorten the introduction further if there is consensus among the reviewers that we should do so.\n\nTo introduce $\\mathcal{S}$ more clearly, we propose to replace Line 161 by \"$|s\\rangle$ is an initial state in the feasible space $\\mathcal{S}$, which is given by the set of all superpositions of classically feasible states, i.e. by\".\n\nWe have removed \"there is no interference between those states, and\" in Line 264.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "At a quick look, the proof seems fine. The proven property also is simple enough.", "experimental_designs_or_analyses": "Experimental analysis is done correctly, although very narrow in what is considered. This refers to both focusing only on a very specific problem domain and also to only considering the one chosen approach. Crucially, empirical evaluation lacks a proper ablation study to find out what parts of the approach really contribute to the results.", "relation_to_broader_scientific_literature": "Generalizing QAOA in the way it is described here appears powerful. However, focusing this strongly on correlation clustering severely limits any potential impact.", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "It is clear that the chosen approach is quite fitted to the problem of correlation clustering. However, potential for other or similarly structured problems should be discussed if not even evaluated.", "other_comments_or_suggestions": "Introduction is way too long. Basically, the first paragraph can be cut directly.\n\nmathcal{S} is weirdly introduced in line 163\n\n\"there is no interference\" is repeated twice (lines 262 -- 265)", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gOjrOE9JjF", "reviewer": "Reviewer_yi8D", "summary": "This paper proposed the QAOA for correlation clustering, by introducing a Sub Problem QAOA. This is motivated by the nucleus sampling and sub problem is dependent to solve correlation clustering. Although QAOA for correlation clustering has been studied in the literature, Weggemans et al. (2022) is restricted to 4-level qudits such that only solutions involving at most 4 clusters can be considered. \n\nThe paper guarantees that there exist parameters such that for depth $p \\rightarrow \\infty$  an optimal solution is obtained with certainty. The experiments are conducted in complete ad Erdos-Renyi graphs with 10 nodes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank all reviewers for their constructive feedback.\nThere seems to be consensus that our experimental and theoretical claims are correct and that the proposed approach surpasses previous QAOA methods for correlation clustering. Here, we gladly address remaining questions and concerns of Reviewer yi8D:\n\n**Applications beyond Correlation Clustering**\n\nThe reviewer is concerned that we apply our approach only to correlation clustering.\nWe agree that our article focuses on correlation clustering and have stated clearly in the title and abstract that it is about a generalization of QAOA for correlation clustering.\nGiven the wide range of applications of correlation clustering and numerous papers, especially in recent years, focusing on this problem specifically, we think that this problem is interesting enough to be considered on its own.\nFurthermore, the constraints have made it particularly hard to apply QAOA to correlation clustering in the past, allowing us to demonstrate the effectiveness of our proposed generalization.\n\nBeyond correlation clustering, candidates for our sub-problem approach are ones in which elements are assigned one of multiple labels. E.g., one could consider the Maximum $k$-Colorable Subgraph Problem with sub-problems coloring so-far-unconsidered parts of the graph by a fixed number of colors smaller than $k$.\n\n**Comparison with Wegemanns et al.**\n\nThe reviewer is concerned that we compare our work only with that of Wegemanns et al. 2022.\nWe emphasize that the work of Wegemanns et al. is the only work that applies QAOA to the correlation clustering problem. In an article from 2020 different QAOA formulations are analyzed, the multi-level formulation is found to perform best and is further evaluated in an article from 2022. We have chosen to compare our approach with this best-performing method because it is the state of the art.\n\n**Minimum Disagreement Formulation**\n\nThe approach is easily adapted to the minimum disagreement formulation (and to other linear objective functions with the same set of constraints) by modifying the phase-separation operator.\nSince the objective value of the minimum disagreement formulation differs from that of the maximum agreement formulation only by an additive constant, one can even use the same phase-separation operator in this particular case and add the constant in classical post-processing.\n\n**Performance with Larger Ansatz Depth $\\mathbf{p}$**\n\nThe reviewer is right, performance does increase with larger $p$, but using it is prohibited by computational resources. To make this explicit, we suggest adding the following paragraph after Line 154.  \n\n\"The approximation ratios are expected to increase with larger ansatz depth $p$ and are guaranteed to improve with optimal parameters. \nHowever, the depth is limited firstly, because the number of applied operators increases, resulting in problems with computational resources for the simulation on classical computers and the introduction of noise for the execution on quantum computers, and, secondly, to a lesser extent, since the number of learnable parameters increases with $p$ and gradients cannot be computed easily for the quantum circuit.\"", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Among the correlation clustering formulation, the paper focuses on the unweighted maximum agreement correlation clustering on general graphs, which is APX-hard but admits a constant-ratio approximation.\n\nCompared with QAOA, SPQAOA uses nucleus sampling for computing the cost function.\nThe set of states called nucleus is selected by the probability mass with threshold $t$ and $t=1$ recovers the standard sampling. $n-1$ subproblems are adapted to QAOA. Once all sub-problems are processed, the expected costs can be computed from the measured probability distributions", "theoretical_claims": "The proof is based on (Morales, 2020) and (D’Alessandro, 2021). It seems that it is not very hard to guarantee the optimality for $p \\rightarrow \\infty$.", "experimental_designs_or_analyses": "The comparison with multi-level QAOA formulation of Weggemans et al. (2022) was performed in simple setting,complete and Erdos-Renyi graphs where the probability of an\nedge being present is 0.5. SQAOA outperforms existing QAOA approaches in terms of approximation ratios and runtime for $p=1$ up to 10 nodes.", "relation_to_broader_scientific_literature": "The proposed method is improved over QAOA formulation of Weggemans et al. (2022).\n\nSPQAOA is specific to correlation clustering, but it would be great to see the possibility of other applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper was very clear to read the details.\nIntroduction of Quantum Alternating Operator Ansatz was done by the elegant description even for non-professionals on quantum information.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "If we consider the minimum disagreement formulation, will  we need a different techniques of QAOA considered in Max-Agree?\n\n\nCan we perform the case with larger depth $p$? Do we expect the performance becomes better? Is it prohibited due to computational resources?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: The paper presents a new quantum optimization approach called the Sub-Problem Quantum Alternating Operator Ansatz (SQAOA) aimed at solving correlation clustering (CC) problems, which present a new kind of problem that can be solved by the general family of QAOA.  It is a solid contribution. However,  the presentation could use extra efforts: in particular, it would be helpful to include more explanation and motivation for the CC problem, a broader literature review and a more thorough discussion of the classical computational limitation.
Decision: Accept (poster)