Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

T0 review · 3 major / 4 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 QAOA1 parameter tuning is a structured signal problem, not a black-box search.

desk verdict The paper's core reduction is real and the supposed Theorem 5 error is a misreading; referee it, but push for code and a more careful Theorem 7. read the letter →

arxiv 2501.16419 v4 pith:O37T5X7X submitted 2025-01-27 quant-ph cs.DScs.ETmath.OC

V Vijendran , Dax Enshan Koh , Eunok Bae , Hyukjoon Kwon , Ping Koy Lam , Syed M Assad This is my paper · ORCID
classification quant-phcs.DScs.ETmath.OC MSC 68Q1281P6890C27
keywords QAOAIsingmodelparameteroptimisationpartialFourierseriesNyquist-ShannonsamplingregulargraphsRQAOAQUBO
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

Level-1 QAOA on arbitrary Ising models has a notoriously hard-looking two-angle optimisation landscape, and this paper's claim is that the hardness is an illusion once the problem is seen as a signal. The expectation value is a bandlimited partial Fourier series in $\gamma$; the paper derives the exact maximum frequency from the graph's couplings and fields, so the Nyquist-Shannon theorem fixes the sampling step that prevents aliased spurious optima. It then eliminates $\beta$ analytically, reducing the search to a one-dimensional line search, and adds a subdivision algorithm whose worst-case cost is $O(N/\sqrt{\epsilon})$. For weighted regular graphs it proves that, in the infinite-size limit, the global optimum $\gamma^*$ concentrates near zero and coincides with the first local optimum, which is why gradient descent from a small initial angle works. In Recursive QAOA benchmarks on 128- and 256-qubit weighted instances, this tuning consistently beats both coarsely optimised RQAOA and semidefinite programming.

What carries the argument

The paper's load-bearing objects are (i) the partial Fourier series representation of the QAOA$_1$ cost, which turns the landscape into a bandlimited signal; (ii) the exact maximum-frequency bounds of Theorem 2 and Corollary 2, computed from edge couplings and node fields; (iii) the Nyquist-Shannon sampling step of Theorem 4, which fixes the minimum grid resolution; (iv) the analytical elimination of the mixer angle via the trigonometric reduction to $R(\gamma)\cos(4\beta-\alpha(\gamma))$ (field-free) and the quartic in $\cos(2\beta)$ (with fields); (v) the subdivision algorithm with a trigonometric maximum-modulus rejection criterion that prunes intervals and certifies the optimum; and (vi) the $\gamma=\alpha/\sqrt{D}$ scaling plus the $aD^\lambda$/$bD^\mu$ parametrisation of triangle and non-triangle neighbour counts, which produces the asymptotic cost forms in eq. (46) and the closed-form $\gamma^*$ in eq. (49). The Fourier bounds do the work of preventing aliasing; the univariate reduction does the work of removing a dimension; the scaling analysis does the work of justifying small-angle initialisation.

What would settle it

Take a sequence of weighted $(D+1)$-regular graphs with i.i.d. weights of finite second moment, let $D$ grow, and compute the exact QAOA1 optimum $\gamma^*$ by a fine line search using the Theorem 4 sampling rate. If $\gamma^*\sqrt{D}$ does not converge to a finite constant, or if a non-vanishing fraction of instances have their first local optimum differ from the global optimum, Theorem 7's conclusion fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that QAOA$_1$ parameter tuning is a structured inverse problem rather than a heuristic search. Using the closed-form expectation values for arbitrary Ising models, the authors show $\langle \gamma,\beta|H_P|\gamma,\beta\rangle$ is a partial Fourier series in $\gamma$ with integer frequencies, whose largest non-zero frequency is given exactly by Theorem 2 (with fields) and Corollary 2 (without fields). Theorem 4 turns that bound into a sampling guarantee: samples spaced at most $1/(2\nu_{\max}+1)$ determine the $\gamma$ landscape, and for commensurable weights the landscape is periodic with period $\pi$, so exact reconstruction needs only $\lceil\pi/\Delta\gamma\rceil$ evaluations. Theorems 5 and 6 give univariate objectives with $\beta^*(\gamma)$ in closed form, and a subdivision algorithm based on Steckin's lemma returns a near-optimal $\gamma^*$ in $O(N/\sqrt{\epsilon})$ steps with a certificate. Theorem 7 then proves for weighted $(D+1)$-regular graphs with i.i.d. weights of finite second moment that the scaled expected cost has the leading-order forms in eq. (46), that $\gamma^* = \alpha^*/\sqrt{D}$ with $\alpha^*$ given in closed form, and that this global optimum coincides with the first local optimum for $\gamma\in\mathbb{R}^+$.

Load-bearing premise

The large-graph concentration theorem assumes the optimal gamma shrinks as $1/\sqrt{D}$ and that each edge's triangle and non-triangle neighbour counts follow the power-law cases in eq. (46); if a regular graph family violates either assumption, the near-zero global optimum and its equality with the first local optimum do not follow.

Editorial extensions

If this is right

  • A coarse grid over $(\gamma,\beta)$ is not a safe default: aliasing can hide the true optimum, and the required $\gamma$ resolution is computed exactly from the instance's couplings and fields.
  • QAOA$_1$ optimisation is polynomial-time structured: a line search with $\beta^*$ analytic, plus the subdivision algorithm, locates near-optimal $\gamma^*$ with $O(N/\sqrt{\epsilon})$ evaluations.
  • For regular weighted graphs at large size, the global $\gamma^*$ is near zero and equals the first local optimum, so gradient descent initialised within the Nyquist step finds it without a full line search.
  • These optimal $p=1$ parameters are directly usable as warm starts for deeper QAOA, improving convergence over random initialisation.
  • Used inside Recursive QAOA, this tuning beats both a coarse-search RQAOA and a semidefinite relaxation on weighted 128- and 256-qubit random-graph instances.

Reading between the lines

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

  • Not argued by the paper, but a direct consequence: the same maximum-frequency bound fixes a safe step size for gradient-based optimisers, since any step larger than the Nyquist spacing can jump over the first local optimum.
  • Theorem 7 suggests instance-family parameter transfer: once the weight distribution and degree are known, $\gamma^*\approx \alpha^*/\sqrt{D}$ is fixed up to the constants $E[J]$, $E[J^2]$ and the triangle-count parameters, so similar instances share near-optimal angles without instance-wise search.
  • The adversarial-instance frequency data in the paper is evidence, not a theorem; a natural testable extension is whether the near-zero alignment persists for non-regular graphs, sparse graphs, or heavy-tailed weight distributions outside the i.i.d. assumption.
  • The Fourier view yields a pre-screening metric: instances whose maximum frequency is high need fine sampling, so computing $\omega_{\max}$ before optimisation tells a user when naive grid search will fail.
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.

