Improving Quantum Optimization to Achieve Quadratic Time Complexity

Dapeng Yu; Jiawei Zhang; Ji Chu; Ji Jiang; Jingjing Niu; Libo Zhang; Peisheng Huang; Song Liu; Weijie Guo; Wenhui Huang

REVIEW 3 major objections 6 minor 79 references

Improving Quantum Optimization to Achieve Quadratic Time Complexity

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Penta-O proves that the energy expectation of a p-level QAOA on any QUBO/Ising Hamiltonian is a two-sine trigonometric function of the final mixer angle, so that angle can be set from five measurements and the classical outer loop…

desk verdict Correct trig theorem and a genuinely useful level-wise parameter-setting scheme, but the hand-picked gamma0 and the notation swap keep it from being the stand-alone recipe it claims. read the letter →

arxiv 2501.13469 v1 pith:4A5KJS6S submitted 2025-01-23 quant-ph

Ji Jiang , Peisheng Huang , Zhiyi Wu , Xuandong Sun , Zechen Guo , Wenhui Huang , Libo Zhang , Yuxuan Zhou

show 10 more authors

Jiawei Zhang Weijie Guo Xiayu Linpeng Song Liu Wenhui Ren Ziyu Tao Ji Chu Jingjing Niu Youpeng Zhong Dapeng Yu

This is my paper · ORCID

classification quant-ph

keywords quantumapproximateoptimizationalgorithmQAOAparametersettingQUBOIsingmodelouter-loop-freevariationalMaxCutSherrington-Kirkpatricktrigonometricenergylandscape

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper seeks to remove the most expensive step in the Quantum Approximate Optimization Algorithm (QAOA): the classical outer loop that repeatedly adjusts circuit angles. It proves that for any quadratic unconstrained binary optimization (QUBO) problem written as an Ising Hamiltonian, the energy expectation of a $p$-level QAOA, seen as a function of the final mixer angle $\theta_p$, is exactly a two-sine trigonometric function whose coefficients are independent of $\theta_p$. Five energy measurements at fixed probe angles therefore recover the whole curve and let the minimizing angle be chosen directly; repeating this level by level builds a $p$-level circuit in $O(p^2)$ time with sampling overhead proportional to $5p+1$. Because the previous level is recovered at $\theta_p=0$, the construction guarantees non-decreasing performance. Experiments on MaxCut and simulations on weighted graphs and the Sherrington-Kirkpatrick model with a longitudinal field show near-optimal ratios at substantially lower depth than prior outer-loop-free methods.

What carries the argument

The machinery is the trigonometric identity for the terminal mixer angle, Eq. (4), derived from the single-qubit rotation formula $U_M^\dagger(\theta_p) Z_i U_M(\theta_p) = \cos(2\theta_p) Z_i + \sin(2\theta_p) Y_i$. This identity separates $\theta_p$ from the Hamiltonian and expresses the five coefficients as $\theta_p$-independent expectations, for example sums of $\langle Z_i Z_j \rangle$, $\langle Y_i Y_j \rangle$, $\langle Z_i Y_j + Y_i Z_j \rangle$, $\langle Z_i \rangle$, and $\langle Y_i \rangle$, evaluated on the state $U_C(p)|\psi_{p-1}\rangle$. Penta-O is the level-wise fitting procedure that uses five (or three) energy samples to recover these coefficients and then selects the minimizing $\theta_p$ for each new level.

What would settle it

Take a small weighted MaxCut instance with a longitudinal field, set $\gamma_0$ to a fixed value, and measure $J_2$ at many $\theta_2$ values; if a two-sine fit from five probe angles does not reproduce the measured curve within sampling error, Eq. (4) is wrong. In the practical direction, run Penta-O on one graph family with $\gamma_0$ spanning 0.01 to 1; if performance depends sharply on a narrow $\gamma_0$ range and no heuristic predicts that range, the method is not yet a standalone recipe.

Watch

Extended reading notes

Core claim

