pith. sign in

arxiv: 2406.14330 · v2 · submitted 2024-06-20 · 🪐 quant-ph · cs.DS· math.OC

Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

Jai Moondra , Philip C. Lotshaw , Greg Mohler , Swati Gupta This is my paper

Pith reviewed 2026-05-24 00:22 UTC · model grok-4.3

classification 🪐 quant-ph cs.DSmath.OC
keywords QAOAMax-Cutgraph sparsificationdecompositiontrapped ionsnoise reductionquantum compilationapproximation ratio
0
0 comments X

The pith

Graph sparsification reduces QAOA compilation to O(n log(n/ε)) H_Ising pulses and O(n log(n/ε)/ε²) Pauli-X flips for Max-Cut on trapped ions with (1-ε) approximation loss.

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

The paper develops new approximate compilation schemes for QAOA solving Max-Cut based on graph sparsification and decomposition. These yield the first provable guarantees that the techniques improve quantum noise resilience and reduce circuit complexity. For trapped-ion simulators, a (1-ε) loss in approximation allows cutting H_Ising pulses to O(n log(n/ε)) and Pauli-X flips to O(n log(n/ε)/ε²) from O(n²). The reductions produce significant noise decreases according to theory and numerical calculations.

Core claim

The authors show that graph sparsification, which maintains the cut value up to a (1-ε) multiplicative factor, can be combined with QAOA to yield compilation schemes with substantially fewer operations: O(n log(n/ε)) H_Ising pulses and O(n log(n/ε)/ε²) Pauli-X bit flips for n-node graphs, compared to the previous O(n²) scaling. This holds for trapped-ion compilations using all-to-all Ising evolution and Pauli-X flips, and the reductions translate to decreased noise as verified theoretically and numerically.

What carries the argument

Graph sparsification that preserves the cut value up to a (1-ε) factor, paired with decomposition of weighted graphs into unweighted ones, which together reduce the number of required quantum operations in QAOA compilations.

If this is right

  • For edge-by-edge QAOA compilations, sparsification directly lowers circuit complexity.
  • Noise reductions are achieved in trapped-ion hardware through fewer pulses and flips.
  • The methods provide performance guarantees previously unavailable for these heuristic techniques.
  • Results extend to some standard gate-based compilations beyond trapped ions.

Where Pith is reading between the lines

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

  • Larger problem instances may become solvable on near-term devices due to lower resource demands.
  • The approach might generalize to other quantum optimization algorithms using similar graph problems.
  • Hardware-specific noise models could be integrated more deeply to predict exact fidelity gains.

Load-bearing premise

That standard graph sparsification preserving cut value up to (1-ε) can be directly composed with QAOA's variational structure and the trapped-ion noise model so that fewer operations produce corresponding noise reduction.

What would settle it

A direct comparison on trapped-ion hardware of noise levels or success probabilities for QAOA on a dense graph versus its sparsified version, checking if the operation savings lead to the expected improvement.

Figures

Figures reproduced from arXiv: 2406.14330 by Greg Mohler, Jai Moondra, Philip C. Lotshaw, Swati Gupta.