Referee Report

3 major / 4 minor

Summary. This paper studies classical parameter tuning for QAOA at depth p=1 on arbitrary Ising models. The authors show that the QAOA1 expectation value is a partial Fourier series in γ, derive instance-wise bounds on its maximum frequency (Theorem 2 and Corollaries 2–4), and use Nyquist–Shannon sampling to set a resolution for searches along γ (Theorem 4). They eliminate the mixer angle analytically, reducing the search to a univariate objective over γ (Theorem 5 without fields, Theorem 6 with fields), and propose to optimize that objective with a subdivision algorithm claimed to certify the global optimum in polynomial time. For (D+1)-regular graphs with i.i.d. weights, Theorem 7 asserts, under a scaling assumption γ=Θ(D^{-1/2}) and a parametrized triangle-count model, that the global optimum γ* concentrates near zero and equals the first local optimum. The strategy is validated by benchmarking RQAOA and an iterative variant (Iter-QAOA) against coarse-grid RQAOA and a classical semidefinite program on Erdős–Rényi instances of 128 and 256 spins. The central claim is that QAOA1 parameter tuning is a structured, polynomial-time problem rather than a heuristic black-box search.

Significance. If the central reduction were correct, this paper would be a valuable contribution to the QAOA parameter-optimization literature: it replaces heuristic grids with a certified one-dimensional search, provides explicit bandwidth-based sampling resolutions, and gives a rigorous account of small-angle initialization for regular graphs. The frequency bounds in Theorem 2 and Corollaries 2–4 are clean, parameter-free, and directly falsifiable on random instances; the numerical protocol is appropriately external, using Gurobi ground states as reference and a Goemans–Williamson-style SDP as baseline; and the quartic-based β elimination in Theorem 6 checks out algebraically. These strengths should be preserved in a revision. However, the algebraic error in Theorem 5 sits in the load-bearing objective of the entire pipeline (line search, subdivision, benchmarks); the certificate claim for Algorithm 1 is not justified for the function actually optimized; and the asymptotic error estimates of Theorem 7 require a consistency fix in the case parametrization. As printed, the quantitative claims in Figures 3, 5, and 6 are not supported.

major comments (3)
  1. [II.B.4, Theorem 5, Eq. (39); Appendix E1] This is a load-bearing algebraic error. From the paper's own definitions, ⟨γ,β|HP|γ,β⟩ = A(γ) sin 4β − B(γ) sin² 2β = A sin 4β + (B/2) cos 4β − B/2 (Eq. (E3)). Minimizing over β gives min = −√(A² + B²/4) − B/2, but Eq. (39) states −√(A² + B²)/4 − B/2, and Eqs. (E6)–(E7) in Appendix E1 repeat the error. The two expressions differ by a factor of four: for a single field-free edge with J=1 one has A = sin 2γ, B = 0, and direct minimization yields min_β ⟨HP⟩ = −|sin 2γ|, while Eq. (39) gives −|sin 2γ|/4. This is not a modeling assumption but a mistake in the central theorem. The univariate objective (39) is what Algorithm 1 optimizes, what Figures 2 and 3 plot as the "optimal path", and what the RQAOA/Iter-QAOA parameter optimization in Section II.C is built on ("analytical solutions derived from theorem 5 and theorem 6"). The β* formula (41) may survive, but the γ-line-search objective, the approximation ratios in Figures 3, 5, and 6, and the adversarial-instance statistics in Figure 4 must all be re-derived and re-run with the corrected expression.
  2. [II.B.5, Algorithm 1 and Theorem 12; Appendix G] The certificate-of-optimality claim is not supported by the arguments given. Algorithm 1 is applied to q(γ) = ⟨γ,β*_γ|HP|γ,β*_γ⟩², but Lemma 10 (Steckin) and Theorem 12 require q to be a real trigonometric polynomial of degree N. The univariate objective (39) contains √(A² + B²/4); after squaring, q = A² + B²/2 + B√(A² + B²/4), which is not a trigonometric polynomial for generic A(γ), B(γ). The envelope function min_β f(γ,β) need not be bandlimited in the sense of Definition 1 either: Figure 2 itself shows discontinuities in the optimal path arising from abrupt switches of β*(γ). The multivariate Steckin bound (Lemma 11) applies only to trigonometric polynomials in (γ,β), and the paper's argument that restricting to the path (γ,β*_γ) reduces to the univariate case does not close the gap, because the value of the envelope at γ₀+s can drop faster than the cos bound at fixed β. A separate envelope bound, or a genuinely multivariate subdivision over f(γ,β)², is needed before the claimed polynomial-time global optimum with certificate is established.
  3. [II.B.6, Theorem 7, Eq. (46); Appendix H, Step 3] The case architecture of Theorem 7 treats a and b in |F̄_uv| = aD^λ and |F_uv| = bD^μ as constants independent of D, but on a (D+1)-regular graph the two counts must satisfy |F̄_uv| + |F_uv| = D exactly. In the mixed regimes this forces one parameter to be D-dependent: for μ=1 and λ<1, regularity gives b = 1 − aD^{λ−1}, so b → 1 with a drift O(D^{λ−1}); similarly, for λ=1 and μ<1, a = 1 − bD^{μ−1}. The error terms declared in Eq. (46) are smaller than this drift in some cases — for example, the μ=1, λ<1/2 case claims O(D^{−1}) while the drift is O(D^{λ−1}), and the λ=1, μ>1/2 case claims O(D^{−1/2}) while the drift is O(D^{μ−1}) — so the leading-order cost expressions and, in particular, the closed-form optimal γ* values in Eq. (49) (such as η(2a) and ζ(b,b)) are not justified in those regimes. Because Theorem 7 is the basis for the paper's headline claim that γ* concentrates near zero and equals the first local optimum, this consistency issue needs to be resolved — either by reformulating the parametrization to respect the exact constraint or by checking the claimed error orders numerically on random (D+1)-regular graphs in each regime.