The paper's central discovery is that at any level $p$, once the earlier levels are fixed, the energy expectation $J_p = \langle \psi_p | H_C | \psi_p \rangle$ is exactly $$J_p = A_p \sin(4\theta_p + \phi_p) + A'_p \sin(2\theta_p + \phi'_p) + C_p,$$ with $A_p, A'_p, \phi_p, \phi'_p, C_p$ all independent of $\theta_p$. The proof pulls the last mixer rotation through the Pauli operators via $U_M^\dagger Z_i U_M = \cos(2\theta_p)Z_i + \sin(2\theta_p)Y_i$, leaving $\theta_p$ only in scalar sine and cosine factors. Measuring at five probe angles $\theta_x = k\pi/6$ for $k=1,\dots,5$ therefore determines $J_p(\theta_p)$ completely, and the minimizer of that fitted curve is the chosen $\theta_p$. When the Ising field $w_{ii}$ is absent, the period shortens to $\pi/2$ and three probes at $k\pi/8$ suffice. Because $\theta_p=0$ reproduces the previous level, the fitted minimizer always yields $J_p \le J_{p-1}$, giving a non-decreasing performance guarantee.

Load-bearing premise

The method depends on a fixed cost-evolution angle $\gamma_0$ that is chosen by hand for each problem family, and the paper explicitly leaves the optimal choice of this angle as an open question; without a reliable way to set it, the reported performance is not a fully parameter-free recipe.

Editorial extensions

If this is right

At each level the minimizing $\theta_p$ is obtained from a closed-form fit, so no gradient-based or black-box classical optimizer is ever invoked.
The full parameter search costs $O(p^2)$ circuit-preparation time and at most $(5p+1)M$ samples, with only $3p+1$ for field-free problems, giving the first quadratic-time level-wise setting with a non-decreasing guarantee.
QAOA performance cannot decrease as $p$ grows, because $\theta_p=0$ exactly reproduces the previous level's circuit and the fitted minimizer is at least as good.
On unweighted 3-regular MaxCut, the average approximation ratio crosses the classical lower bound around $p\approx 30$ and in the worst case by $p\approx 40$, roughly an order of magnitude shallower than the leading feedback-based outer-loop-free method.
For spin-glass instances with longitudinal fields, more than half of the tested replicas sample low-energy states with probability above 0.8, and the paper's time-to-solution extrapolation locates a practical quantum-classical crossover near $N\approx 500$ if the required QAOA level grows only logarithmically with $N$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the rotation-identity proof does not use the fact that the problem is quadratic in a deep way, so a similar finite-harmonic trigonometric form should hold for Hamiltonians whose terms are products of $Z$ operators, with more harmonics appearing at higher interaction order.
Beyond the paper: five probe angles are a minimal interpolation set, so using redundant probe angles with a least-squares fit would give a noise-robust variant whose sampling overhead is still $O(p)$; this is a cheap experimental upgrade.
Beyond the paper: the open choice of $\gamma_0$ is the main obstacle to a fully automatic method, and a per-instance heuristic for $\gamma_0$ based on graph degree, weight statistics, or a short classical prescreen would complete the recipe.
Beyond the paper: the benchmark design suggests a falsifiable scaling test — on random 3-regular MaxCut graphs with $N$ growing beyond 20, one should check whether the level count needed to cross the classical bound stays near 40 or grows with $N$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing: the central claim is true. S1 gives a clean conjugation proof that J_p is a trig polynomial in the final mixer angle with coefficients independent of that angle, and the five-probe reconstruction is nonsingular. The p=1 version was known, but extending it to general p and turning it into level-wise Penta-O — inherit previous parameters, fix gamma0, fit the curve with five energy measurements, pick the minimizer — is genuinely new. It removes the classical outer loop over theta and gives non-decreasing depth performance. That is a useful practical result, and the relevant p=1 derivations are cited fairly.

Where the soft spots are. The gamma/theta notation is swapped between Eq. (2) and the S1 proof. It matters because the non-decreasing argument only works if theta_p is the mixer angle, as in S1. The main text's Eq. (2) has them reversed. Fixing this is not a pedantic point; a reader following Eq. (2) won't get the guarantee.

The bigger issue is gamma0. It is set by hand (0.2 hardware, 0.075 u3r, 0.05 SK), and the paper admits the optimal value is open. Since the coefficients in Eq. (S8) depend on gamma_p, the convergence speed and final approximation ratio are conditional on this choice. Non-decreasing holds for any fixed gamma0, so the theorem is fine, but Penta-O is not a parameter-free recipe. At minimum the paper needs a sensitivity analysis or a plausible selection rule. The benchmarks also lack error bars and code, which matters for the hardware and near-optimality claims.

The complexity claim is O(p^2) in level count, with t0 proportional to N per level, so total gate cost is O(p^2 N). The abstract's "quadratic time complexity" is defensible but could mislead. The N approximately 500 crossover estimate is explicitly speculative because p-N scaling is unknown; I would not treat it as a result.

This is a solid methods paper with one clear free parameter. The theorem is correct, the algorithm is simple and testable, and the comparison with FALQON is reasonably fair. It deserves proper peer review. I would send it, but with referees asked to pin down the gamma0 problem and demand code and data.

Referee Report

3 major / 6 minor

Summary. The paper proves that for a p-level QAOA on an Ising/QUBO Hamiltonian, the energy expectation J_p is a trigonometric function of the final-level mixer angle, specifically J_p = A_p sin(4θ_p + φ_p) + A'_p sin(2θ_p + φ'_p) + C_p, with coefficients independent of θ_p. On the basis of this identity, the authors propose Penta-O, a level-wise parameter-setting method that determines each level's final mixer angle from a small number of probe measurements (five in general, three in the field-free case), removing the classical outer loop over variational parameters. They claim an O(p^2) time complexity and 5p+1 trial sampling overhead, and demonstrate the method on a superconducting processor for a small MaxCut instance and in noiseless simulations for MaxCut and Sherrington-Kirkpatrick models, reporting near-optimal approximation ratios and low-energy sampling probabilities. The authors also discuss the role of the fixed cost angle γ0 and potential quantum-classical crossover. The central mathematical derivation is presented in Supplemental Material S1, and numerical details are in S2 and S3.

