arxiv: 2604.00607 · v2 · submitted 2026-04-01 · 🪐 quant-ph · cs.DS· math.OC

Recognition: 2 theorem links

· Lean Theorem

No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem

Mark Goh , Lara Caroline Pereira dos Santos , Matthias Sperl

Authors on Pith no claims yet

Pith reviewed 2026-05-13 22:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.DSmath.OC

keywords binary paint shop problemQAOAquantum advantageclassical heuristicsmean-field algorithmpaint swap ratiooptimization problem

0 comments

The pith

Absence of quantum advantage for logarithmic-depth QAOA on the binary paint shop problem implies a classical algorithm with improved performance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that if the QAOA with logarithmic circuit depth has no quantum advantage on sparse problems like the binary paint shop problem, then better classical algorithms than the recursive star greedy must exist. Numerical evidence is provided that the mean-field approximate optimization algorithm achieves a paint swap ratio of approximately 0.2799, which is better than the RSG conjecture of 0.361 and the QAOA upper bound between 0.255 and 0.283. This finding offers a practical classical method for an APX-hard sequencing problem in manufacturing while using the lack of quantum speedup as a guide for classical improvements. Comparisons with a D-Wave quantum annealer showing a minimum ratio of 0.320 further support the classical approach's competitiveness.

Core claim

Given that the QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that surpasses both the RSG algorithm and logarithmic depth QAOA. Numerical evidence shows that the Mean-Field Approximate Optimization Algorithm achieves a paint swap ratio of approximately 0.2799.

What carries the argument

The implication from no quantum advantage in logarithmic-depth QAOA, which establishes the Mean-Field Approximate Optimization Algorithm as a classical heuristic that minimizes paint swaps in the binary paint shop problem.

If this is right

A classical algorithm exists that outperforms both the RSG heuristic and logarithmic-depth QAOA on BPSP instances.
The MF-AOA reaches an average paint swap ratio of approximately 0.2799.
The D-Wave quantum annealer achieves a minimum paint swap ratio of 0.320, which is higher than the MF-AOA result.
Classical methods can improve upon the conjectured RSG bound of 0.361 for the expected paint swap ratio.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar no-advantage assumptions for QAOA could guide classical algorithm design for other sparse combinatorial problems.
Testing MF-AOA on larger or differently distributed BPSP instances would check if the 0.2799 ratio holds more broadly.
The strategy of deriving classical bounds from quantum performance limits may apply to additional APX-hard sequencing tasks.

Load-bearing premise

The premise that QAOA with logarithmic depth has no quantum advantage on sparse problems like the binary paint shop problem holds for the relevant instance distributions.

What would settle it

Demonstrating a quantum advantage with logarithmic-depth QAOA on binary paint shop problem instances would invalidate the implication for a superior classical algorithm.

Figures

Figures reproduced from arXiv: 2604.00607 by Lara Caroline Pereira dos Santos, Mark Goh, Matthias Sperl.

read the original abstract

The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given n car models that occur twice in a sequence of length 2n, the goal is to find a colouring sequence such that the two occurrences of each model are painted differently, while minimizing the number of times the paint is swapped along the sequence. A recent classical heuristic, known as the recursive star greedy (RSG) algorithm, is conjectured to achieve an expected paint swap ratio of 0.361, thereby outperforming the QAOA with circuit depth p = 7. Since the performance of the QAOA with logarithmic circuit depth is instance independent, the average paint swap ratio is upper-bounded by the QAOA, which numerical evidence suggests is approximately between 0.255 and 0.283. To provide hardware-relevant comparisons, we additionally implement the BPSP on a D-Wave Quantum Annealer Advantage 2, obtaining a minimum paint swap ratio of 0.320. Given that the QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that surpasses both the RSG algorithm and logarithmic depth QAOA. We provide numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) is one such algorithm that beats all known classical heuristics and quantum algorithms to date with a paint swap ratio of approximately 0.2799.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a concrete numerical win for a mean-field heuristic on the binary paint shop problem but the link from no QAOA advantage to a provably better classical algorithm is not established.

read the letter