minor comments (4)
  1. [Appendix E1] The proof of Theorem 5 states that the minimum is achieved at β* = α(γ*) + π/4, which is inconsistent with the theorem's own β* = (1/4)(arctan(2A, B) + π); the two expressions differ by a factor of four in the arctangent argument and should be reconciled. This inconsistency compounds the algebraic error in Eq. (39).
  2. [II.B.3, Theorem 3] The sampling bound T_s ≤ 1/(2B+1) is not the standard Nyquist–Shannon condition (usually T_s ≤ 1/(2B)); the '+1' variant is conservative, so the subsequent bounds remain valid, but the statement of 'exact reconstruction' should be justified with respect to the standard theorem or the variant should be flagged as a non-tight sufficient condition.
  3. [II.B.3, Theorem 4] The assertion that integer weights imply a maximum period T_γ = π needs a one-line justification; the period π follows from the factor-2 prefactor in γ′ = 2Jγ together with the integrality of the frequencies, and the text should spell this out rather than stating it as immediate.
  4. [II.B.6, Figure 4] The text claims that adversarial instances 'decrease exponentially with increasing graph size or density', but the figure shows a probability that stabilizes near 0.01 for graphs with more than about 14 nodes; the claim is stronger than the displayed evidence and should be reworded or supplemented with fitted decay curves.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the univariate reduction and sampling bounds are built on external closed-form expressions and standard sampling theory; only minor non-load-bearing self-citations are present.

full rationale

The derivation chain is self-contained: Theorem 1/Corollary 1 are quoted from Ozaeta et al. [18]; Theorem 2 applies product-to-sum lemmas to those expressions; Theorem 4 is Nyquist-Shannon applied to the resulting bandlimit; Theorem 5 eliminates beta algebraically from A(gamma) and B(gamma), which are defined from the same external expectation formula. None of these steps fits a parameter to data and then reports it as a prediction. Theorem 7 is an asymptotic expansion under the explicitly stated ansatz 'By assuming that gamma proportional to D^{-1/2}, we derive closed-form expressions...' (Section II.B.6), so the conclusion gamma* = eta/sqrt(D) is conditional on that scaling assumption. This is a transparent modeling/scope limitation, not a hidden circularity: the ansatz is motivated by external results (Boulebnane-Montanaro; Sureshbabu et al.), and the proof does not claim to establish the scaling from scratch. The RQAOA benchmarks use GUROBI ground states and a classical Goemans-Williamson SDP, so performance claims are externally falsifiable. Self-citations [19] and [92] are used for related expressions and illustrative empirical observations; neither is load-bearing for the central univariate reduction, frequency bound, or first-local-optimum result. Separately, Theorem 5 Eq. (39) prints -sqrt(A^2+B^2)/4 - B/2 while Appendix E 1 derives -B/2 - sqrt(A^2+B^2/4); this is an apparent algebraic error affecting the printed univariate objective and Figures 2-3, but it is not a circular step because the objective is not defined in terms of its own minimizer. Score 2 reflects minor, non-load-bearing self-citations, not a circular reduction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The theory introduces no invented entities and no data-fitted parameters; however, it leans on the known QAOA1 expectation formulas, a scaling ansatz, and several standard theorems. The central numerical method has no free parameters beyond the problem instance data itself.

assumptions (6)
  • standard math Nyquist-Shannon sampling theorem
    Used in Theorem 4 to derive the sampling resolution for exact reconstruction of the QAOA1 cost landscape; standard result.
  • standard math Steckin's lemma
    Used as the rejection criterion in Algorithm 1 for the subdivision search; cited to Edwards [110].
  • domain assumption Analytical expectation formulas of Ozaeta et al. (Theorem 1 and Corollary 1)
    The entire analysis builds on these p=1 closed forms; the paper cites Ozaeta et al. [18] for the proofs.
  • ad hoc to paper Scaling assumption gamma = Theta(D^{-1/2}) for regular graphs
    The asymptotic Theorem 7 assumes this scaling to derive the leading-order cost; motivated by numerics and prior work, but not proven from first principles.
  • domain assumption Interchange of summation and expectation in Taylor expansions
    Assumed in Appendix H.1.b for the expectation computations; requires probability densities with sufficient decay.
  • domain assumption Commensurable and bounded weights for polynomial-time certification
    The claimed polynomial-time global search with certificate requires commensurable, bounded weights; stated in the abstract and Section II.B.5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models." pith.science (2026). https://pith.science/paper/O37T5X7X

@misc{pith2026250116419,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O37T5X7X}},
  note         = {Machine review of arXiv:2501.16419}
}
abstract

The Quantum Approximate Optimisation Algorithm (QAOA) tackles combinatorial optimisation problems by encoding their solutions into the ground state of an Ising Hamiltonian prepared by a $p$-level parameterised circuit, with the angles tuned classically. Parameter optimisation is widely regarded as a central bottleneck, even for the shallowest circuits. Focusing on QAOA at $p=1$ (QAOA$_1$), we show that tuning the two angles $(\gamma, \beta)$ for weighted Ising models is not a black-box search but a structured signal-processing problem. We prove that the QAOA$_1$ expectation value is a partial Fourier series in $\gamma$ whose frequencies are determined explicitly by the problem's couplings and fields, giving instance-wise bandwidth bounds and, via the Nyquist--Shannon theorem, the sampling resolution needed to avoid the aliasing that causes coarse-grid searches to return spurious optima. We then eliminate the mixer angle analytically, computing $\beta^*(\gamma)$ in closed form to reduce the search to one dimension, and apply a subdivision algorithm that locates the globally optimal $\gamma$ in polynomial time with a certificate of optimality when the weights are commensurable and bounded. For regular weighted graphs, we further prove the conventional wisdom that the globally optimal $\gamma^* \in \mathbb{R}^+$ concentrates near zero and coincides with the first local optimum, giving a rigorous account of the empirical success of small-angle initialisation and allowing gradient descent to replace exhaustive line searches. Validated within Recursive QAOA (RQAOA) on weighted instances of 128 and 256 qubits, our method consistently outperforms both coarsely optimised RQAOA and semidefinite programming.

Figures

Figures reproduced from arXiv: 2501.16419 by the authors.