Significance. If the trigonometric identity and the reconstruction protocol are correct, this is a valuable contribution: it replaces a variational optimization over a continuous parameter with a fixed small number of quantum measurements per level, provides a non-decreasing performance guarantee (via θ_p = 0 recovering the previous level), and yields a clean O(p^2) circuit-preparation cost. The proof in S1 is explicit and, once the notation is fixed, appears mathematically sound; the coefficient formulas in Eq. (S8) follow from a straightforward trigonometric expansion. The empirical demonstrations support the plausibility of the method on small instances, though they are conditional on a hand-picked γ0. The strengths of the paper include a first-principles derivation rather than a black-box fit, a simple and falsifiable prediction about the functional form of J_p, and a clear protocol for determining the five coefficients from measurements. The main weaknesses are the internal notation reversal and the presence of a free hyperparameter γ0 that is tuned per benchmark class without a selection rule.

major comments (3)

[§S1 and Eq. (2)] The roles of γ and θ are exchanged between the main text and the proof. In Eq. (2) of the main text, θ_l multiplies H_C and γ_l multiplies H_M, so θ_p is the final cost angle. In S1, however, U_C(l) = e^{-iγ_l H_C} and U_M(l) = e^{-iθ_l H_M}, and the identity (S2) is derived for U_M† Z_i U_M, so θ_p is the final mixer angle. The state written at the start of S1 (∏ e^{-iγ_l H_M} e^{-iθ_l H_C}) contradicts the definitions of U_C and U_M immediately following it. As written, Eq. (4) in the main text therefore asserts that J_p is a trigonometric function of the final cost angle, which is not what the proof establishes; the proof establishes the dependence on the final mixer angle. This ambiguity affects the core algorithm, since the probe angles θ_x in the Penta-O protocol must be applied to the final mixer unitary. The authors should adopt a single convention throughout, restate Eq. (2) and Eq. (4) consistently, and ensure the S1 proof uses the same pairing of parameters and unitaries as the main text.
[Discussion and outlook (γ0 choice) and Fig. 2] The fixed cost angle γ0 is a free hyperparameter whose values are chosen per benchmark class: γ0 = 0.2 for the hardware experiment, γ0 = 0.075 for unweighted 3-regular MaxCut, and γ0 = 0.05 for the SK model (Fig. 2 captions and main text). The coefficients in Eq. (S8) depend on γ_p through the state U_C(p)|ψ_{p-1}⟩, so the achievable per-level energy decrease and the depth p needed to reach a target approximation ratio are functions of γ0. The paper acknowledges that determining the optimal γ0 remains an open question. This means Penta-O does not fully eliminate the classical outer loop; it replaces optimization over θ_p with a per-problem-class choice of γ0. The reported performance claims are therefore conditional on tuning choices that the paper does not derive or justify. To make the method a standalone recipe, the authors should either provide a rule for setting γ0 from the instance (e.g., based on max_i,j |w_ij| or other spectral properties), or demonstrate through a sensitivity analysis that the results are robust over a wide range of γ0 values.
[§S2 and Fig. 2(a)] The numerical evidence is presented without error bars for the hardware experiment and without a public code or data repository. The hardware results in Fig. 2(a) are based on single runs with M = 3000 repetitions per trial; quantum measurement statistical fluctuations and gate errors are not quantified, so it is difficult to assess whether the observed monotonic decrease in energy is significant. For the simulations, the use of Qiskit with exact statevector evolution is not explicitly stated, nor is a reproducibility package provided. Given that the empirical demonstrations are a central part of the paper's practical claims, the authors should provide at least confidence intervals for the hardware data and make the simulation scripts and instance lists available.

minor comments (6)