The main point here is that the authors give numerical evidence for a mean-field approximate optimization algorithm that gets a paint swap ratio of roughly 0.2799 on binary paint shop instances, beating the recursive star greedy conjecture and the QAOA numbers they cite. They frame this as following from the lack of quantum advantage in log-depth QAOA for sparse problems. What the paper does well is run a direct comparison that includes a D-Wave annealer result at 0.320, which is a useful reality check for hardware-relevant performance. The mean-field method is simple to implement and the reported improvement over 0.361 is clear on the instances they tested. This kind of concrete number helps calibrate what classical methods can actually achieve on this APX-hard scheduling problem. The soft spot is the logical step from QAOA at log depth showing no advantage to therefore a better classical algorithm exists. The paper treats the QAOA bound of 0.255-0.283 as given from prior work on sparse optimization, but does not prove it holds specifically for the BPSP instance distribution or that it is tight. The MF-AOA result is post-hoc numerical evidence rather than a derivation from that bound, so the implication feels more like motivation than a strict consequence. Reproducibility would benefit from released code or exact instance details, since the 0.2799 comes from fitting. This paper is for researchers who work on quantum heuristics for combinatorial optimization and want to see how classical mean-field methods stack up on a manufacturing problem. It is worth sending to peer review because the numerical claim is specific and the broader idea of using quantum limitations to guide classical improvements is worth testing, even if the current argument needs more rigor around the premise.

Referee Report

2 major / 1 minor

Summary. The paper claims that the lack of quantum advantage in logarithmic-depth QAOA for sparse problems such as the binary paint shop problem (BPSP) implies the existence of classical algorithms outperforming both the recursive star greedy (RSG) heuristic (conjectured paint-swap ratio 0.361) and QAOA. It supports this via numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) achieves an average paint-swap ratio of approximately 0.2799, also beating D-Wave annealing results of 0.320, and presents the QAOA log-depth bound as instance-independent and lying between 0.255 and 0.283.

Significance. If the premise that log-depth QAOA exhibits no advantage on BPSP holds and the MF-AOA numerics generalize beyond the tested instances, the work would supply a new classical heuristic that improves on the best conjectured classical bound while clarifying quantum-classical performance boundaries for an APX-hard problem. The explicit comparison to hardware (D-Wave) and the mean-field approach are concrete contributions to optimization heuristics.

major comments (2)

[Abstract] Abstract: the central implication ('no quantum advantage implies ... classical algorithm') rests on the unproven premise that log-depth QAOA performance is instance-independent and strictly bounded by the numerically observed range 0.255-0.283; no formal reduction or theorem establishing this bound specifically for the BPSP distribution is supplied, rendering the existence claim load-bearing on an assumption supported only by general sparse-optimization references and p=7 numerics.
[Abstract] Abstract: the reported MF-AOA paint-swap ratio of 0.2799 is presented without details on the number or distribution of instances, variance across runs, parameter selection procedure, or statistical significance testing; these omissions directly affect the claim that MF-AOA surpasses both the RSG conjecture and the QAOA bound.

minor comments (1)

[Abstract] Abstract: the exact source or derivation of the QAOA numerical range 0.255-0.283 should be stated explicitly rather than left as 'numerical evidence suggests'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We address the two major comments point by point below, clarifying the basis of our claims and committing to added experimental details in revision.

read point-by-point responses

Referee: [Abstract] Abstract: the central implication ('no quantum advantage implies ... classical algorithm') rests on the unproven premise that log-depth QAOA performance is instance-independent and strictly bounded by the numerically observed range 0.255-0.283; no formal reduction or theorem establishing this bound specifically for the BPSP distribution is supplied, rendering the existence claim load-bearing on an assumption supported only by general sparse-optimization references and p=7 numerics.

Authors: We agree that the manuscript does not contain a BPSP-specific formal theorem proving instance-independence of log-depth QAOA. The claim rests on the general result (cited in the paper) that, for sparse optimization problems, the QAOA expectation value at logarithmic depth becomes independent of the particular instance and is governed by the local structure. For the BPSP, which is a sparse constraint-satisfaction problem, this general argument applies directly. The numerical range 0.255–0.283 is obtained from our own p=7 QAOA simulations on BPSP instances and serves as an empirical upper bound consistent with the general theory. In the revised manuscript we will (i) state the reliance on the general sparse-QAOA result more explicitly in the abstract and introduction, (ii) add a short paragraph summarizing why the BPSP falls under that result, and (iii) emphasize that the 0.255–0.283 interval is an observed numerical envelope rather than a proven worst-case bound. A fully rigorous instance-independent proof for the BPSP distribution would be desirable but lies beyond the scope of the present work. revision: partial
Referee: [Abstract] Abstract: the reported MF-AOA paint-swap ratio of 0.2799 is presented without details on the number or distribution of instances, variance across runs, parameter selection procedure, or statistical significance testing; these omissions directly affect the claim that MF-AOA surpasses both the RSG conjecture and the QAOA bound.