Figure 2
Figure 2. Figure 2: The graph de￾composition process: The weighted graph G on the left can be written as the weighted sum G1 + 2G2 of two unweighted graphs G1, G2 on the right. QAOA begins with a classical problem defined in terms of a cost function C(z) with a bitstring argument z = (z1, . . . zN ). This is mapped to a quantum cost Hamiltonian C with an eigenspectrum that contains the set of classical solutions C|z⟩ = C(z)|z… view at source ↗
Figure 3
Figure 3. Figure 3: Reduction in N(HIsing) (total number of HIsing pulses) vs Max-Cut approximation for various runs of our experiment on weighted graphs in MQLib, colored by parameter q. Each data point is a single run. Points on the lower right have high reductions and high Max-Cut approximation [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Reduction in the total length or time of pulses vs Max-Cut approximation for various runs of our experiment on weighted graphs in MQLib. Each data point is a single run [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Landscapes of the QAOA cost function. Left column shows the noiseless case [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Expected cost ⟨C⟩ in QAOA for original, decomposed, and decomposed and sparsified and sparsified compilations, relative to the "ideal" case without noise and with the original compilation. (a) noiseless case, (b) noisy case with Γ = 0.001, and (c) with Γ = 0.002. The black curve exp(−Γt/2) is an upper bound in the triangle-free case as described in the text. Each instance is compiled into three distinct sp… view at source ↗
Figure 9
Figure 9. Figure 9: Expected improvement in cost from modified compilations relative to the original compi [PITH_FULL_IMAGE:figures/full_fig_p017_9.png] view at source ↗
read the original abstract

We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli-$X$ operations and all-to-all Ising Hamiltonian $H_\text{Ising}$ evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all $H_\text{Ising}$ pulses, we show that for a $(1-\epsilon)$ factor loss in the Max-Cut approximation ($\epsilon>0)$, our compilations improve the (worst-case) number of $H_\text{Ising}$ pulses from $O(n^2)$ to $O(n\log(n/\epsilon))$ and the (worst-case) number of Pauli-$X$ bit flips from $O(n^2)$ to $O\left(\frac{n\log(n/\epsilon)}{\epsilon^2}\right)$ for $n$-node graphs. We demonstrate significant reductions in noise are obtained in our new compilation approaches using theory and numerical calculations for trapped-ion hardware. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.

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 paper develops approximate compilation schemes for QAOA on Max-Cut using graph sparsification (to reduce edges while preserving cut value up to (1-ε)) and decomposition (to break weighted graphs into unweighted ones). For trapped-ion hardware with all-to-all H_Ising pulses (Mølmer-Sørensen or ODF) and Pauli-X flips, it claims the first provable bounds: worst-case H_Ising pulses reduced from O(n²) to O(n log(n/ε)) and X flips from O(n²) to O(n log(n/ε)/ε²) while incurring only (1-ε) loss in the Max-Cut approximation factor. Noise reduction is asserted via both the derived operation counts and numerical calculations under a trapped-ion noise model.

Significance. If the composition of standard cut-sparsifier guarantees with the QAOA variational loop and the specific trapped-ion noise model (decoherence, crosstalk) is valid, the work supplies the first rigorous performance guarantees for sparsification-based compilation in QAOA. This would be a useful tool for reducing circuit complexity on near-term hardware, especially since the bounds are expressed in terms of n and ε rather than fitted parameters.

major comments (2)
  1. [Abstract (and the section deriving the O(n log(n/ε)) bounds)] The central translation step (sparsification guarantees → reduced pulse counts → noise reduction) is load-bearing for the main claim in the abstract. Standard cut sparsifiers preserve the cut value up to (1-ε), but the manuscript must explicitly bound any additional error introduced when QAOA parameters (γ, β) are re-optimized on the sparsified instance rather than the original graph; without this, the (1-ε) factor does not automatically carry over to the QAOA expectation value.
  2. [Numerical calculations section (and the paragraph stating 'significant reductions in noise are obtained... using theory'] The trapped-ion noise model (decoherence and crosstalk) is assumed to scale directly with the number of H_Ising pulses and X flips. The manuscript should provide the explicit functional dependence (e.g., error ∝ pulse count, or error ∝ total duration) used in both the theoretical noise bound and the numerical calculations; if the model includes amplitude- or duration-dependent terms that are not reduced by sparsification, the claimed noise improvement does not follow.
minor comments (2)
  1. Notation for the all-to-all H_Ising evolution should be defined once (e.g., whether it is a single global pulse or a sum over pairs) to avoid ambiguity when counting pulses after sparsification.
  2. [Abstract] The abstract states results apply to 'some' standard gate-based compilations; a brief remark on the scope (which gate sets or connectivity assumptions) would clarify the reach of the O(n log(n/ε)) claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. Below we respond point-by-point to the major comments. We will incorporate clarifications and explicit statements in the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract (and the section deriving the O(n log(n/ε)) bounds)] The central translation step (sparsification guarantees → reduced pulse counts → noise reduction) is load-bearing for the main claim in the abstract. Standard cut sparsifiers preserve the cut value up to (1-ε), but the manuscript must explicitly bound any additional error introduced when QAOA parameters (γ, β) are re-optimized on the sparsified instance rather than the original graph; without this, the (1-ε) factor does not automatically carry over to the QAOA expectation value.

    Authors: We appreciate the referee highlighting the need for rigor here. A cut sparsifier by definition multiplicatively approximates every cut value (i.e., the Ising energy for every computational-basis state) within (1±ε). Because the expectation value of any quantum state is a convex combination of these basis-state energies, <ψ|H_Ising|ψ> is likewise preserved within (1±ε) for every |ψ>, including all states generated by the QAOA ansatz. Consequently the entire variational energy landscape is preserved up to the same factor, and re-optimizing (γ, β) on the sparsified instance introduces no additional error beyond the (1-ε) already guaranteed by the sparsifier. The claimed (1-ε) loss in Max-Cut approximation therefore carries directly to the QAOA expectation value. We will add an explicit paragraph stating this reasoning in the revised manuscript. revision: partial

  2. Referee: [Numerical calculations section (and the paragraph stating 'significant reductions in noise are obtained... using theory'] The trapped-ion noise model (decoherence and crosstalk) is assumed to scale directly with the number of H_Ising pulses and X flips. The manuscript should provide the explicit functional dependence (e.g., error ∝ pulse count, or error ∝ total duration) used in both the theoretical noise bound and the numerical calculations; if the model includes amplitude- or duration-dependent terms that are not reduced by sparsification, the claimed noise improvement does not follow.

    Authors: We agree that the scaling assumptions should be stated explicitly. In the revised manuscript we will add a clear statement of the noise model: the dominant contributions (decoherence accumulated during each pulse and crosstalk) are taken to scale linearly with the number of H_Ising pulses and X flips, consistent with standard trapped-ion models in the relevant regime. We will also confirm that the numerical simulations employ exactly this linear scaling and that no significant amplitude- or duration-dependent error terms outside this scaling appear in the model. revision: yes

Circularity Check

0 steps flagged

No significant circularity; external sparsification theorems applied to QAOA compilation bounds

full rationale

The derivation applies known graph sparsification results (preserving cut values to (1-ε)) and decomposition to obtain the stated O(n log(n/ε)) H_Ising pulse and O(n log(n/ε)/ε²) X-flip bounds for trapped-ion all-to-all implementations. These follow from the external edge-count guarantees of sparsifiers composed with the hardware model, without any quantity being defined in terms of the target noise reduction or fitted inside the paper. The abstract and claims explicitly position the work as the first provable guarantees on these techniques for quantum noise resilience, relying on literature theorems rather than self-citations or internal redefinitions. Noise reduction is asserted separately via theory and numerical calculations rather than by construction from the operation counts. The chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only view; the central bounds rest on the standard assumption that graph sparsification preserves cut value to (1-ε) and that fewer pulses map monotonically to lower noise under the trapped-ion model. No free parameters or invented entities are named.

axioms (1)
  • domain assumption Graph sparsification preserves the cut value up to multiplicative (1-ε) factor
    Invoked to obtain the stated approximation loss while reducing operation counts.

pith-pipeline@v0.9.0 · 5904 in / 1313 out tokens · 23632 ms · 2026-05-24T00:22:11.782656+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute

    quant-ph 2025-08 unverdicted novelty 2.0

    A synthesis of expert insights from the ADAC Quantum Computing Working Group and member survey on the complementary roles of quantum and classical high-performance computing in future hybrid infrastructures.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga. Quantum In- terior Point Methods for Semidefinite Optimization.Quantum, 7:1110, September 2023. Pub- lisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften

    work page 2023

  2. [2]

    Twice-RamanujanSparsifiers

    JoshuaBatson, DanielA.Spielman, andNikhilSrivastava. Twice-RamanujanSparsifiers. SIAM Review, 56(2):315–334, January 2014. Publisher: Society for Industrial and Applied Mathe- matics

    work page 2014

  3. [3]

    Quantum spin dynamics and entanglement generation with hundreds of trapped ions.Science, 352(6291):1297–1301, 2016

    Justin G Bohnet, Brian C Sawyer, Joseph W Britton, Michael L Wall, Ana Maria Rey, Michael Foss-Feig, and John J Bollinger. Quantum spin dynamics and entanglement generation with hundreds of trapped ions.Science, 352(6291):1297–1301, 2016

    work page 2016

  4. [4]

    Clark, Holly N

    Craig R. Clark, Holly N. Tinkey, Brian C. Sawyer, Adam M. Meier, Karl A. Burkhardt, Christopher M. Seck, Christopher M. Shappert, Nicholas D. Guise, Curtis E. Volin, Spencer D. Fallek, Harley T. Hayden, Wade G. Rellergert, and Kenton R. Brown. High-Fidelity Bell- State Preparation with $^{40}{\mathrm{Ca}}^{+}$ Optical Qubits.Physical Review Letters, 127(1...

    work page 2021

  5. [5]

    MIT press, 2022

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.Introduction to algorithms. MIT press, 2022

    work page 2022

  6. [6]

    What Works Best When? A Systematic Eval- uationofHeuristicsforMax-CutandQUBO

    Iain Dunning, Swati Gupta, and John Silberholz. What Works Best When? A Systematic Eval- uationofHeuristicsforMax-CutandQUBO. INFORMS Journal on Computing, 30(3):608–624, August 2018

    work page 2018

  7. [7]

    Quantum optimiza- tion of maximum independent set using rydberg atom arrays.Science, 376(6598):1209–1215, 2022

    Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Blu- vstein, Giulia Semeghini, Ahmed Omran, J-G Liu, Rhine Samajdar, et al. Quantum optimiza- tion of maximum independent set using rydberg atom arrays.Science, 376(6598):1209–1215, 2022

    work page 2022

  8. [8]

    Warm-starting quantum optimization

    Daniel J Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, 2021

    work page 2021

  9. [9]

    The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, April 2020

    Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, April 2020. arXiv:2004.09002 [quant-ph]

    work page arXiv 2020

  10. [10]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm, November 2014. arXiv:1411.4028 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  11. [11]

    The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size.Quantum, 6:759, July 2022

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size.Quantum, 6:759, July 2022. Publisher: Verein zur Förderung des Open Access Publizierens in den Quan- tenwissenschaften

    work page 2022

  12. [12]

    Nonequilibrium dynamicsofarbitrary-rangeisingmodelswithdecoherence: Anexactanalyticsolution

    Michael Foss-Feig, Kaden RA Hazzard, John J Bollinger, and Ana Maria Rey. Nonequilibrium dynamicsofarbitrary-rangeisingmodelswithdecoherence: Anexactanalyticsolution. Physical Review A, 87(4):042101, 2013

    work page 2013

  13. [13]

    Animprovedapproximationratiofortheminimumlatency problem

    MichelGoemansandJonKleinberg. Animprovedapproximationratiofortheminimumlatency problem. Mathematical Programming, 82(1):111–124, June 1998

    work page 1998

  14. [14]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. InProceedings of the twenty-eighth annual ACM symposium on Theory of Computing, STOC ’96, pages 212–219, New York, NY, USA, July 1996. Association for Computing Machinery

    work page 1996

  15. [15]

    Formulating and Solving Routing Problems on Quantum Computers.IEEE Transactions on Quantum Engineering, 2:1–17, 2021

    Stuart Harwood, Claudio Gambella, Dimitar Trenev, Andrea Simonetto, David Bernal, and Donny Greenberg. Formulating and Solving Routing Problems on Quantum Computers.IEEE Transactions on Quantum Engineering, 2:1–17, 2021. Conference Name: IEEE Transactions on Quantum Engineering

    work page 2021

  16. [16]

    David R. Karger. Random sampling in cut, flow, and network design problems. InProceedings of the twenty-sixth annual ACM symposium on Theory of Computing, STOC ’94, pages 648– 657, New York, NY, USA, May 1994. Association for Computing Machinery

    work page 1994

  17. [17]

    A Quantum Interior Point Method for LPs and SDPs

    Iordanis Kerenidis and Anupam Prakash. A Quantum Interior Point Method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1):5:1–5:32, October 2020

    work page 2020

  18. [18]

    17 Norris, Christian Kraglund Andersen, Markus Müller, Alexandre Blais, Christopher Eichler, and Andreas Wallraff

    Sebastian Krinner, Nathan Lacroix, Ants Remm, Agustin Di Paolo, Elie Genois, Catherine Leroux, Christoph Hellings, Stefania Lazar, Francois Swiadek, Johannes Herrmann, Graham J. 17 Norris, Christian Kraglund Andersen, Markus Müller, Alexandre Blais, Christopher Eichler, and Andreas Wallraff. Realizing repeated quantum error correction in a distance-three ...

    work page 2022

  19. [19]

    Quantum Approximate Optimization Algo- rithm with Sparsified Phase Operator

    Xiaoyuan Liu, Ruslan Shaydulin, and Ilya Safro. Quantum Approximate Optimization Algo- rithm with Sparsified Phase Operator. In2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 133–141, September 2022. arXiv:2205.00118 [quant- ph]

    work page arXiv 2022

  20. [20]

    Lotshaw, Kevin D

    Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble, and Cre- ston D. Herold. Modeling noise in global M\o{}lmer-S\o{}rensen interactions applied to quan- tum approximate optimization.Physical Review A, 107(6):062406, June 2023

    work page 2023

  21. [21]

    Scaling quantum approximate opti- mization on near-term hardware.Scientific Reports, 12(1):12388, 2022

    Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S Humble. Scaling quantum approximate opti- mization on near-term hardware.Scientific Reports, 12(1):12388, 2022

    work page 2022

  22. [22]

    Ising formulations of many np problems.Frontiers in physics, 2:74887, 2014

    Andrew Lucas. Ising formulations of many np problems.Frontiers in physics, 2:74887, 2014

    work page 2014

  23. [23]

    Performant near-term quantum combinatorial opti- mization

    Titus D Morris and Phillip C Lotshaw. Performant near-term quantum combinatorial opti- mization. arXiv:2404.16135, 2024

    work page arXiv 2024

  24. [24]

    Fast Quantum Subroutines for the Simplex Method.Operations Research, 72(2):763–780, March 2024

    Giacomo Nannicini. Fast Quantum Subroutines for the Simplex Method.Operations Research, 72(2):763–780, March 2024

    work page 2024

  25. [25]

    Quantum computation and quantum information, volume 2

    Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001

    work page 2001

  26. [26]

    Expectation values from the single- layer quantum approximate optimization algorithm on ising problems.Quantum Science and Technology, 7(4):045036, 2022

    Asier Ozaeta, Wim van Dam, and Peter L McMahon. Expectation values from the single- layer quantum approximate optimization algorithm on ising problems.Quantum Science and Technology, 7(4):045036, 2022

    work page 2022

  27. [27]

    Pagano, A

    G. Pagano, A. Bapat, P. Becker, K. Collins, A. De, P. Hess, H. Kaplan, A. Kyprianidis, W. Tan, C. Baldwin, L. Brady, A. Deshpande, F. Liu, S. Jordan, A. Gorshkov, and C. Monroe. Quantum Approximate Optimization with a Trapped-Ion Quantum Simulator. 2019

    work page 2019

  28. [28]

    Love, Alán Aspuru-Guzik, and Jeremy L

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-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 Communications, 5(1):4213, July 2014

    work page 2014

  29. [29]

    The quantum-jump approach to dissipative dynamics in quantum optics.Reviews of Modern Physics, 70(1):101, 1998

    Martin B Plenio and Peter L Knight. The quantum-jump approach to dissipative dynamics in quantum optics.Reviews of Modern Physics, 70(1):101, 1998

    work page 1998

  30. [30]

    Quantum Computing in the NISQ era and beyond

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

    work page 2018

  31. [31]

    Joel Rajakumar, Jai Moondra, Bryan Gard, Swati Gupta, and Creston D. Herold. Generat- ing target graph couplings for the quantum approximate optimization algorithm from native quantum hardware couplings.Physical Review A, 106(2):022606, August 2022

    work page 2022

  32. [32]

    Ryan-Anderson, J.G

    C. Ryan-Anderson, J.G. Bohnet, K. Lee, D. Gresh, A. Hankin, J.P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N.C. Brown, T.M. Gatterman, S.K. Halit, K. Gilmore, J.A. Gerber, B. Neyenhuis, D. Hayes, and R.P. Stutz. Realization of Real-Time Fault-Tolerant 18 Quantum Error Correction. Physical Review X, 11(4):041058, December 2021. Publisher: America...

    work page 2021

  33. [33]

    Parameter transfer for quantum approximate optimization of weighted maxcut

    Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S Hum- ble. Parameter transfer for quantum approximate optimization of weighted maxcut. ACM Transactions on Quantum Computing, 4(3):1–15, 2023

    work page 2023

  34. [34]

    Multistart Methods for Quantum Approxi- mate optimization

    Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. Multistart Methods for Quantum Approxi- mate optimization. In2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8, September 2019. ISSN: 2643-1971

    work page 2019

  35. [35]

    Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52(4):R2493–R2496, October 1995. Publisher: American Physical Society

    work page 1995

  36. [36]

    V. V. Sivak, A. Eickbusch, B. Royer, S. Singh, I. Tsioutsios, S. Ganjam, A. Miano, B. L. Brock, A. Z. Ding, L. Frunzio, S. M. Girvin, R. J. Schoelkopf, and M. H. Devoret. Real-time quantum error correction beyond break-even.Nature, 616(7955):50–55, April 2023

    work page 2023

  37. [37]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resistances.SIAM Journal on Computing, 40(6):1913–1926, January 2011

    work page 1913

  38. [38]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. InProceedings of the thirty-sixth annual ACM symposium on Theory of computing, STOC ’04, pages 81–90, New York, NY, USA, June 2004. Association for Computing Machinery

    work page 2004

  39. [39]

    Quantum speedups for convex dynamic programming, March 2021

    David Sutter, Giacomo Nannicini, Tobias Sutter, and Stefan Woerner. Quantum speedups for convex dynamic programming, March 2021. arXiv:2011.11654 [quant-ph]

    work page arXiv 2021

  40. [40]

    Lokhov, Sidhant Misra, and Carleton Coffrin

    Byron Tasseff, Tameem Albash, Zachary Morrell, Marc Vuffray, Andrey Y. Lokhov, Sidhant Misra, and Carleton Coffrin. On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization, October 2022. arXiv:2210.04291 [quant-ph]

    work page arXiv 2022

  41. [41]

    Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths.Quantum, 7:1121, September 2023

    Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta. Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths.Quantum, 7:1121, September 2023

    work page 2023

  42. [42]

    Decoherence due to elastic rayleigh scattering.Physical review letters, 105(20):200401, 2010

    HermannUys, MichaelJBiercuk, AaronPVanDevender, ChristianOspelkaus, DominicMeiser, Roee Ozeri, and John J Bollinger. Decoherence due to elastic rayleigh scattering.Physical review letters, 105(20):200401, 2010

    work page 2010

  43. [43]

    Prentice Hall, 2001

    Doug West.Introduction to Graph Theory, volume 2. Prentice Hall, 2001

    work page 2001

  44. [44]

    Williamson and David B

    David P. Williamson and David B. Shmoys.The Design of Approximation Algorithms. Cam- bridge University Press, 2010. A Omitted proofs from Section 3 We analyze our algorithms for fasterunion-of-starsfrom Section 3 and prove their theoretical guarantees. 19 A.1 Analysis of Algorithm binar y-decompose Proof of Theorem 3.Denote G = ( V, E, c). Let c∗, η, k be...

    work page 2010