[Eq. (2)] The product notation ∏_{l=1}^p e^{-iγ_l H_M} e^{-iθ_l H_C} is ambiguous for quantum circuits; specify explicitly whether the l = 1 factor is on the right (applied first) or left, as the ordering affects the subsequent derivations.
[Abstract and main text] The word 'unprecedented' oversells the result; other outer-loop-free methods such as FALQON already remove the variational outer loop, so the novelty is the fixed number of trials and quadratic cost, not the general concept. Suggest rephrasing to avoid a misleading uniqueness claim.
[Main text, sampling overhead] The phrase 'sampling overhead proportional to 5p+1' should be more precise: the total number of shots is (5p+1)M, where M is the number of repetitions per trial. This distinction matters for practical resource estimation.
[Fig. 2(b)] The comparison of the ground-state probability 0.2733 to 'the classical algorithm' is vague; specify which classical algorithm (e.g., Goemans-Williamson) and what probability is being compared, and note that the QAOA probability is for the specific 2×3 grid instance rather than a worst-case bound.
[S3] The quantum-classical crossover estimate depends on speculative p-N scaling laws (p ∝ N^2, p ∝ N, p ∝ log N) and on an assumed t0 and M; these assumptions should be clearly labeled as speculative and not as a proven advantage result.
[Discussion] There is a typo: 'proportion to' should be 'proportional to', and the statement about the discretization error should refer to the operator norm of the commutator or a more precise bound rather than an informal proportionality.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the trigonometric ansatz is proven from operator identities, and the five-probe reconstruction is a legitimate interpolation fit, not a prediction forced by construction.

full rationale

The paper's core claim, Eq. (4), is not assumed but derived in Supplemental Section S1. The derivation conjugates H_C by the final mixer unitary e^{-i θ_p H_M}, uses the exact identity U_M^† Z_i U_M = cos(2θ_p) Z_i + sin(2θ_p) Y_i, and obtains Eq. (S7) with coefficients that are explicitly independent of θ_p. The five-trial procedure measures J_p at fixed probe angles and solves a nonsingular linear system for the five coefficients; the subsequent minimization of the fitted trigonometric curve over θ_p is standard interpolation-based optimization, not a circular re-instatement of the fitted values. The non-decreasing guarantee follows from J_p(θ_p=0) = J_{p-1} and the minimization step, which is logically valid. The fixed angle γ_0 is a manually chosen hyperparameter (0.2 for hardware, 0.075 for u3r, 0.05 for SK), and the paper explicitly states that determining its optimal value remains an open question; this is a tuning limitation, not circularity. The only self-citation to prior work [60] concerns the experimental hardware platform and is not load-bearing for the derivation. Overall, the derivation chain is self-contained and no step reduces to its own inputs by construction.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central proof uses only the operator identity for conjugating Z by a transverse-field rotation and the restriction to two-body Ising Hamiltonians. The main extra assumption is the hand-chosen fixed cost angle γ0, which functions as a free parameter. No new physical entities are introduced.

free parameters (1)

γ0 (fixed cost angle) = 0.2 for hardware, 0.075 for u3r, 0.05 for SK
Chosen by hand for each problem class; performance and convergence depend on it, and no systematic selection rule is provided.

assumptions (3)

domain assumption The cost Hamiltonian is restricted to QUBO/Ising form: H_C = Σ w_ij Z_i Z_j + Σ w_ii Z_i.
The proof of the trigonometric form relies on this two-body diagonal structure; higher-order k-local terms would generate additional frequencies and break the five-trial scheme.
domain assumption The mixer is the transverse field H_M = -⊗ X_i, and the optimized variable is the mixer angle.
The identity U† Z U = cos2θ Z + sin2θ Y requires a single-qubit Pauli mixer; the paper's core formulas depend on this, despite the γ/θ notation swap in Eq. (2).
standard math The five probe angles (kπ/6 for general Ising, kπ/8 for field-free) yield an invertible system for the five unknown coefficients.
The paper assumes, but does not prove, that measuring J_p at these angles uniquely determines A_p, A'_p, φ_p, φ'_p, C_p.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improving Quantum Optimization to Achieve Quadratic Time Complexity." pith.science (2026). https://pith.science/paper/4A5KJS6S

@misc{pith2026250113469,
  author       = {Pith},
  title        = {Pith review of: Improving Quantum Optimization to Achieve Quadratic Time Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4A5KJS6S}},
  note         = {Machine review of arXiv:2501.13469}
}