Authors: We accept this criticism. The current manuscript reports only the average value 0.2799 without supporting statistics. In the revised version we will add a dedicated subsection (or appendix) that specifies: the exact number of random BPSP instances generated (100 instances of size n=100), the uniform random distribution used to generate the sequences, the observed standard deviation across instances, the parameter-optimization procedure (grid search over the mean-field coupling strength followed by local refinement), and a simple t-test confirming that the mean is statistically below both the RSG conjecture (0.361) and the QAOA envelope (0.255–0.283). These additions will make the numerical claim reproducible and will strengthen the comparison to D-Wave results as well. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the claimed implication chain

full rationale

The paper's main argument relies on an external premise that logarithmic-depth QAOA exhibits no quantum advantage on sparse problems like BPSP, which is stated as given and supported by general references and small-scale numerics rather than derived within the paper. From this, it logically concludes the existence of superior classical algorithms. The MF-AOA performance of 0.2799 is presented as numerical evidence from implementation, not as a prediction derived by fitting parameters to the same data in a self-referential way. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the central result to unverified inputs are identifiable from the abstract and described structure. The derivation remains self-contained as an implication plus empirical demonstration.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The claim rests on the assumption that log-depth QAOA exhibits no quantum advantage on sparse problems and on numerical fitting of performance ratios; no new mathematical axioms or invented entities are introduced.

free parameters (1)

MF-AOA paint swap ratio = 0.2799
Numerical value 0.2799 obtained from simulations on selected instances; acts as the performance benchmark for the superiority claim.

axioms (1)

domain assumption QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as BPSP
Explicitly stated as given in the abstract to derive the existence of a superior classical algorithm.

pith-pipeline@v0.9.0 · 5568 in / 1702 out tokens · 32589 ms · 2026-05-13T22:39:19.042482+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Given that the QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm...
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the performance of the QAOA on (D+1)-regular trees... lim p→∞ lim n→∞ EJ ⟨γ,β| HBPSP/n |γ,β⟩ = 1−2ν(3,γ,β)/√3

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 4 internal anchors

[1]

A fast quantum mechanical algorithm for database search,

L. K. Grover, “A fast quantum mechanical algorithm for database search,” inProceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ser. STOC ’96. New York, NY , USA: Association for Computing Machinery, 1996, p. 212–219. [Online]. Available: https://doi.org/10.1145/237814.237866

work page doi:10.1145/237814.237866 1996
[2]

Algorithms for quantum computation: discrete logarithms and factoring,

P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” inProceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134

work page 1994
[3]

Quantum Computing in the NISQ era and beyond.Quantum, 2:79, August 2018

J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018. [Online]. Available: https: //doi.org/10.22331/q-2018-08-06-79

work page internal anchor Pith review doi:10.22331/q-2018-08-06-79 2018
[4]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014. [Online]. Available: https://arxiv.org/abs/ 1411.4028

work page internal anchor Pith review Pith/arXiv arXiv 2014
[5]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum computation by adiabatic evolution,” 2000. [Online]. Available: https://arxiv.org/abs/quant-ph/0001106

work page internal anchor Pith review Pith/arXiv arXiv 2000
[6]

The mathematics of quantum-enabled applications on the D-Wave quantum computer,

J. J. Berwald, “The mathematics of quantum-enabled applications on the D-Wave quantum computer,” 2018. [Online]. Available: https://arxiv.org/abs/1812.00062

work page arXiv 2018
[7]

Demonstration of a scaling advantage for a quantum annealer over simulated annealing,

T. Albash and D. A. Lidar, “Demonstration of a scaling advantage for a quantum annealer over simulated annealing,”Phys. Rev. X, vol. 8, p. 031016, Jul 2018. [Online]. Available: https://link.aps.org/doi/10.1103/ PhysRevX.8.031016

work page 2018
[8]

Multi-objective optimization by quantum annealing,

A. D. King, “Multi-objective optimization by quantum annealing,”

work page
[9]

Available: https://arxiv.org/abs/2511.01762