Figure 1
Figure 1. FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7 [PITH_FULL_IMAGE:figures/full_fig_p025_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting

    quant-ph 2026-07 conditional novelty 6.0 of 10

    Bitflip-gauge warm-start QAOA that aligns the ansatz with amplitude-damping noise improves 100-qubit Ising approximation ratios over non-gauge iterative warm-start at no extra circuit cost.

Reference graph

Works this paper leans on

126 extracted references · 58 canonical work pages · cited by 1 Pith paper

  1. [1]

    Consider the case without external fields

    Sherrington-Kirkpatrick Model Proof of Corollary 3. Consider the case without external fields. The maximum angular frequency of the γ terms in the expectation value is ωmax h ⟨Cuv⟩γ i = 2× max   |Juv|+max (X w∈e |Jwv|, X w∈d |Juw| ) ,max    X f ∈F |Juf ±Jvf |       . (D1) Since the graph is complete, the number of neighbours excluding vertices...

    work page

  2. [2]

    For a triangle-free graph, the maximum angular frequency of the γ terms in the expectation value is given by: ωmax h ⟨Cuv⟩γ i = 2|Juv| + 2 × max (X w∈e |Jwv|, X w∈d |Juw| )

    T riangle-F ree Graphs Proof of Corollary 4. For a triangle-free graph, the maximum angular frequency of the γ terms in the expectation value is given by: ωmax h ⟨Cuv⟩γ i = 2|Juv| + 2 × max (X w∈e |Jwv|, X w∈d |Juw| ) . (D5) Since the graph is D-regular, each vertex has D − 1 neighbours excluding u and v, so |e| = |d| = D − 1. Consequently, max (X w∈e |Jw...

    work page

  3. [3]

    (H36) 37 Proof

    For the (D + 1)-th power of expectation: E x∼p cos ax√ D D+1 = e − 1 2 a2 E x∼p[x2] " 1 + − 1 2 a2 E x∼p x2 + 1 4! a4 E x∼p x4 − 1 8 a4 E x∼p x2 2 ! 1 D + O 1 D2 # = e − 1 2 a2 E x∼p[x2] 1 + O 1 D . (H36) 37 Proof. 1. For the first result, we compute: E x∼p cos ax√ D = E x∼p   ∞X k=0 k even (−1)k/2 k! ax√ D k    using cos x = ∞X k=0 k even (−1)k/...

    work page

  4. [4]

    Cheng, X.-H

    B. Cheng, X.-H. Deng, X. Gu, Y. He, G. Hu, P. Huang, J. Li, B.-C. Lin, D. Lu, Y. Lu, C. Qiu, H. Wang, T. Xin, S. Yu, M.-H. Yung, J. Zeng, S. Zhang, Y. Zhong, X. Peng, F. Nori, and D. Yu, Noisy intermediate-scale quantum computers, Frontiers of Physics 18, 21308 (2023)

    2023

  5. [5]

    Cerezo, A

    M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, et al. , Variational quantum algorithms, Na- ture Reviews Physics 3, 625 (2021)

    2021

  6. [6]

    Bharti, A

    K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, et al. , Noisy intermediate- scale quantum algorithms, Reviews of Modern Physics 94, 015004 (2022)

    2022

  7. [7]

    Bittel and M

    L. Bittel and M. Kliesch, Training variational quantum algorithms is NP-Hard, Physical Review Letters 127, 120502 (2021)

    2021

  8. [8]

    J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Bab- bush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature communications 9, 4812 (2018)

    2018

Show all 126 references
  1. [9]

    E. R. Anschuetz and B. T. Kiani, Quantum variational algorithms are swamped with traps, Nature Communi- cations 13, 7760 (2022)

    2022

  2. [10]

    S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature communications 12, 6961 (2021)

    2021

  3. [11]

    Cerezo, A

    M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shal- low parametrized quantum circuits, Nature communi- cations 12, 1791 (2021)

    2021

  4. [12]

    Ortiz Marrero, M

    C. Ortiz Marrero, M. Kieferov´ a, and N. Wiebe, Entanglement-induced barren plateaus, PRX Quantum 2, 040316 (2021)

    2021

  5. [13]

    N. A. Nemkov, E. O. Kiktenko, and A. K. Fedorov, Bar- ren plateaus are swamped with traps, arXiv preprint arXiv:2405.05332 (2024)

    2024 arXiv

  6. [14]

    Farhi, J

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

    2014 arXiv

  7. [15]

    Weidenfeller, L

    J. Weidenfeller, L. C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D. J. Egger, Scaling of the quantum approximate optimization algorithm on su- perconducting qubit based hardware, Quantum 6, 870 (2022)

    2022

  8. [16]

    S. A. Hadfield, Quantum algorithms for scientific com- puting and approximate optimization , Ph.D. thesis, Columbia University (2018)

    2018

  9. [17]

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

    2018

  10. [18]

    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- ence and Technology 7, 045036 (2022)

    2022

  11. [19]

    Vijendran, A

    V. Vijendran, A. Das, D. E. Koh, S. M. Assad, and P. K. Lam, An expressive ansatz for low-depth quan- tum approximate optimisation, Quantum Science and Technology 9, 025010 (2024)

    2024

  12. [20]

    Basso, E

    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, in 17th Conference on the Theory of Quantum Computation, Communication and ...

    2022

  13. [21]

    T. Y. Ng, J. M. Koh, and D. E. Koh, Analytical expres- sions for the quantum approximate optimization algo- rithm and its variants, arXiv preprint arXiv:2411.09745 (2024)

    2024 arXiv

  14. [22]

    Wurtz and D

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

    2021

  15. [23]

    F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, For fixed control parameters the quan- tum approximate optimization algorithm’s objective function value concentrates for typical instances, arXiv preprint arXiv:1812.04170 (2018)

    2018 arXiv

  16. [24]

    Akshay, D

    V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, Parameter concentrations in quantum approximate op- timization, Physical Review A 104, L010401 (2021)

    2021

  17. [25]

    Katial, K

    V. Katial, K. Smith-Miles, and C. Hill, On the instance dependence of optimal parameters for the quadratic ap- proximate optimisation algorithm: Insights via instance space analysis, arXiv preprint arXiv:2401.08142 (2024)

    2024 arXiv

  18. [26]

    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 Confer- ence on Quantum Computing and Engineering (QCE) (IEEE, 2021) pp. 171–180

    2021

  19. [27]

    Galda, E

    A. Galda, E. Gupta, J. Falla, X. Liu, D. Lykov, Y. Alex- eev, and I. Safro, Similarity-based parameter transfer- ability in the quantum approximate optimization algo- rithm, Frontiers in Quantum Science and Technology2, 1200975 (2023)

    2023

  20. [28]

    Brundin and L

    I. Brundin and L. Garc ´ ıa-´Alvarez, Symmetry-informed transferability of optimal parameters in the quantum 22 approximate optimization algorithm, arXiv preprint arXiv:2407.04496 (2024)

    2024 arXiv

  21. [29]

    Langfitt, J

    Q. Langfitt, J. Falla, I. Safro, and Y. Alexeev, Parame- ter transferability in QAOA under noisy conditions, in 2023 IEEE International Conference on Quantum Com- puting and Engineering (QCE) , Vol. 2 (IEEE, 2023) pp. 300–301

    2023

  22. [30]

    Sakai, H

    R. Sakai, H. Matsuyama, W.-H. Tam, Y. Yamashiro, and K. Fujii, Linearly simplified QAOA parameters and transferability, arXiv preprint arXiv:2405.00655 (2024)

    2024 arXiv

  23. [31]

    S. H. Sack and M. Serbyn, Quantum annealing initial- ization of the quantum approximate optimization algo- rithm, Quantum 5, 491 (2021)

    2021

  24. [32]

    Liang, L

    D. Liang, L. Li, and S. Leichenauer, Investigating quan- tum approximate optimization algorithms under bang- bang protocols, Physical Review Research 2, 033402 (2020)

    2020

  25. [33]

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

    2022

  26. [34]

    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, Physical Review X 10, 021067 (2020)

    2020

  27. [35]

    Ni, B.-B

    X.-H. Ni, B.-B. Cai, H.-L. Liu, S.-J. Qin, F. Gao, and Q.-Y. Wen, Multilevel leapfrogging initialization strat- egy for quantum approximate optimization algorithm, Advanced Quantum Technologies 7, 2300419 (2024)

    2024

  28. [36]

    X. Lee, N. Xie, D. Cai, Y. Saito, and N. Asai, A depth- progressive initialization strategy for quantum approx- imate optimization algorithm, Mathematics 11, 2176 (2023)

    2023

  29. [37]

    Shaydulin, P

    R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, Parameter transfer for quantum approximate optimization of weighted MaxCut, ACM Transactions on Quantum Computing 4, 1 (2023)

    2023

  30. [38]

    Stechly, L

    M. Stechly, L. Gao, B. Yogendran, E. Fontana, and M. Rudolph, Connecting the Hamiltonian structure to the QAOA energy and Fourier landscape structure, arXiv preprint arXiv:2305.13594 (2023)

    2023 arXiv

  31. [39]

    M. Alam, A. Ash-Saki, and S. Ghosh, Accelerating quantum approximate optimization algorithm using machine learning, in 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE) (IEEE, 2020) pp. 686–689

    2020

  32. [40]

    N. Xie, X. Lee, D. Cai, Y. Saito, and N. Asai, Quantum approximate optimization algorithm parameter predic- tion using a convolutional neural network, Journal of Physics: Conference Series 2595, 012001 (2023)

    2023

  33. [41]

    Liang, G

    Z. Liang, G. Liu, Z. Liu, J. Cheng, T. Hao, K. Liu, H. Ren, Z. Song, J. Liu, F. Ye, and Y. Shi, Invited: Graph learning for parameter prediction of quantum ap- proximate optimization algorithm, in Proceedings of the 61st ACM/IEEE Design Automation Conference , DAC ’24 (Associa...

    2024

  34. [42]

    Meng and X

    F. Meng and X. Zhou, Parameter generation of quan- tum approximate optimization algorithm with diffusion model, arXiv preprint arXiv:2407.12242 (2024)

    2024 arXiv

  35. [43]

    Amosy, T

    O. Amosy, T. Danzig, O. Lev, E. Porat, G. Chechik, and A. Makmal, Iteration-free quantum approximate optimization algorithm using neural networks, Quan- tum Machine Intelligence 6, 38 (2024)

    2024

  36. [44]

    Khairy, R

    S. Khairy, R. Shaydulin, L. Cincio, Y. Alexeev, and P. Balaprakash, Reinforcement-learning-based varia- tional quantum circuits optimization for combinatorial problems, arXiv preprint arXiv:1911.04574 (2019)

    2019 arXiv

  37. [45]

    Montanez-Barrera, D

    J. Montanez-Barrera, D. Willsch, and K. Michielsen, Transfer learning of optimal QAOA parameters in combinatorial optimization, arXiv preprint arXiv:2402.05549 (2024)

    2024 arXiv

  38. [46]

    Falla, Q

    J. Falla, Q. Langfitt, Y. Alexeev, and I. Safro, Graph representation learning for parameter transferability in quantum approximate optimization algorithm, Quan- tum Machine Intelligence 6, 46 (2024)

    2024

  39. [47]

    Cheng, Y.-Q

    L. Cheng, Y.-Q. Chen, S.-X. Zhang, and S. Zhang, Quantum approximate optimization via learning-based adaptive optimization, Communications Physics 7, 83 (2024)

    2024

  40. [48]

    Bravyi, A

    S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Ob- stacles to variational quantum optimization from sym- metry protection, Physical Review Letters 125, 260505 (2020)

    2020

  41. [49]

    S. Kim, T. Luo, E. Lee, and I.-S. Suh, Distributed quan- tum approximate optimization algorithm on integrated high-performance computing and quantum computing systems for large-scale optimization, arXiv preprint arXiv:2407.20212 (2024)

    2024 arXiv

  42. [50]

    B. Yue, S. Xue, Y. Pan, M. Jiang, and D. Dong, Lo- cal to global: A distributed quantum approximate op- timization algorithm for pseudo-Boolean optimization problems, arXiv preprint arXiv:2310.05062 (2023)

    2023 arXiv

  43. [51]

    K.-C. Chen, X. Xu, F. Burt, C.-Y. Liu, S. Yu, and K. K. Leung, Noise-aware distributed quantum approx- imate optimization algorithm on near-term quantum hardware, in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) , Vol. 02 (2024) pp. 144–149

    2024

  44. [52]

    J. R. Finˇ zgar, A. Kerschbaumer, M. J. Schuetz, C. B. Mendl, and H. G. Katzgraber, Quantum-informed re- cursive optimization algorithms, PRX Quantum 5, 020327 (2024)

    2024

  45. [53]

    L. T. Brady and S. Hadfield, Iterative quantum algo- rithms for maximum independent set, Physical Review A 110, 052435 (2024)

    2024

  46. [54]

    B. Bach, J. Falla, and I. Safro, MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multi- level QAOA, in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) , Vol. 01 (2024) pp. 1–12

    2024

  47. [55]

    Z. Zhou, Y. Du, X. Tian, and D. Tao, QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines, Physical Review Applied 19, 024027 (2023)

    2023

  48. [56]

    Ponce, R

    M. Ponce, R. Herrman, P. C. Lotshaw, S. Powers, G. Siopsis, T. Humble, and J. Ostrowski, Graph decom- position techniques for solving combinatorial optimiza- tion problems with variational quantum algorithms, arXiv preprint arXiv:2306.00494 (2023)

    2023 arXiv

  49. [57]

    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, Science Advances 9, eadi0487 (2023)

    2023

  50. [58]

    Dupont and B

    M. Dupont and B. Sundar, Extending relax-and-round combinatorial optimization solvers with quantum corre- lations, Physical Review A 109, 012429 (2024). 23

    2024

  51. [59]

    L. Caha, A. Kliesch, and R. Koenig, Twisted hybrid al- gorithms for combinatorial optimization, Quantum Sci- ence and Technology 7, 045013 (2022)

    2022

  52. [60]

    Fischer, M

    V. Fischer, M. Passek, F. Wagner, J. R. Finˇ zgar, L. Palackal, and C. B. Mendl, Quantum and classical correlations in shrinking algorithms for optimization, arXiv preprint arXiv:2404.17242 (2024)

    2024 arXiv

  53. [61]

    A. P. Punnen, The quadratic unconstrained binary op- timization problem, Springer International Publishing 10, 978 (2022)

    2022

  54. [62]

    Schuld, R

    M. Schuld, R. Sweke, and J. J. Meyer, Effect of data encoding on the expressive power of variational quantum-machine-learning models, Physical Review A 103, 032430 (2021)

    2021

  55. [63]

    F. J. Gil Vidal and D. O. Theis, Input redundancy for parameterized quantum circuits, Frontiers in Physics 8, 297 (2020)

    2020

  56. [64]

    Fontana, I

    E. Fontana, I. Rungger, R. Duncan, and C. C ˆ ırstoiu, Spectral analysis for noise diagnostics and filter- based digital error mitigation, arXiv preprint arXiv:2206.08811 (2022)

    2022 arXiv

  57. [65]

    Fontana, I

    E. Fontana, I. Rungger, R. Duncan, and C. C ˆ ırstoiu, Ef- ficient recovery of variational quantum algorithms land- scapes using classical signal processing, arXiv preprint arXiv:2208.05958 (2022)

    2022 arXiv

  58. [66]

    N. A. Nemkov, E. O. Kiktenko, and A. K. Fedorov, Fourier expansion in variational quantum algorithms, Physical Review A 108, 032406 (2023)

    2023

  59. [67]

    C. E. Shannon, Communication in the presence of noise, Proceedings of the IRE 37, 10 (1949)

    1949

  60. [68]

    T. Hao, K. Liu, and S. Tannu, Enabling high perfor- mance debugging for variational quantum algorithms using compressed sensing, in Proceedings of the 50th Annual International Symposium on Computer Archi- tecture (2023) pp. 1–13

    2023

  61. [69]

    M¨ ussig, M

    D. M¨ ussig, M. Wappler, S. Lenk, and J. L¨ assig, Connecting the Hamiltonian structure to the QAOA performance and energy landscape, arXiv preprint arXiv:2407.04435 (2024)

    2024 arXiv

  62. [70]

    Ch´ avez-Pichardo, M

    M. Ch´ avez-Pichardo, M. A. Mart ´ ınez-Cruz, A. Trejo- Mart ´ ınez, D. Mart ´ ınez-Carbajal, and T. Arenas- Resendiz, A complete review of the general quartic equation with real coefficients and multiple roots, Math- ematics 10, 2377 (2022)

    2022

  63. [71]

    J. P. Boyd, Computing the zeros, maxima and inflec- tion points of Chebyshev, Legendre and Fourier series: solving transcendental equations by spectral interpola- tion and polynomial rootfinding, Journal of Engineering Mathematics 56, 203 (2006)

    2006

  64. [72]

    J. P. Boyd, A comparison of companion matrix methods to find roots of a trigonometric polynomial, Journal of Computational Physics 246, 96 (2013)

    2013

  65. [73]

    Kalantari, F

    B. Kalantari, F. Andreev, and C. Lau, Characteriza- tion of local optima of polynomial modulus over a disc, Numerical Algorithms 90, 773 (2022)

    2022

  66. [74]

    E. R. Hansen, Global optimization using interval anal- ysis: the one-dimensional case, Journal of Optimization Theory and Applications 29, 331 (1979)

    1979

  67. [75]

    Hansen and G

    E. Hansen and G. W. Walster, Global optimization using interval analysis: revised and expanded , Vol. 264 (CRC press, 2003)

    2003

  68. [76]

    J. J. Green, Calculating the maximum modulus of a polynomial using Steckin’s lemma, SIAM Journal on Numerical Analysis 36, 1022 (1999)

    1999

  69. [77]

    De La Chevrotiere, Finding the maximum modulus of a polynomial on the polydisk using a generalization of Steckin’s lemma, SIAM Undergraduate Research Online 2, 2 (2009)

    G. De La Chevrotiere, Finding the maximum modulus of a polynomial on the polydisk using a generalization of Steckin’s lemma, SIAM Undergraduate Research Online 2, 2 (2009)

    2009

  70. [78]

    Emeliyanenko and M

    P. Emeliyanenko and M. Sagraloff, On the complexity of solving a bivariate polynomial system, in Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (2012) pp. 154–161

    2012

  71. [79]

    Plestenjak and M

    B. Plestenjak and M. E. Hochstenbach, Roots of bivari- ate polynomial systems via determinantal representa- tions, SIAM Journal on Scientific Computing 38, A765 (2016)

    2016

  72. [80]

    Boulebnane, X

    S. Boulebnane, X. Lucas, A. Meyder, S. Adaszewski, and A. Montanaro, Peptide conformational sampling us- ing the quantum approximate optimization algorithm, npj Quantum Information 9, 70 (2023)

    2023

  73. [81]

    Brandhofer, D

    S. Brandhofer, D. Braun, V. Dehn, G. Hellstern, M. H¨ uls, Y. Ji, I. Polian, A. S. Bhatia, and T. Wellens, Benchmarking the performance of portfolio optimiza- tion with QAOA, Quantum Information Processing 22, 25 (2022)

    2022

  74. [82]

    Boulebnane and A

    S. Boulebnane and A. Montanaro, Predicting param- eters for the quantum approximate optimization algo- rithm for MAX-CUT from the infinite-size limit, arXiv preprint arXiv:2110.10685 (2021)

    2021 arXiv

  75. [83]

    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

  76. [84]

    Erd¨ os and A

    P. Erd¨ os and A. R´ enyi, On random graphs I, Publ. math. debrecen 6, 290 (1959)

    1959

  77. [85]

    E. N. Gilbert, Random graphs, The Annals of Mathe- matical Statistics 30, 1141 (1959)

    1959

  78. [86]

    Gurobi Optimization, LLC, Gurobi Optimizer Refer- ence Manual (2022)

    2022

  79. [87]

    M. X. Goemans and D. P. Williamson, Improved ap- proximation algorithms for maximum cut and satisfia- bility problems using semidefinite programming, Jour- nal of the ACM (JACM) 42, 1115 (1995)

    1995

  80. [88]

    Bravyi, A

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

    2022

  81. [89]

    Y. J. Patel, S. Jerbi, T. B¨ ack, and V. Dunjko, Reinforce- ment learning assisted recursive QAOA, EPJ Quantum Technology 11, 6 (2024)

    2024

  82. [90]

    Bravyi, D

    S. Bravyi, D. Gosset, D. Grier, and L. Schaeffer, Classical algorithms for forrelation, arXiv preprint arXiv:2102.06963 (2021)

    2021 arXiv

  83. [91]

    Bae and S

    E. Bae and S. Lee, Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs, Quantum Information Processing 23, 78 (2024)

    2024

  84. [92]

    E. Bae, H. Kwon, V. Vijendran, and S. Lee, Modified Recursive QAOA for Exact Max-Cut Solutions on Bi- partite Graphs: Closing the Gap Beyond QAOA Limit, arXiv preprint arXiv:2408.13207 (2024)

    2024

  85. [93]

    Moussa, H

    C. Moussa, H. Wang, T. B¨ ack, and V. Dunjko, Unsu- pervised strategies for identifying optimal parameters in quantum approximate optimization algorithm, EPJ Quantum Technology 9, 11 (2022)

    2022

  86. [94]

    Thelen, H

    S. Thelen, H. Safi, and W. Mauerer, Approximat- ing under the Influence of Quantum Noise and Com- pute Power, in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE Computer Society, Los Alamitos, CA, USA, 2024) pp. 24 274–279

    2024

  87. [95]

    D. J. Egger, J. Mareˇ cek, and S. Woerner, Warm-starting quantum optimization, Quantum 5, 479 (2021)

    2021

  88. [96]

    D. P. Williamson and D. B. Shmoys, The design of ap- proximation algorithms (Cambridge University Press, 2011)

    2011

  89. [97]

    L. C. Lau, R. Ravi, and M. Singh, Iterative methods in combinatorial optimization, Vol. 46 (Cambridge Univer- sity Press, 2011)

    2011

  90. [98]

    M. H. Freedman and M. B. Hastings, Quantum sys- tems on non- k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs, Quantum Information & Computation 14, 144 (2014)

    2014

  91. [99]

    Farhi, D

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

    2020 arXiv

  92. [100]

    Farhi, D

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

    2020 arXiv

  93. [101]

    Basso, D

    J. Basso, D. Gamarnik, S. Mei, and L. Zhou, Perfor- mance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022) pp. 335–343

    2022

  94. [102]

    Anshu and T

    A. Anshu and T. Metger, Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations, Quantum 7, 999 (2023)

    2023

  95. [103]

    Barak and K

    B. Barak and K. Marwaha, Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs, in 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 215, edited by M. Braverman ...

    2022

  96. [104]

    M. X. H. Goh, The overlap gap property limits limit swapping in QAOA, arXiv preprint arXiv:2404.06087 (2024)

    2024

  97. [105]

    Akshay, H

    V. Akshay, H. Philathong, M. E. Morales, and J. D. Bi- amonte, Reachability deficits in quantum approximate optimization, Physical Review Letters 124, 090504 (2020)

    2020

  98. [106]

    Akshay, H

    V. Akshay, H. Philathong, I. Zacharov, and J. Bia- monte, Reachability deficits in quantum approximate optimization of graph problems, Quantum 5, 532 (2021)

    2021

  99. [107]

    A. Chen, N. Huang, and K. Marwaha, Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs, arXiv preprint arXiv:2310.01563 (2023)

    2023 arXiv

  100. [108]

    C.-N. Chou, P. J. Love, J. S. Sandhu, and J. Shi, Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond, in 49th International Col- loquium on Automata, Languages, and Programming (ICALP 2022), Leibniz International Proceedings in In- formatics (LIPIcs), Vol. ...

    2022

  101. [109]

    Marwaha and S

    K. Marwaha and S. Hadfield, Bounds on approximat- ing Max kXOR with quantum and classical local algo- rithms, Quantum 6, 757 (2022)

    2022

  102. [110]

    R. E. Edwards, Fourier Series: A Modern Introduction Volume 1 , 2nd ed., Graduate Texts in Mathematics, Vol. 2 (Springer-Verlag New York, NY, 1979) pp. XII, 228. 25 SUPPLEMENT AR Y MA TERIAL Appendix A: F ourier Insights into the Performance Limitations of Level-1 QAOA In sect...

    1979

  103. [111]

    As shown in fig

    Error bars represent the standard deviation across the random instances. As shown in fig. 7, the maximum frequency attainable by QAOA 1 is significantly lower than that of HP , primarily due to the locality constraints inherent in QAOA. In a p-level implementation, each qubit ...

  104. [112]

    Ising Models without Fields Proof of Theorem 5. Using the definitions of the coefficients A(γ) and B(γ), the expectation value for an arbitrary Ising model without external fields can be rewritten as: ⟨γ, β|HP |γ, β⟩ = A(γ) sin 4β − B(γ) sin2 2β (E1) = A(γ) sin 4β − B(γ) 1 − c...

  105. [113]

    Ising Models with Fields Proof of Theorem 6. Using the definitions of the coefficients A(γ), B(γ), and C(γ), the expectation value for an arbitrary 2-local Ising model with external fields can be rewritten as: ⟨γ, β|HP |γ, β⟩ = sin(2β)A(γ) + sin(4β)B(γ) + sin2(2β)C(γ). (E8) To...

  106. [114]

    Mathematical Preliminaries a. Probability Density Functions In this subsection, we introduce the necessary definitions and notations related to probability density functions (PDFs) that are essential for our proof. We begin by defining the expectation operator for functions of...

  107. [115]

    Let x be a random variable distributed according to p(x), and let D be a large parameter

    Some Useful Lemmas Lemma 13. Let x be a random variable distributed according to p(x), and let D be a large parameter. Then the expectation of x sin ax√ D can be approximated by: Ex∼p x sin ax√ D = a√ D E h2 − a3 6D3/2 E h4 + O D− 5 2 , = a√ D E h2 + O D− 3 2 . (H13) Proof. E ...

  108. [116]

    (H30) where the Taylor expansion: ex = 1 + x + x2 2 + O(x3) is applied in the last step

    For the first result, we compute: 1 + a D + b D2 + O 1 D3 D = eD ln(1+ a D + b D2 +O( 1 D3 )) (H27) = e a+ b− a2 2 1 D +O( 1 D2 ) (H28) = ea · e b− a2 2 1 D +O( 1 D2 ) (H29) = ea 1 + b − a2 2 1 D + O 1 D2 . (H30) where the Taylor expansion: ex = 1 + x + x2 2 + O(x3) is applied...

  109. [117]

    (H33) Lemma 15

    For the second result: 1 + a D + b D2 + O 1 D3 D+1 = ea 1 + b − a2 2 1 D + O 1 D2 1 + a D + O 1 D2 (H31) = ea 1 + b − a2 2 1 D + a D + O 1 D2 (H32) = ea 1 + a + b − a2 2 D + O 1 D2 ! . (H33) Lemma 15. Let x be a random variable distributed according to p(x), and let D be a lar...

  110. [118]

    The expectation of cos ax√ D is given by: E x∼p cos ax√ D = 1 − 1 2 a2 D E x∼p x2 + 1 4! a4 D2 E x∼p x4 + O 1 D3 . (H34)

  111. [119]

    For the D-th power of expectation: E x∼p cos ax√ D D = e − 1 2 a2 E x∼p[x2] " 1 + 1 8 a4 1 3 E x∼p x4 − E x∼p x2 2! 1 D + O 1 D2 # = e − 1 2 a2 E x∼p[x2] 1 + O 1 D . (H35)

  112. [120]

    1 3 E x∼p x4 − E x∼p x2 2# . (H46) Using eq. (H20) of lemma 14, we find: E x∼p cos ax√ D D = e − 1 2 a2 E x∼p[x2]

    Using the eq. (H34), we expand its D-th power: E x∼p cos ax√ D D = 1 − 1 2 a2 D E x∼p x2 + 1 4! a4 D2 E x∼p x4 + O 1 D3 D (H41) Let: s = − 1 2 a2 E x∼p x2 , (H42) t = 1 4! a4 E x∼p x4 . (H43) Then: t − s2 2 = 1 4! a4 E x∼p x4 − 1 2 − 1 2 a2 E x∼p x2 2 (H44) = 1 4! a4 E x∼p x4 ...

  113. [121]

    1 3 E x∼p x4 − E x∼p x2 2# . (H49) Using the eq. (H21) of lemma 14, we get: E x∼p cos ax√ D D+1 = e − 1 2 a2 E x∼p[x2]

    Similarly, for the ( D + 1)-th power: E x∼p cos ax√ D D+1 = 1 − 1 2 a2 D E x∼p x2 + 1 4! a4 D2 E x∼p x4 + O 1 D3 D+1 . (H48) Using the definitions of s and t from eq. (H42) and eq. (H43), we compute: s + t − s2 2 = − 1 2 a2 E x∼p x2 + 1 8 a4 " 1 3 E x∼p x4 − E x∼p x2 2# . (H49...

  114. [122]

    These adjustments facilitate a more streamlined presentation of the proof

    Proof of Theorem 7 Before proceeding with the proof of theorem 7, we redefine some notations introduced earlier in the manuscript for improved clarity and compactness. These adjustments facilitate a more streamlined presentation of the proof. Specifically, for an edge {u, v} ∈...

  115. [123]

    Computation of 1 • Case 1: a = 0 (i.e., |Nu\ \v| = 0) 1 = E J∼f cos 2J α√ D 0 = 1. (H122) • Case 2: a >0 (i.e., |Nu\ \v| ̸= 0) Using lemma 18 with substitutions x → J, p → f , a → 2α, and c → 2a, we obtain: 1 =    e −4aα2 E J∼f[J 2] 1 + O D−1 if λ = 1, 1 − 4aα2 E J∼f J 2 ...

  116. [124]

    Computation of 2 and 4 2,4 = E h,h′∼g cos 2(h ± h′) α√ D (H125) = 1 − 4α2 D E h∼g h2 ± ( E h∼g [h])2 + O 1 D2 (H126) = 1 + O 1 D (H127) where the second line was obtained using lemma 16

  117. [125]

    Computation of 3 and 5 • Case 1: b = 0 (|Nuv| = 0) 3,5 = E J,J′∼f cos 2(J ± J ′) α√ D 0 = 1. (H128) • Case 2: b >0 (|Nuv| > 0) Using lemma 19, and setting x → J, p → f , a → 2α, c → b, and λ → µ, we get: 3,5 = E J,J′∼f cos 2(J ± J ′) α√ D bDµ (H129) =    e −4α2b E J...

  118. [126]

    1 − 4α2b E J∼f J 2 + E J∼f [J] 2! Dµ−1 + O D2µ−2 # (H142) − 1 + O D−1

    Computation of 6 = 2 3 − 4 5 45 • Case 1: b = 0 (i.e., |Nuv| = 0) 6 = 1 − 4α2 D E h∼g h2 + ( E h∼g [h])2 + O 1 D2 · 1 (H132) − 1 − 4α2 D E h∼g h2 − ( E h∼g [h])2 + O 1 D2 · 1 = − 8α2 D E h∼g [h] 2 + O 1 D2 . (H133) • Case 2: b >0 (i.e., |Nuv| > 0) 6 = E h,h′∼g cos 2(h + h′) α√...

Pith tools

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