Research map / Learning theory and algorithms / Clustering
A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SQAOA, a QAOA generalization for correlation clustering that uses nucleus sampling for the expected cost and splits the problem into sequential max-cut sub-problems, each solved by QAOA.
Problem
Applying QAOA to correlation clustering is hard because the clustering constraints are difficult to encode in the ansatz's mixer and the multi-level qudit formulation needs many qubits and is costly to simulate.
Approach
Model correlation clustering as iterated max-cut sub-problems, each solved by a QAOA-style circuit on one qubit per remaining node, measuring after each sub-problem so qubits are reused; combine with nucleus (top-p) sampling when computing the expected cost.
Key results
- On Erdős-Rényi graphs with n=3-5 at p=1, SQAOA with t=0.1 reaches approximation ratios of 1.00 (n=3), 1.00±0.02 (n=4), 1.00±0.02 (n=5), versus 1.00, 1.00, 1.00 for multi-level QAOA with t=0.1.
- SQAOA with t=0.1 at p=1 runs in 2±1 s (n=3), 6±2 s (n=4), 10±5 s (n=5) versus 5, 15, 109 s for multi-level QAOA with t=0.1 on Erdős-Rényi graphs.
- Theoretically, for p→∞ there exist parameters such that SQAOA yields an optimal solution with certainty, proven via a Lie-algebra universality argument when a node-weight term is included.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use nucleus sampling with t=0.1 instead of t=1 (ablation) | QAOA · Erdős-Rényi graphs, n=3–5 | approximation ratio: 0.97 ± 0.04 -> 1.00 ± 0.00; 0.92 ± 0.07 -> 1.00 ± 0.00; 0.92 ± 0.07 -> 1.00 ± 0.01 | Helped |
| Use nucleus sampling with t=0.1 instead of t=1 (ablation) | SQAOA · Erdős-Rényi graphs, n=3–5 | approximation ratio: 0.94 ± 0.08 -> 1.00 ± 0.00; 0.88 ± 0.09 -> 1.00 ± 0.02; 0.85 ± 0.10 -> 1.00 ± 0.02 | Helped |
| Use nucleus sampling with t=0.1 instead of t=1 (ablation) | QAOA · Erdős-Rényi graphs, n=3–5 | runtime [s]: 121 ± 40 -> 5 ± 0; 221 ± 30 -> 15 ± 2; 316 ± 44 -> 109 ± 32 | Helped |
| Use nucleus sampling with t=0.1 instead of t=1 (ablation) | SQAOA · Erdős-Rényi graphs, n=3–5 | runtime [s]: 23 ± 12 -> 2 ± 1; 161 ± 45 -> 6 ± 2; 799 ± 256 -> 10 ± 5 | Helped |
| Use SQAOA instead of QAOA, both with t=0.1 | Correlation clustering · Erdős-Rényi graphs, n=3–5 | approximation ratio: 1.00 ± 0.00 vs 1.00 ± 0.00; 1.00 ± 0.00 vs 1.00 ± 0.02; 1.00 ± 0.01 vs 1.00 ± 0.02 | Mixed |
| Use SQAOA instead of QAOA, both with t=0.1 | Correlation clustering · Erdős-Rényi graphs, n=3–5 | runtime [s]: 5 ± 0 vs 2 ± 1; 15 ± 2 vs 6 ± 2; 109 ± 32 vs 10 ± 5 | Helped |
Surprising findings
- With threshold t=1 (no nucleus truncation), SQAOA performs slightly worse than multi-level QAOA, but with t=0.1 it outperforms it in runtime.
- Lowering the nucleus threshold reduced QAOA runtime in general, but for QAOA at 5 nodes t=0.5 took significantly longer than t=1.
Limitations
- Theoretical optimality guarantee only proven when including an additional node-weight term; pairwise-only mixer case unresolved.
- Experiments limited to graphs with up to 10 nodes; runtime still grows exponentially with size.
- No lower bound on approximation ratio is provided; same operators are reused across all sub-problems.
Experimental setup
Datasets: synthetic complete graphs synthetic Erdős-Rényi graphs (edge probability 0.5)
Benchmarks: synthetic complete graphs (n=3-10) synthetic Erdős-Rényi graphs (n=3-10)
Metrics: approximation ratio runtime (s) nucleus size function evaluations
Baselines: multi-level QAOA (Weggemans et al. 2022) Swamy bound
Builds on: QAOA nucleus sampling multi-level QAOA for correlation clustering universality of QAOA (Morales et al. 2020)
Closest papers by meaning
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.87)
- Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.86)
- Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing (CVPR 2024 · similarity 0.85)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.84)
- Topological data analysis on noisy quantum computers (ICLR 2024 · similarity 0.84)
- Q-MAML: Quantum Model-Agnostic Meta-Learning for Variational Quantum Algorithms (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.