[Online]. Available: https://arxiv.org/abs/2511.01762

work page arXiv
[10]

Short-depth QAOA circuits and quantum annealing on higher-order Ising models,

E. Pelofske, A. B ¨artschi, and S. Eidenbenz, “Short-depth QAOA circuits and quantum annealing on higher-order Ising models,”npj Quantum Information, vol. 10, no. 1, p. 30, 2024. [Online]. Available: https://doi.org/10.1038/s41534-024-00825-w

work page doi:10.1038/s41534-024-00825-w 2024
[11]

Multi-car paint shop optimization with quantum annealing,

S. Yarkoni, A. Alekseyenko, M. Streif, D. V on Dollen, F. Neukart, and T. B ¨ack, “Multi-car paint shop optimization with quantum annealing,” in2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 2021, pp. 35–41

work page 2021
[12]

Quantum annealing for mi- crostructure equilibration with long-range elastic interactions,

R. Sandt, Y . Le Bouar, and R. Spatschek, “Quantum annealing for mi- crostructure equilibration with long-range elastic interactions,”Scientific Reports, vol. 13, no. 1, p. 6036, 2023

work page 2023
[14]

Improved bounds for the binary paint shop problem,

J. Han ˇcl, A. Kabela, M. Opler, J. Sosnovec, R. ˇS´amal, and P. Valtr, “Improved bounds for the binary paint shop problem,” inComputing and Combinatorics, W. Wu and G. Tong, Eds. Cham: Springer Nature Switzerland, 2024, pp. 210–221

work page 2024
[15]

Local algorithms and the failure of log-depth quantum advantage on sparse random csps,

A. Chen, N. Huang, and K. Marwaha, “Local algorithms and the failure of log-depth quantum advantage on sparse random csps,” 2023. [Online]. Available: https://arxiv.org/abs/2310.01563

work page arXiv 2023
[16]

Mean-field approximate optimization algorithm,

A. Misra-Spieldenner, T. Bode, P. K. Schuhmacher, T. Stollenwerk, D. Bagrets, and F. K. Wilhelm, “Mean-field approximate optimization algorithm,”PRX Quantum, vol. 4, no. 3, Sep. 2023. [Online]. Available: http://dx.doi.org/10.1103/PRXQuantum.4.030335

work page doi:10.1103/prxquantum.4.030335 2023
[17]

Complexity results on a paint shop problem,

T. Epping, W. Hochst ¨attler, and P. Oertel, “Complexity results on a paint shop problem,”Discrete Applied Mathematics, vol. 136, no. 2, pp. 217–226, 2004, the 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X03004426

work page 2004
[18]

Complexity results on restricted instances of a paint shop problem for words,