abstract

Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage in combinatorial optimization. However, its variational framework presents a long-standing challenge in selecting circuit parameters. In this work, we prove that the energy expectation produced by QAOA can be expressed as a trigonometric function of the final-level mixer parameter. Leveraging this insight, we introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance. This method is broadly applicable to the generic quadratic unconstrained binary optimization formulated as the Ising model. For a $p$-level QAOA, Penta-O achieves an unprecedented quadratic time complexity of $\mathcal{O}(p^2)$ and a sampling overhead proportional to $5p+1$. Through experiments and simulations, we demonstrate that QAOA enhanced by Penta-O achieves near-optimal performance with exceptional circuit depth efficiency. Our work provides a versatile tool for advancing variational quantum algorithms.

Figures

Figures reproduced from arXiv: 2501.13469 by the authors.

**Figure 2.** FIG. 2. (a) Triple-level QAOA experiment results with Penta-O where [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

79 extracted references · 63 canonical work pages

[1]

Lucas, Ising formulations of many NP problems, Front

A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014)

work page 2014
[2]

Glover, G

F. Glover, G. Kochenberger, R. Hennig, and Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, Ann. Oper. Res. 314, 141 (2022)

work page 2022
[3]

Herman, R

D. Herman, R. Shaydulin, Y. Sun, S. Chakrabarti, S. Hu, P. Minssen, A. Rattew, R. Yalovetzky, and M. Pistoia, Constrained optimization via quantum Zeno dynamics, Commun. Phys. 6, 219 (2023)

work page 2023
[4]

Buonaiuto, F

G. Buonaiuto, F. Gargiulo, G. De Pietro, M. Esposito, and M. Pota, Best practices for portfolio optimization by quantum computing, experimented on real quantum devices, Sci. Rep. 13, 19434 (2023)

work page 2023
[5]

N. N. Hegade, P. Chandarana, K. Paul, X. Chen, F. Al- barr´ an-Arriagada, and E. Solano, Portfolio optimiza- tion with digitized counterdiabatic quantum algorithms, Phys. Rev. Res. 4, 043204 (2022)

work page 2022
[6]

Brandhofer, D

S. Brandhofer, D. Braun, V. Dehn, G. Hellstern, M. H¨ uls, Y. Ji, I. Polian, A. S. Bhatia, and T. Wellens, Bench- marking the performance of portfolio optimization with QAOA, Quantum Inf. Process. 22, 25 (2022)

work page 2022
[7]

Stollenwerk, S

T. Stollenwerk, S. Hadfield, and Z. Wang, Toward quan- tum gate-model heuristics for real-world planning prob- lems, IEEE Transactions on Quantum Engineering 1, 1 (2020)

work page 2020
[8]

Vikst˚ al, M

P. Vikst˚ al, M. Gr¨ onkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, Applying the quantum ap- proximate optimization algorithm to the tail-assignment problem, Phys. Rev. Appl. 14, 034009 (2020)

work page 2020

Show all 79 references

[9]

Y. Chai, L. Funcke, T. Hartung, K. Jansen, S. K¨ uhn, P. Stornati, and T. Stollenwerk, Optimal flight-gate as- signment on a digital quantum computer, Phys. Rev. Appl. 20, 064025 (2023)

2023
[10]

Ding, Y.-M

Q.-M. Ding, Y.-M. Huang, and X. Yuan, Molecular dock- ing via quantum approximate optimization algorithm, Phys. Rev. Appl. 21, 034036 (2024)

2024
[11]

Zaborniak, J

T. Zaborniak, J. Giraldo, H. M¨ uller, H. Jabbari, and U. Stege, A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing, in 2022 IEEE International Conference on Quantum Com- puting and Engineering (QCE) (2022) pp. 174–185

2022
[12]

D. M. Fox, C. M. MacDermaid, A. M. Schreij, M. Zwierzyna, and R. C. Walker, RNA folding using quantum computers, PLoS Comput. Biol. 18, e1010032 (2022)

2022
[13]

Chandarana, N

P. Chandarana, N. N. Hegade, I. Montalban, E. Solano, and X. Chen, Digitized counterdiabatic quantum algo- rithm for protein folding, Phys. Rev. Appl. 20, 014024 (2023)

2023
[14]

Robert, P

A. Robert, P. K. Barkoutsos, S. Woerner, and I. Tav- ernelli, Resource-efficient quantum algorithm for protein folding, npj Quantum Inf. 7, 38 (2021)

2021
[15]

Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zale- tel, K. Temme, et al. , Evidence for the utility of quan- tum computing before fault tolerance, Nature 618, 500 (2023)

2023
[16]

Pagano, A

G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, et al., Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator, Proc. Natl. Acad. Sci. 117, 25396 (2020)

2020
[17]

Dupont, B

M. Dupont, B. Evert, M. J. Hodson, B. Sundar, S. Jef- frey, Y. Yamaguchi, D. Feng, F. B. Maciejewski, S. Had- field, M. S. Alam, et al. , Quantum-enhanced greedy combinatorial optimization solver, Sci. Adv. 9, eadi0487 (2023)

