pith. sign in

arxiv: 2507.10908 · v2 · submitted 2025-07-15 · 🪐 quant-ph

Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem

Gary J Mooney , Jedwin Villanueva , Bhaskar Roy Radhan , Joydip Ghosh , Charles D Hill , Lloyd C L Hollenberg This is my paper

Pith reviewed 2026-05-19 04:20 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QAOARQAOABinary Paint Shop Problemparameter transferquantum optimizationMAX-CUTIsing modelrecursive algorithms
0
0 comments X p. Extension

The pith

Recursive QAOA solves the binary paint shop problem near-optimally using transferred parameters without any variational optimization.

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

The paper establishes that recursive QAOA, when combined with parameter transfer from smaller instances, delivers near-optimal solutions to the binary paint shop problem while avoiding the classical optimization loop entirely. This works because the problem maps to a symmetric local MAX-CUT Hamiltonian that tolerates inexact parameters well. A sympathetic reader would care because it removes the main practical barrier of barren plateaus and high classical overhead in variational quantum algorithms, opening a path to larger instances on near-term hardware. The work benchmarks this approach against standard QAOA and classical solvers, showing reduced circuit sizes and measurement counts with little loss in solution quality.

Core claim

By formulating the binary paint shop problem as an Ising ground-state task equivalent to MAX-CUT and applying recursive QAOA with parameters transferred across problem sizes, the algorithm maintains solution quality comparable to fully optimized QAOA while using substantially smaller circuits and fewer measurements; the method trims outer gates via reverse causal cones and remains robust when parameters deviate from their optimal values.

What carries the argument

Recursive QAOA with parameter transfer, which iteratively reduces problem size by fixing variables and reuses variational parameters from smaller instances to eliminate the classical optimization loop.

If this is right

  • RQAOA maintains near-optimal performance even when parameters are transferred rather than optimized for the target instance.
  • Quantum resource costs drop markedly compared with standard QAOA because recursion shortens circuits and reduces the number of measurements required.
  • The approach bypasses the barren-plateau issue that normally forces expensive classical optimization in variational quantum algorithms.
  • The same parameter-transfer strategy applies directly to other MAX-CUT-type problems with symmetric local Hamiltonians.

Where Pith is reading between the lines

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

  • This technique could be tested on other manufacturing or scheduling problems whose Hamiltonians share the same local symmetry.
  • Parameter transfer might allow quantum optimization to scale beyond the size where classical optimizers fail due to noise or barren plateaus.
  • Hybrid classical-quantum pipelines could combine this method with fast classical heuristics to refine solutions after the quantum step.

Load-bearing premise

The binary paint shop problem's Hamiltonian has enough symmetric local structure that parameters from smaller instances remain effective when applied to larger ones.

What would settle it

Apply the optimization-free recursive QAOA to a binary paint shop instance of size 50 using parameters transferred from a size-10 instance and measure whether the fraction of color changes deviates by more than 5 percent from the value obtained with instance-specific optimization.

Figures

Figures reproduced from arXiv: 2507.10908 by Bhaskar Roy Radhan, Charles D Hill, Gary J Mooney, Jedwin Villanueva, Joydip Ghosh, Lloyd C L Hollenberg.