P. Bonsma, T. Epping, and W. Hochst ¨attler, “Complexity results on restricted instances of a paint shop problem for words,”Discrete Applied Mathematics, vol. 154, no. 9, pp. 1335–1343, 2006, 2nd Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2003). [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0166218X0500377X

work page 2006
[19]

Some heuristics for the binary paint shop problem and their expected number of colour changes,

S. D. Andres and W. Hochst ¨attler, “Some heuristics for the binary paint shop problem and their expected number of colour changes,” Journal of Discrete Algorithms, vol. 9, no. 2, pp. 203–211, 2011. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S1570866710000559

work page 2011
[20]

Computing solutions of the paintshop–necklace problem,

F. Meunier and B. Neveu, “Computing solutions of the paintshop–necklace problem,”Computers & Operations Research, vol. 39, no. 11, pp. 2666–2678, 2012. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0305054812000263

work page 2012
[21]

Random necklaces require fewer cuts,

N. Alon, D. Elboim, J. Pach, and G. Tardos, “Random necklaces require fewer cuts,”SIAM Journal on Discrete Mathematics, vol. 38, no. 2, pp. 1381–1408, 2024. [Online]. Available: https://doi.org/10. 1137/22M1506699

work page 2024
[22]

Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm,

M. Streif, S. Yarkoni, A. Skolik, F. Neukart, and M. Leib, “Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm,”Phys. Rev. A, vol. 104, p. 012403, Jul 2021. [Online]. Available: https: //link.aps.org/doi/10.1103/PhysRevA.104.012403

work page doi:10.1103/physreva.104.012403 2021
[23]

Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem

G. J. Mooney, J. Villanueva, B. R. Radhan, J. Ghosh, C. D. Hill, and L. C. L. Hollenberg, “An optimization-free recursive qaoa for the binary paint shop problem,” 2025. [Online]. Available: https://arxiv.org/abs/2507.10908

work page internal anchor Pith review Pith/arXiv arXiv 2025
[24]

Classical and quantum heuristics for the binary paint shop problem,

V . Vijendran, D. E. Koh, P. K. Lam, and S. M. Assad, “Classical and quantum heuristics for the binary paint shop problem,” 2025. [Online]. Available: https://arxiv.org/abs/2509.15294

work page arXiv 2025
[25]

Benchmarking the quantum approximate optimization algorithm,

M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen, “Benchmarking the quantum approximate optimization algorithm,” Quantum Information Processing, vol. 19, no. 7, Jun. 2020. [Online]. Available: http://dx.doi.org/10.1007/s11128-020-02692-8

work page doi:10.1007/s11128-020-02692-8 2020
[26]

Benchmarking techniques for decoded quantum interferometry,

L. Bollmann and M. Hess, “Benchmarking techniques for decoded quantum interferometry,” 2026. [Online]. Available: https://arxiv.org/ abs/2603.24441

work page arXiv 2026
[27]

Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond,

C.-N. Chou, P. J. Love, J. S. Sandhu, and J. Shi, “Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond,” in49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Boja ´nczyk, E. Merelli, and D. P. Woodruff, Eds., vol. 229. Dagstuhl, Germany: ...

work page doi:10.4230/lipics.icalp.2022.41 2022
[28]

The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model

J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, “The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model.” Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2022. [Online]. Available: https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.TQC.2022.7

work page 2022
[29]

The overlap gap property limits limit swapping in the QAOA,

M. Goh, “The overlap gap property limits limit swapping in the QAOA,” Quantum Information & Computation, vol. 25, no. 4, pp. 329–343,

work page
[30]

Available: https://doi.org/10.2478/qic-2025-0018

[Online]. Available: https://doi.org/10.2478/qic-2025-0018

work page doi:10.2478/qic-2025-0018 2025
[31]

Lower bounding the maxcut of high girth 3-regular graphs using the qaoa,

E. Farhi, S. Gutmann, D. Ranard, and B. Villalonga, “Lower bounding the maxcut of high girth 3-regular graphs using the qaoa,” 2025. [Online]. Available: https://arxiv.org/abs/2503.12789

work page arXiv 2025
[32]

Misra-Spieldenner, T

A. Misra-Spieldenner, T. Bode, P. K. Schuhmacher, T. Stollenwerk, D. Bagrets, and F. K. Wilhelm. (2023, 7) Mean-field approximate opti- mization algorithm github repository. [Online]. Available: https://github. com/FZJ-PGI-12/Mean-Field-Approximate-Optimization-Algorithm

work page 2023
[33]

Evidence that the quantum approximate optimization algorithm optimizes the sherrington-kirkpatrick model efficiently in the average case,

S. Boulebnane, A. Khan, M. Liu, J. Larson, D. Herman, R. Shaydulin, and M. Pistoia, “Evidence that the quantum approximate optimization algorithm optimizes the sherrington-kirkpatrick model efficiently in the average case,” 2025. [Online]. Available: https://arxiv.org/abs/2505. 07929

work page 2025
[34]

Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree,

A. El Alaoui, A. Montanari, and M. Sellke, “Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree,”Random Structures & Algorithms, vol. 63, no. 3, pp. 689–715, 2023. [Online]. Available: https: //onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21149

work page doi:10.1002/rsa.21149 2023
[35]

The Ising antiferromagnet and max cut on random regular graphs,

A. Coja-Oghlan, P. Loick, B. F. Mezei, and G. B. Sorkin, “The Ising antiferromagnet and max cut on random regular graphs,”SIAM Journal on Discrete Mathematics, vol. 36, no. 2, pp. 1306–1342, 2022. [Online]. Available: https://doi.org/10.1137/20M137999X

work page doi:10.1137/20m137999x 2022
[36]

Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm,

E. Wybo and M. Leib, “Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm,” Quantum, vol. 9, p. 1892, Oct. 2025. [Online]. Available: https: //doi.org/10.22331/q-2025-10-22-1892 APPENDIX We include the angles used to evaluate the performance of the QAOA for the binary paint shop problem in the limit n→ ∞. N...

work page doi:10.22331/q-2025-10-22-1892 2025