Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917518600306688 |
|---|---|
| author | Apte, Anuj Boulebnane, Sami Jin, Yuwei Omanakuttan, Sivaprasad Perlin, Michael A. Shaydulin, Ruslan |
| author_facet | Apte, Anuj Boulebnane, Sami Jin, Yuwei Omanakuttan, Sivaprasad Perlin, Michael A. Shaydulin, Ruslan |
| contents | Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05956 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut Apte, Anuj Boulebnane, Sami Jin, Yuwei Omanakuttan, Sivaprasad Perlin, Michael A. Shaydulin, Ruslan Quantum Physics Mathematical Physics Optimization and Control Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage. |
| title | Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut |
| topic | Quantum Physics Mathematical Physics Optimization and Control |
| url | https://arxiv.org/abs/2602.05956 |