Figure 1
Figure 1. Figure 1: FIG. 1. A diagram of the quantum approximate optimisation [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. An example of the binary paint shop problem (BPSP) consisting of a sequence of 8 car instances and 4 body types. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. An example of the reverse causal cone (RCC) for a line Ising graph QAOA circuit. The [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. A graphic highlighting the RQAOA reduction process. Eliminating variables by choosing edge correlations to round [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The data was obtained from Streif et. al. [27], which uses the approach presented in [28]. We include the values here [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Plots showing the effect on performance caused by deviations of QAOA parameters away from optimal. The data are [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Quantum resource requirements for QAOA Reverse Causal Cone (RCC) and full circuits. The plots compare the circuit [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. The number of circuits used for each quantum algorithm. The algorithms compared are the precomputed-parameter [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. Resource usages for 1D Matrix Product State (MPS) simulations of QAOA circuits with and without Reverse Causal [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
read the original abstract

The Quantum Approximate Optimisation Algorithm (QAOA) is a leading candidate for near-term quantum advantage, yet its practical impact is hindered by limited performance on symmetric local Hamiltonians and the costly optimisation of variational parameters. The Recursive-QAOA (RQAOA) introduced by Bravyi et al. Phys. Rev. Lett. (2020), addresses the first limitation while also reducing circuit size, and parameter transfer techniques can be used to effectively bypass the optimisation loop. In this work, we combine these two ideas to develop an optimisation-free RQAOA and evaluate its performance on the Binary Paint Shop Problem (BPSP) -- an optimisation problem found in manufacturing where a sequence of cars must be painted under constraints while minimising the number of colour changes. The BPSP can be formulated as an Ising ground state problem with a symmetric local Hamiltonian in the form of MAX-CUT and properties well-suited for the application of QAOA parameter transfer. We benchmark QAOA and RQAOA with parameter transfer against classical solvers and heuristics, and investigate their resilience to suboptimal parameters. For circuit optimisation, we use reverse causal cones (RCC) and introduce a method of trimming outer two-qubit gates. To estimate the classical resources needed to simulate these quantum algorithms, we compute entanglement entropy and bond dimensions using matrix product state methods. We also compare circuit sizes and measurement counts across implementations. Our results show that RQAOA is inherently robust to parameter deviations, maintaining near-optimal solutions without noticeable degradation under parameter transfer while substantially reducing quantum resource requirements compared to QAOA. This highlights a viable route toward scalable quantum optimisation without the overhead of the classical optimisation loop and its challenges with barren plateaus.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes combining Recursive QAOA (RQAOA) with parameter-transfer techniques to create an optimisation-free variant, and evaluates it on the Binary Paint Shop Problem (BPSP) formulated as a MAX-CUT-like Ising Hamiltonian. It reports that RQAOA with transferred parameters remains near-optimal across recursion depths, substantially reduces circuit size and measurement overhead relative to standard QAOA, and demonstrates resilience to parameter deviations. Resource estimates are obtained via matrix-product-state calculations of entanglement entropy and bond dimension; circuit optimisation employs reverse causal cones together with a new outer-gate trimming procedure. Benchmarks against classical solvers and heuristics are included.

Significance. If the central empirical claims hold, the work supplies a concrete route to bypass the classical optimisation loop and its barren-plateau issues for at least one industrially relevant problem class, while quantifying the resulting quantum-resource savings. The use of MPS-based entanglement diagnostics and the introduction of outer-gate trimming are concrete technical contributions that could be reused elsewhere.

major comments (2)
  1. [Results on recursion depths] Results section (around the recursion-depth experiments): the central claim that transferred parameters remain near-optimal at every recursion depth rests on the assumption that the reduced Hamiltonians retain the symmetric local MAX-CUT structure of the original BPSP instance. No explicit verification—e.g., computation of the same symmetry measures or transferability metrics on the reduced instances—is reported. This is load-bearing for the robustness conclusion.
  2. [Benchmark tables/figures] Benchmark tables and figures: the reported performance advantages of RQAOA with parameter transfer are presented without error bars, without the number of independent instances or random seeds, and without statistical comparison to the classical baselines. This weakens the quantitative claim of “no noticeable degradation” and “substantially reducing quantum resource requirements.”
minor comments (2)
  1. [Methods] The description of the outer-gate trimming procedure would benefit from an explicit pseudocode or circuit diagram showing which gates are removed at each step.
  2. [Resource estimation] A short comparison table of circuit depth and CNOT count before and after RCC + trimming would make the resource-saving claim easier to assess at a glance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive comments. We address each major comment below and describe the revisions we intend to incorporate.

read point-by-point responses

  1. Referee: [Results on recursion depths] Results section (around the recursion-depth experiments): the central claim that transferred parameters remain near-optimal at every recursion depth rests on the assumption that the reduced Hamiltonians retain the symmetric local MAX-CUT structure of the original BPSP instance. No explicit verification—e.g., computation of the same symmetry measures or transferability metrics on the reduced instances—is reported. This is load-bearing for the robustness conclusion.

    Authors: We appreciate the referee pointing out this load-bearing assumption. The recursive reduction procedure in RQAOA is constructed to eliminate variables while preserving the local interaction structure of the original BPSP Ising Hamiltonian; however, we agree that an explicit check on the reduced instances would strengthen the robustness argument. In the revised manuscript we will add a short subsection (or supplementary figure) that computes the same symmetry measures and transferability metrics on the reduced Hamiltonians at successive recursion depths, thereby directly verifying that the symmetric local MAX-CUT character is retained. revision: yes

  2. Referee: [Benchmark tables/figures] Benchmark tables and figures: the reported performance advantages of RQAOA with parameter transfer are presented without error bars, without the number of independent instances or random seeds, and without statistical comparison to the classical baselines. This weakens the quantitative claim of “no noticeable degradation” and “substantially reducing quantum resource requirements.”

    Authors: We acknowledge that the current presentation of the benchmark results omits important statistical information. In the revised version we will (i) report the exact number of independent BPSP instances and random seeds used, (ii) add error bars (standard error of the mean) to all relevant tables and figures, and (iii) include a brief statistical comparison (e.g., paired t-tests or Wilcoxon tests with p-values) against the classical baselines. These additions will provide quantitative support for the statements of “no noticeable degradation” and resource savings. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical benchmarks are self-contained

full rationale

The paper evaluates an optimisation-free RQAOA variant on the Binary Paint Shop Problem by combining the external RQAOA construction from Bravyi et al. (2020) with parameter transfer techniques. All reported performance claims, including robustness to parameter deviations and resource reductions, rest on direct numerical benchmarks against classical solvers, entanglement entropy calculations via matrix product states, and circuit-size comparisons. No derivation step equates a fitted quantity to a prediction by construction, no self-citation is load-bearing for the central empirical result, and the Hamiltonian symmetry is invoked only as motivation for applying known transfer methods rather than as a self-defined property. The work is therefore self-contained against external benchmarks and prior literature.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only view yields minimal explicit ledger entries; the central claim rests on standard domain assumptions about Hamiltonian structure and parameter transfer suitability rather than new postulates.

axioms (1)
  • domain assumption The Binary Paint Shop Problem admits an Ising formulation as a symmetric local MAX-CUT Hamiltonian well-suited for QAOA parameter transfer.
    Directly stated in the abstract as the basis for applying the method.

pith-pipeline@v0.9.0 · 5853 in / 1193 out tokens · 60937 ms · 2026-05-19T04:20:42.868853+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    quant-ph 2026-04 unverdicted novelty 5.0

    Absence of quantum advantage for log-depth QAOA on the binary paint shop problem implies a classical mean-field algorithm achieving a paint-swap ratio of approximately 0.2799, outperforming known heuristics and quantu...

Reference graph

Works this paper leans on

70 extracted references · 70 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    Reverse-Causal Cones (RCCs) The RQAOA allows us to avoid needing to prepare the full ansatz state. This is because RQAOA only needs to know the largest correlation magnitude between each ad- jacent pair of qubits to round a correlation to±1 when reducing the graph and the parameterized ansatz state can be optimised at each reduction step by calculating th...

    work page

  2. [2]

    Trimming RCC Outer Two-Qubit Gates In cases when the RCC’s first layer includes qubits that are not included in the second layer, these extra qubits and the gates that connect them can be replaced with noise gates applied to remaining qubits that neighbour the removed ones. To mimic the effects of depolarising noise, a noise gate can be implemented on a q...

    work page

  3. [3]

    worst value

    Approximation Measure To compare methods fairly, we aim for a measure of approximation quality that is independent of problem in- stance and preferably independent of the objective func- tion’s properties, such as whether higher values are bet- ter or whether the values span positive and negative val- ues. To keep comparisons simple, we construct a measur...

    work page

  4. [4]

    Then, iterating through the sequence, each unassigned car is assigned the same colour as the previous car in the sequence

    Greedy Heuristic Thefirstcarinthesequenceisassignedred(whichcon- sequently assigns blue to its paired car). Then, iterating through the sequence, each unassigned car is assigned the same colour as the previous car in the sequence. For example, Ω(S) → { , , , , , , , } → { , , , , , , , } → { , , , , , , , } → { , , , , , , , }, resulting in a colour chang...

    work page

  5. [5]

    Each pair’s colours are assigned to minimise the number of colour changes directly after they are added

    Recursive Greedy Heuristic Each car body pair is added to the sequence one by one, in the same order they appear in the problem car se- quence. Each pair’s colours are assigned to minimise the number of colour changes directly after they are added. For example, Ω(S) → { , } → { , , , } → { , , , , , } → { , , , , , , , }, resulting in a colour change coun...

    work page

  6. [6]

    BPSP Precomp

    NumPy Minimum Eigensolver This algorithm is used to find exact solutions to the BPSP. By first mapping the BPSP instance to an Ising Hamiltonian, using the method shown in Section IIC, the algorithm uses an eigensolver to find the eigenvector with the smallest eigenvalue, which corresponds to the minimum number of colour changes. For diagonal Hamil- tonia...

    work page

  7. [7]

    Obstacles to variational quantum opti- mization from symmetry protection

    Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum opti- mization from symmetry protection. Physical Review Letters, 125(26):260505, 2020

    work page 2020

  8. [8]

    Quantum computing in the NISQ era and beyond

    John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018

    work page 2018

  9. [9]

    Benchmarking the performance of portfolio opti- mization with QAOA.Quantum Information Processing, 22(1):25, 2022

    Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, et al. Benchmarking the performance of portfolio opti- mization with QAOA.Quantum Information Processing, 22(1):25, 2022

    work page 2022

  10. [10]

    An investigation of IBM quantum computing device performance on combinatorial optimi- sation problems

    Maxine T Khumalo, Hazel A Chieza, Krupa Prag, and Matthew Woolway. An investigation of IBM quantum computing device performance on combinatorial optimi- sation problems. Neural Computing and Applications, pages 1–16, 2022

    work page 2022

  11. [11]

    Beat- ing classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm

    Michael Streif, Sheir Yarkoni, Andrea Skolik, et al. Beat- ing classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm. Physical Review A, 104(1):012403, 2021

    work page 2021

  12. [12]

    Improving variational quantum optimiza- tion using CVaR.Quantum, 4:256, 2020

    Panagiotis Kl Barkoutsos, Giacomo Nannicini, Anton Robert, et al. Improving variational quantum optimiza- tion using CVaR.Quantum, 4:256, 2020

    work page 2020

  13. [13]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  14. [14]

    A review on quantum approximate optimization algorithm and its variants.Physics Reports, 1068:1–66, 2024

    Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Sum- mer. A review on quantum approximate optimization algorithm and its variants.Physics Reports, 1068:1–66, 2024

    work page 2024

  15. [15]

    Challenges and opportuni- ties in quantum optimization

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportuni- ties in quantum optimization. Nature Reviews Physics, pages 1–18, 2024

    work page 2024

  16. [16]

    Algorithms for quantum computation: discrete logarithms and factoring

    Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994

    work page 1994

  17. [17]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996

    work page 1996

  18. [18]

    Exper- imental analysis of heuristics for the ATSP.The travel- ing salesman problem and its variations, pages 445–487, 2007

    David S Johnson, Gregory Gutin, Lyle A McGeoch, An- dersYeo, WeixiongZhang, andAlexeiZverovitch. Exper- imental analysis of heuristics for the ATSP.The travel- ing salesman problem and its variations, pages 445–487, 2007

    work page 2007

  19. [19]

    Chained Lin-Kernighan for large traveling salesman problems

    David Applegate, William Cook, and André Rohe. Chained Lin-Kernighan for large traveling salesman problems. Informs journal on computing, 15(1):82–92, 2003

    work page 2003

  20. [20]

    An effective implementation of the Lin– Kernighantravelingsalesmanheuristic

    Keld Helsgaun. An effective implementation of the Lin– Kernighantravelingsalesmanheuristic. European journal of operational research, 126(1):106–130, 2000

    work page 2000

  21. [21]

    Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

    Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753–782, 1998

    work page 1998

  22. [22]

    The traveling salesman problem: a case study in local optimization

    David S Johnson and Lyle A Mcgeoch. The traveling salesman problem: a case study in local optimization. John Wiley and Sons, 1995

    work page 1995

  23. [23]

    Data structures for traveling salesmen

    Michael L Fredman, David S Johnson, Lyle A McGeoch, and Gretchen Ostheimer. Data structures for traveling salesmen. Journal of Algorithms, 18(3):432–479, 1995

    work page 1995

  24. [24]

    Connecting ansatz expressibility to gradient magnitudes and barren plateaus

    Zoë Holmes, Kunal Sharma, Marco Cerezo, and Patrick J Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum, 3(1):010313, 2022

    work page 2022

  25. [25]

    Noise-induced barren plateaus in variational quantum al- gorithms

    Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum al- gorithms. Nature communications, 12(1):1–11, 2021

    work page 2021

  26. [26]

    Barren plateaus in quantum neural network training landscapes.Nature communications, 9(1):1–6, 2018

    Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes.Nature communications, 9(1):1–6, 2018

    work page 2018

  27. [27]

    Environment-aware production scheduling for paint shops in automobile manufacturing: A multi- objective optimization approach

    Rui Zhang. Environment-aware production scheduling for paint shops in automobile manufacturing: A multi- objective optimization approach. International Journal of Environmental Research and Public Health, 15(1):32, 2018

    work page 2018

  28. [28]

    Complexity results on restricted instances of a paint shop problem for words.Discrete Applied Mathematics, 154(9):1335–1343, 2006

    P Bonsma, Th Epping, and Winfried Hochstättler. Complexity results on restricted instances of a paint shop problem for words.Discrete Applied Mathematics, 154(9):1335–1343, 2006

    work page 2006

  29. [29]

    Paintshop, odd cy- cles and necklace splitting.Discrete Applied Mathemat- ics, 157(4):780–793, 2009

    Frédéric Meunier and András Sebő. Paintshop, odd cy- cles and necklace splitting.Discrete Applied Mathemat- ics, 157(4):780–793, 2009

    work page 2009

  30. [30]

    Some simplified NP-complete problems

    Michael R Garey, David S Johnson, and Larry Stock- meyer. Some simplified NP-complete problems. InPro- ceedings of the sixth annual ACM symposium on Theory of computing, pages 47–63, 1974

    work page 1974

  31. [31]

    The fixed angle conjecture for QAOA on regular MaxCut graphs.arXiv preprint arXiv:2107.00677, 2021

    Jonathan Wurtz and Danylo Lykov. The fixed angle conjecture for QAOA on regular MaxCut graphs.arXiv preprint arXiv:2107.00677, 2021

    work page arXiv 2021

  32. [32]

    Ex- pectation values from the single-layer quantum approxi- mate optimization algorithm on Ising problems.Quan- tum Science and Technology, 7(4):045036, 2022

    AsierOzaeta, WimvanDam, andPeterLMcMahon. Ex- pectation values from the single-layer quantum approxi- mate optimization algorithm on Ising problems.Quan- tum Science and Technology, 7(4):045036, 2022

    work page 2022

  33. [33]

    Beating classical heuristics for the binary paint shop problem with the quantum ap- proximate optimization algorithm

    Michael Streif, Sheir Yarkoni, Andrea Skolik, Florian Neukart, and Martin Leib. Beating classical heuristics for the binary paint shop problem with the quantum ap- proximate optimization algorithm. Physical Review A, 104(1):012403, 2021

    work page 2021

  34. [34]

    Training the quantum approximate optimization algorithm without access to a quantum processing unit

    Michael Streif and Martin Leib. Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Science and Tech- nology, 5(3):034008, 2020

    work page 2020

  35. [35]

    QAOAKit: A toolkit for re- producible study, application, and verification of the QAOA

    Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C Lotshaw. QAOAKit: A toolkit for re- producible study, application, and verification of the QAOA. In2021 IEEE/ACM Second International Work- shop on Quantum Computing Software (QCS), pages 64–

    work page

  36. [36]

    Parametertrans- fer for quantum approximate optimization of weighted maxcut

    Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, JamesOstrowski, andTravisSHumble. Parametertrans- fer for quantum approximate optimization of weighted maxcut. ACM Transactions on Quantum Computing, 4(3):1–15, 2023

    work page 2023

  37. [37]

    A variational eigenvalue solver on a photonic quantum processor.Nature Com- munications, 5(1):1–7, 2014

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man- 17 Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru- Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor.Nature Com- munications, 5(1):1–7, 2014

    work page 2014

  38. [38]

    Quantum Computation by Adiabatic Evolution

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evo- lution. arXiv preprint quant-ph/0001106, 2000

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  39. [39]

    Beweis des adiabaten- satzes

    Max Born and Vladimir Fock. Beweis des adiabaten- satzes. Zeitschrift für Physik, 51(3):165–180, 1928

    work page 1928

  40. [40]

    On the adiabatic theorem of quantum mechanics

    Tosio Kato. On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan, 5(6):435–439, 1950

    work page 1950

  41. [41]

    V12.1: User’smanualforCPLEX

    IBMILOGCplex. V12.1: User’smanualforCPLEX. In- ternational Business Machines Corporation, 46(53):157, 2009

    work page 2009

  42. [42]

    Approximability of the minimum bi- section problem: An algorithmic challenge

    Marek Karpinski. Approximability of the minimum bi- section problem: An algorithmic challenge. InInterna- tional Symposium on Mathematical Foundations of Com- puter Science, pages 59–67. Springer, 2002

    work page 2002

  43. [43]

    Complexity results on a paint shop problem

    Th Epping, Winfried Hochstättler, and Peter Oertel. Complexity results on a paint shop problem. Discrete Applied Mathematics, 136(2-3):217–226, 2004

    work page 2004

  44. [44]

    Multi- car paint shop optimization with quantum annealing

    Sheir Yarkoni, Alex Alekseyenko, Michael Streif, David Von Dollen, Florian Neukart, and Thomas Bäck. Multi- car paint shop optimization with quantum annealing. In 2021 IEEE International Conference on Quantum Com- puting and Engineering (QCE),pages35–41.IEEE, 2021

    work page 2021

  45. [45]

    Paint line color change reduction in automobile assembly through simu- lation

    Yong-Hee Han, Chen Zhou, Bert Bras, Leon McGinnis, Carol Carmichael, and PJ Newcomb. Paint line color change reduction in automobile assembly through simu- lation. InWinter Simulation Conference, volume2, pages 1204–1209, 2003

    work page 2003

  46. [46]

    The quantum approximate optimization algorithm needs to see the whole graph: A typical case

    EdwardFarhi, DavidGamarnik, andSamGutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv preprint arXiv:2004.09002, 2020

    work page arXiv 2004

  47. [47]

    The quantum approximate optimization algorithm needs to seethewholegraph: Worstcaseexamples

    EdwardFarhi, DavidGamarnik, andSamGutmann. The quantum approximate optimization algorithm needs to seethewholegraph: Worstcaseexamples. arXiv preprint arXiv:2005.08747, 2020

    work page arXiv 2005

  48. [48]

    Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models

    Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 335–343. IEEE, 2022

    work page 2022

  49. [49]

    Classical and quantum bounded depth approximation algorithms

    Matthew B Hastings. Classical and quantum bounded depth approximation algorithms. arXiv preprint arXiv:1905.07047, 2019

    work page arXiv 1905

  50. [50]

    Recursive QAOA outper- forms the original QAOA for the MAX-CUT problem on complete graphs

    Eunok Bae and Soojoon Lee. Recursive QAOA outper- forms the original QAOA for the MAX-CUT problem on complete graphs. Quantum Information Processing, 23(3):78, 2024

    work page 2024

  51. [51]

    Reinforcement learning assisted recursive QAOA

    Yash J Patel, Sofiene Jerbi, Thomas Bäck, and Ve- dran Dunjko. Reinforcement learning assisted recursive QAOA. EPJ Quantum Technology, 11(1):6, 2024

    work page 2024

  52. [52]

    Quantum-informed recursive optimization algorithms

    Jernej Rudi Finžgar, Aron Kerschbaumer, Martin JA Schuetz, Christian B Mendl, and Helmut G Katzgraber. Quantum-informed recursive optimization algorithms. PRX Quantum, 5(2):020327, 2024

    work page 2024

  53. [53]

    Recursivequantumrelaxationforcombinatorial optimization problems

    Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Ya- mamoto. Recursivequantumrelaxationforcombinatorial optimization problems. Quantum, 9:1594, 2025

    work page 2025

  54. [54]

    Majority voting with recursive qaoa and cost-restricted uniform sampling for maximum- likelihooddetectioninmassivemimo

    Burhan Gulbahar. Majority voting with recursive qaoa and cost-restricted uniform sampling for maximum- likelihooddetectioninmassivemimo. IEEE Transactions on Wireless Communications, 2025

    work page 2025

  55. [55]

    The quantum alternating operator ansatz on maximum k-vertex cover

    Jeremy Cook, Stephan Eidenbenz, and Andreas Bärtschi. The quantum alternating operator ansatz on maximum k-vertex cover. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 83–92. IEEE, 2020

    work page 2020

  56. [56]

    Accelerating quantum approximate optimiza- tion algorithm using machine learning

    Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh. Accelerating quantum approximate optimiza- tion algorithm using machine learning. In2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 686–689. IEEE, 2020

    work page 2020

  57. [57]

    Reinforcement-learning- assisted quantum optimization

    Matteo M Wauters, Emanuele Panizon, Glen B Mbeng, and Giuseppe E Santoro. Reinforcement-learning- assisted quantum optimization. Physical Review Re- search, 2(3):033446, 2020

    work page 2020

  58. [58]

    Iteration-free quantum ap- proximate optimization algorithm using neural networks

    Ohad Amosy, Tamuz Danzig, Ohad Lev, Ely Porat, Gal Chechik, and Adi Makmal. Iteration-free quantum ap- proximate optimization algorithm using neural networks. Quantum Machine Intelligence, 6(2):38, 2024

    work page 2024

  59. [59]

    Transferability of optimal QAOA parameters between random graphs

    Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alex- eev, and Ilya Safro. Transferability of optimal QAOA parameters between random graphs. In2021 IEEE In- ternational Conference on Quantum Computing and En- gineering (QCE), pages 171–180. IEEE, 2021

    work page 2021

  60. [60]

    Empirical perfor- mance bounds for quantum approximate optimization

    Phillip C Lotshaw, Travis S Humble, Rebekah Herrman, James Ostrowski, and George Siopsis. Empirical perfor- mance bounds for quantum approximate optimization. Quantum Information Processing, 20(12):1–32, 2021

    work page 2021

  61. [61]

    Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices

    Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2):021067, 2020

    work page 2020

  62. [62]

    MaxCut quantum ap- proximate optimization algorithm performance guaran- tees for p> 1.Physical Review A, 103(4):042612, 2021

    Jonathan Wurtz and Peter Love. MaxCut quantum ap- proximate optimization algorithm performance guaran- tees for p> 1.Physical Review A, 103(4):042612, 2021

    work page 2021

  63. [63]

    Improved approximation algorithms for maximum cut and satisfia- bility problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfia- bility problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    work page 1995

  64. [64]

    For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

    Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimiza- tion algorithm’s objective function value concentrates for typicalinstances. arXiv preprint arXiv:1812.04170, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  65. [65]

    Quantum approximate optimization algorithm for MaxCut: A fermionic view

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Physical Re- view A, 97(2):022304, 2018

    work page 2018

  66. [66]

    Columbia University, 2018

    Stuart Andrew Hadfield.Quantum algorithms for scien- tific computing and approximate optimization. Columbia University, 2018

    work page 2018

  67. [67]

    The quantum approximate optimization algo- rithm and the Sherrington-Kirkpatrick model at infinite size

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algo- rithm and the Sherrington-Kirkpatrick model at infinite size. Quantum, 6:759, 2022

    work page 2022

  68. [68]

    Learning to opti- mize variational quantum circuits to solve combinatorial problems

    Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. Learning to opti- mize variational quantum circuits to solve combinatorial problems. In Proceedings of the AAAI conference on ar- tificial intelligence, volume 34, pages 2367–2375, 2020

    work page 2020

  69. [69]

    Symmetry- informed transferability of optimal parameters in the 18 quantum approximate optimization algorithm.Physical Review A, 111(2):022418, 2025

    Isak Lyngfelt and Laura García-Álvarez. Symmetry- informed transferability of optimal parameters in the 18 quantum approximate optimization algorithm.Physical Review A, 111(2):022418, 2025

    work page 2025

  70. [70]

    Hybrid quantum optimization in the con- text of minimizing traffic congestion

    Jedwin Villanueva, Gary J Mooney, Bhaskar Roy Bard- han, Joydip Ghosh, Charles D Hill, and Lloyd CL Hollenberg. Hybrid quantum optimization in the con- text of minimizing traffic congestion. arXiv preprint arXiv:2504.08275, 2025

    work page arXiv 2025