2023
[18]

Pelofske, A

E. Pelofske, A. B¨ artschi, L. Cincio, J. Golden, and S. Ei- denbenz, Scaling whole-chip QAOA for higher-order Ising spin glass models on heavy-hex graphs, npj Quantum Inf. 10, 109 (2024)

2024
[19]

F. B. Maciejewski, S. Hadfield, B. Hall, M. Hodson, M. Dupont, B. Evert, J. Sud, M. S. Alam, Z. Wang, S. Jeffrey, B. Sundar, P. A. Lott, S. Grabbe, E. G. Rief- fel, M. J. Reagor, and D. Venturelli, Design and execution of quantum circuits using tens of superconducting qubits a...

2024
[20]

M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, et al. , Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021)

2021
[21]

Ebadi, A

S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science376, 1209 (2022)

2022
[22]

Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rief- fel, xy mixers: Analytical and numerical results for the quantum alternating operator ansatz, Phys. Rev. A 101, 012320 (2020)

2020
[23]

M. H. Mu˜ noz Arias, S. Kourtis, and A. Blais, Low-depth clifford circuits approximately solve maxcut, Phys. Rev. Res. 6, 023294 (2024)

2024
[24]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014)

2014 arXiv
[25]

Hadfield, Z

S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Ven- turelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating opera- tor ansatz, Algorithms 12, 34 (2019)

2019
[26]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size, Quantum 6, 759 (2022)

2022
[27]

Shaydulin, C

R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Her- man, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, et al. , Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically in- tractable problem, Sci. Adv. 10, eadm6761 (2024)

2024
[28]

Zhou, S.-T

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices, Phys. Rev. X 10, 021067 (2020)

2020
[29]

Bonet-Monroig, H

X. Bonet-Monroig, H. Wang, D. Vermetten, B. Senjean, C. Moussa, T. B¨ ack, V. Dunjko, and T. E. O’Brien, Per- formance comparison of optimization methods on vari- ational quantum algorithms, Phys. Rev. A 107, 032407 (2023)

2023
[30]

Blekos, D

K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A review on quantum ap- proximate optimization algorithm and its variants, Phys. Rep. 1068, 1 (2024)

2024
[31]

Wierichs, C

D. Wierichs, C. Gogolin, and M. Kastoryano, Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer, Phys. Rev. Res.2, 043246 (2020)

2020
[32]

Koczor and S

B. Koczor and S. C. Benjamin, Quantum natural gradi- ent generalized to noisy and nonunitary circuits, Phys. Rev. A 106, 062416 (2022)

2022
[33]

Bittel and M

L. Bittel and M. Kliesch, Training variational quantum algorithms is NP-hard, Phys. Rev. Lett. 127, 120502 (2021)

2021
[34]

Akshay, D

V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, Parameter concentrations in quantum approximate opti- mization, Phys. Rev. A 104, L010401 (2021)

2021
[35]

Wurtz and D

J. Wurtz and D. Lykov, Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs, Phys. Rev. A 104, 052419 (2021)

2021
[36]

Shaydulin, P

R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, Parameter transfer for quantum approx- imate optimization of weighted MaxCut, ACM Trans. Quantum Comput. 4, 1 (2023)

2023
[37]

Galda, X

A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, Transferability of optimal QAOA parameters between random graphs, in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE,

2021
[38]

S. H. Sureshbabu, D. Herman, R. Shaydulin, J. Basso, S. Chakrabarti, Y. Sun, and M. Pistoia, Parameter Set- ting in Quantum Approximate Optimization of Weighted Problems, Quantum 8, 1231 (2024)

2024
[39]

A. B. Magann, K. M. Rudinger, M. D. Grace, and M. Sarovar, Feedback-based quantum optimization, Phys. Rev. Lett. 129, 250502 (2022)

2022
[40]

A. B. Magann, K. M. Rudinger, M. D. Grace, and M. Sarovar, Lyapunov-control-inspired strategies for quantum combinatorial optimization, Phys. Rev. A 106, 062414 (2022)

2022
[41]

J. B. Larsen, M. D. Grace, A. D. Baczewski, and A. B. Magann, Feedback-based quantum algorithms for ground state preparation, Phys. Rev. Res. 6, 033336 (2024)

2024
[42]

R. K. Malla, H. Sukeno, H. Yu, T.-C. Wei, A. Weich- selbaum, and R. M. Konik, Feedback-based quantum al- gorithm inspired by counterdiabatic driving, Phys. Rev. Res. 6, 043068 (2024)

2024
[43]

Chandarana, K

P. Chandarana, K. Paul, K. R. Swain, X. Chen, and A. del Campo, Lyapunov controlled counterdiabatic quantum optimization, arXiv preprint arXiv:2409.12525 (2024)

2024 arXiv
[44]

S. X. Li, W. L. Mu, J. B. You, and X. Q. Shao, Sim- ulation of a feedback-based algorithm for quantum op- timization for a realistic neutral-atom system with an optimized small-angle controlled-phase gate, Phys. Rev. A 109, 062603 (2024)

2024
[45]

L. T. Brady and S. Hadfield, FOCQS: Feedback optimally controlled quantum states, arXiv preprint arXiv:2409.15426 (2024)

2024 arXiv
[46]

Abbas, A

A. Abbas, A. Ambainis, B. Augustino, A. B¨ artschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, et al. , Challenges and oppor- tunities in quantum optimization, Nat. Rev. Phys. , 1 (2024)

2024
[47]

Hauke, H

P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishi- mori, and W. D. Oliver, Perspectives of quantum anneal- ing: Methods and implementations, Rep. Prog. Phys. 83, 054401 (2020)

2020
[48]

Kadowaki and H

T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Phys. Rev. E 58, 5355 (1998)

1998
[49]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv preprint quant-ph/0001106 (2000)

2000 arXiv
[50]

Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quan- tum approximate optimization algorithm for maxcut: A fermionic view, Phys. Rev. A 97, 022304 (2018)

2018
[51]

Bravyi, A

S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obsta- cles to variational quantum optimization from symmetry protection, Phys. Rev. Lett. 125, 260505 (2020)

2020
[52]

Bravyi, A

S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Hybrid quantum-classical algorithms for approximate graph col- oring, Quantum 6, 678 (2022)

2022
[53]

Ozaeta, W

A. Ozaeta, W. van Dam, and P. L. McMahon, Expecta- tion values from the single-layer quantum approximate optimization algorithm on Ising problems, Quantum Sci. 7 Technol. 7, 045036 (2022)

2022
[54]

See Supplemental Material for the proof and details of simulations
[57]

Berman and M

P. Berman and M. Karpinski, On some tighter inap- proximability results, in Automata, Languages and Pro- gramming: 26th International Colloquium, ICALP’99 Prague, Czech Republic, July 11-15, 1999 Proceedings 26 (Springer, 1999) pp. 200–209

1999
[58]

M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115 (1995)

1995
[60]

X. Yang, J. Chu, Z. Guo, W. Huang, Y. Liang, J. Liu, J. Qiu, X. Sun, Z. Tao, J. Zhang, J. Zhang, L. Zhang, Y. Zhou, W. Guo, L. Hu, J. Jiang, Y. Liu, X. Linpeng, T. Chen, Y. Chen, J. Niu, S. Liu, Y. Zhong, and D. Yu, Coupler-assisted leakage reduction for scalable quantum error...

2024
[61]

Javadi-Abhari, M

A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, et al. , Quantum computing with Qiskit, arXiv preprint arXiv:2405.08810 (2024)

2024 arXiv
[62]

Alimonti and V

P. Alimonti and V. Kann, Some APX-completeness re- sults for cubic graphs, Theoretical Computer Science 237, 123 (2000)

2000
[63]

Halperin, D

E. Halperin, D. Livnat, and U. Zwick, MAX CUT in cubic graphs, J. Algorithms 53, 169 (2004)

2004
[64]

Charikar and A

M. Charikar and A. Wirth, Maximizing quadratic pro- grams: Extending grothendieck’s inequality, in 45th An- nual IEEE Symposium on Foundations of Computer Sci- ence (IEEE, 2004) pp. 54–60

2004
[65]

Panchenko, The Sherrington-Kirkpatrick model (Springer New York, 2013)

D. Panchenko, The Sherrington-Kirkpatrick model (Springer New York, 2013)

2013
[66]

Talagrand, Mean field models for spin glasses: Volume I: Basic examples , Vol

M. Talagrand, Mean field models for spin glasses: Volume I: Basic examples , Vol. 54 (Springer New York, 2010)

2010
[68]

G. G. Guerreschi and A. Y. Matsuura, QAOA for Max- Cut requires hundreds of qubits for quantum speed-up, Sci. Rep. 9, 6903 (2019)

2019
[69]

D´ ıez-Valle, D

P. D´ ıez-Valle, D. Porras, and J. J. Garc´ ıa-Ripoll, Quantum approximate optimization algorithm pseudo- Boltzmann states, Phys. Rev. Lett. 130, 050601 (2023)

2023
[70]

P. C. Lotshaw, G. Siopsis, J. Ostrowski, R. Herrman, R. Alam, S. Powers, and T. S. Humble, Approximate Boltzmann distributions in quantum approximate opti- mization, Phys. Rev. A 108, 042411 (2023)

2023
[71]

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

2019 arXiv
[72]

Akshay, H

V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, X.-M. Zhang, and J. D. Biamonte, Cir- cuit depth scaling for quantum approximate optimiza- tion, Phys. Rev. A 106, 042438 (2022)

2022
[73]

De Palma, M

G. De Palma, M. Marvian, C. Rouz´ e, and D. S. Fran¸ ca, Limitations of variational quantum algorithms: A quan- tum optimal transport approach, PRX Quantum 4, 010309 (2023). Supplemental materials for: Improving Quantum Optimization to Achieve Quadratic Time Complexity S1. PRO...

2023 arXiv
[74]

Ozaeta, W

A. Ozaeta, W. van Dam, and P. L. McMahon, Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems, Quantum Sci. Technol. 7, 045036 (2022)

2022
[75]

Bravyi, A

S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to variational quantum optimization from symmetry protection, Phys. Rev. Lett. 125, 260505 (2020)

2020
[76]

Coolsaet, S

K. Coolsaet, S. D’hondt, and J. Goedgebeur, House of Graphs 2.0: A database of interesting graphs and more, Discrete Appl. Math. 325, 97–107 (2023)

2023
[77]

Misra and D

J. Misra and D. Gries, A constructive proof of Vizing’s theorem, Information Processing Letters 41, 131 (1992)

1992
[78]

B¨ aumer and S

E. B¨ aumer and S. Woerner, Measurement-based long-range entangling gates in constant depth, arXiv preprint arXiv:2408.03064 (2024). 6

2024 arXiv
[79]

P. C. Lotshaw, T. Nguyen, A. Santana, A. McCaskey, R. Herrman, J. Ostrowski, G. Siopsis, and T. S. Humble, Scaling quantum approximate optimization on near-term hardware, Sci. Rep. 12, 12388 (2022)

2022
[80]

Farhi, D

E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: A typical case, arXiv preprint arXiv:2004.09002 (2020)

2020 arXiv
[81]

Farhi, D

E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples, arXiv preprint arXiv:2005.08747 (2020)

2020 arXiv
[82]

De Palma, M

G. De Palma, M. Marvian, C. Rouz´ e, and D. S. Fran¸ ca, Limitations of variational quantum algorithms: A quantum optimal transport approach, PRX Quantum 4, 010309 (2023)

2023
[83]

G. G. Guerreschi and A. Y. Matsuura, QAOA for Max-Cut requires hundreds of qubits for quantum speed-up, Sci. Rep. 9, 6903 (2019)

2019

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Lucas, Ising formulations of many NP problems, Front

A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014)

work page 2014

[2] [2]

Glover, G

F. Glover, G. Kochenberger, R. Hennig, and Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, Ann. Oper. Res. 314, 141 (2022)

work page 2022

[3] [3]

Herman, R

D. Herman, R. Shaydulin, Y. Sun, S. Chakrabarti, S. Hu, P. Minssen, A. Rattew, R. Yalovetzky, and M. Pistoia, Constrained optimization via quantum Zeno dynamics, Commun. Phys. 6, 219 (2023)

work page 2023

[4] [4]

Buonaiuto, F

G. Buonaiuto, F. Gargiulo, G. De Pietro, M. Esposito, and M. Pota, Best practices for portfolio optimization by quantum computing, experimented on real quantum devices, Sci. Rep. 13, 19434 (2023)

work page 2023

[5] [5]

N. N. Hegade, P. Chandarana, K. Paul, X. Chen, F. Al- barr´ an-Arriagada, and E. Solano, Portfolio optimiza- tion with digitized counterdiabatic quantum algorithms, Phys. Rev. Res. 4, 043204 (2022)

work page 2022

[6] [6]

Brandhofer, D

S. Brandhofer, D. Braun, V. Dehn, G. Hellstern, M. H¨ uls, Y. Ji, I. Polian, A. S. Bhatia, and T. Wellens, Bench- marking the performance of portfolio optimization with QAOA, Quantum Inf. Process. 22, 25 (2022)

work page 2022

[7] [7]

Stollenwerk, S

T. Stollenwerk, S. Hadfield, and Z. Wang, Toward quan- tum gate-model heuristics for real-world planning prob- lems, IEEE Transactions on Quantum Engineering 1, 1 (2020)

work page 2020

[8] [8]

Vikst˚ al, M

P. Vikst˚ al, M. Gr¨ onkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, Applying the quantum ap- proximate optimization algorithm to the tail-assignment problem, Phys. Rev. Appl. 14, 034009 (2020)

work page 2020