quantum-computing

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

Jai Moondra, Phillip C. Lotshaw, Greg Mohler, and Swati Gupta

28 min read

0 likes

⚡ Quantum Brief

We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. For trapped-ion quantum simulators implementing all-to-all $H_{Ising}$ pulses, we show that for a $(1-\epsilon)$ factor loss in the Max-Cut approximation ($\epsilon \gt 0)$, our compilations improve the (worst-case) number of $H_{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. The list may be incomplete as not all publishers provide suitable and complete citation data.

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractWe 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_{Ising}$ pulses, we show that for a $(1-\epsilon)$ factor loss in the Max-Cut approximation ($\epsilon \gt 0)$, our compilations improve the (worst-case) number of $H_{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. This is an asymptotic improvement for any constant $\epsilon \gt 0$. We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.Popular summaryQuantum devices hold promise for solving classically hard optimization problems with the advent of algorithms like the Quantum Approximate Optimization Algorithm (QAOA), but current quantum devices are noisy: longer quantum circuits accumulate higher noise and lead to higher error. We show that classically simplifying the problem before it reaches the quantum device can substantially reduce this noise. We focus on QAOA for the Max-Cut problem, a standard benchmark that seeks to partition a network's vertices into two parts to maximize the sum of edges connecting one part to the other. We use two classical pre-processing techniques: (1) sparsification, which removes connections while approximately preserving the solution, and (2) decomposition, which breaks a weighted network into a small number of unweighted pieces. We show that these techniques yield dramatically shorter quantum circuits on trapped-ion hardware as compared to the state-of-the-art, with only a small, controllable loss in solution quality. We provide both theoretical guarantees (the first such guarantees, to our knowledge) and empirical evidence for QAOA circuits based on trapped-ion hardware. We also show that our algorithms lead to smaller overall noise under a simple quantum noise model. Our results suggest that classical pre-processing can drastically reduce the impact of noise on current quantum hardware.► BibTeX data@article{Moondra2026promiseofgraph, doi = {10.22331/q-2026-08-07-2185}, url = {https://doi.org/10.22331/q-2026-08-07-2185}, title = {Promise of {G}raph {S}parsification and {D}ecomposition for {N}oise {R}eduction in {QAOA}: {A}nalysis for {T}rapped-{I}on {C}ompilations}, author = {Moondra, Jai and Lotshaw, Phillip C. and Mohler, Greg and Gupta, Swati}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2185}, month = aug, year = {2026} }► References [1] B. Augustino, M. Cain, E. Farhi, S. Gupta, S. Gutmann, D. Ranard, E. Tang, and K. Van Kirk. Strategies for running the QAOA at hundreds of qubits. arXiv:2410.03015, 2024. DOI: https://doi.org/10.48550/arXiv.2410.03015. https://doi.org/10.48550/arXiv.2410.03015 arXiv:2410.03015 [2] B. Augustino, G. Nannicini, T. Terlaky, and L. Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023. DOI: https://doi.org/10.22331/q-2023-09-11-1110. https://doi.org/10.22331/q-2023-09-11-1110 [3] 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 Cryptography (TQC), 2022. DOI: https://doi.org/10.4230/LIPIcs.TQC.2022.7. https://doi.org/10.4230/LIPIcs.TQC.2022.7 [4] J. Batson, D. Spielman, and N. Srivastava. Twice-Ramanujan sparsifiers. SIAM Review, 56(2):315–334, 2014. DOI: https://doi.org/10.1137/090772873. https://doi.org/10.1137/090772873 [5] L. Binkowski, G. Koßmann, T. Ziegler, and R. Schwonnek. Elementary proof of QAOA convergence. New Journal of Physics, 26(7):073001, 2024. DOI: https://doi.org/10.1088/1367-2630/ad59bb. https://doi.org/10.1088/1367-2630/ad59bb [6] R. Blümel, N. Grzesiak, N. Pisenti, K. Wright, and Y. Nam. Power-optimal, stabilized entangling gate between trapped-ion qubits. npj Quantum Information, 7(1):147, 2021. DOI: https://doi.org/10.1038/s41534-021-00489-w. https://doi.org/10.1038/s41534-021-00489-w [7] D. Bluvstein, S. Evered, A. Geim, S. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al. Logical quantum processor based on reconfigurable atom arrays. Nature, 626(7997):58–65, 2024. DOI: https://doi.org/10.1038/s41586-023-06927-3. https://doi.org/10.1038/s41586-023-06927-3 [8] J. Bohnet, B. Sawyer, J. Britton, M. Wall, A. Rey, M. Foss-Feig, and J. Bollinger. Quantum spin dynamics and entanglement generation with hundreds of trapped ions. Science, 352(6291):1297–1301, 2016. DOI: https://doi.org/10.1126/science.aad9958. https://doi.org/10.1126/science.aad9958 [9] S. Bravyi, O. Dial, J. Gambetta, D. Gil, and Z. Nazario. The future of quantum computing with superconducting qubits. Journal of Applied Physics, 132(16), 2022. DOI: https://doi.org/10.1063/5.0082975. https://doi.org/10.1063/5.0082975 [10] M. Charikar, T. Leighton, S. Li, and A. Moitra. Vertex sparsifiers and abstract rounding algorithms. In 51st IEEE Symposium on Foundations of Computer Science (FOCS), pages 265–274, 2010. DOI: https://doi.org/10.1109/FOCS.2010.32. https://doi.org/10.1109/FOCS.2010.32 [11] C. Clark, H. Tinkey, B. Sawyer, A. Meier, K. Burkhardt, C. Seck, C. Shappert, N. Guise, C. Volin, S. Fallek, H. Hayden, W. Rellergert, and K. Brown. High-fidelity Bell-state preparation with $^{40}\mathrm{Ca}^{+}$ optical qubits.

Physical Review Letters, 127(13):130505, 2021. DOI: https://doi.org/10.1103/PhysRevLett.127.130505. https://doi.org/10.1103/PhysRevLett.127.130505 [12] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. 2022. [13] D. Liu, J. Li, X. Chen, and N. Jiang. Noisy quantum approximation optimization algorithm for solving MaxCut problem. Physica Scripta, 2025. DOI: https://doi.org/10.1088/1402-4896/ae009f. https://doi.org/10.1088/1402-4896/ae009f [14] I. Dunning, S. Gupta, and J. Silberholz. What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS Journal on Computing, 30(3):608–624, 2018. DOI: https://doi.org/10.1287/ijoc.2017.0798. https://doi.org/10.1287/ijoc.2017.0798 [15] S. Ebadi, A. Keesling, M. Cain, 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. Science, 376(6598):1209–1215, 2022. DOI: https://doi.org/10.1126/science.abo6587. https://doi.org/10.1126/science.abo6587 [16] D. Egger, J. Mareček, and S. Woerner. Warm-starting quantum optimization. Quantum, 5:479, 2021. DOI: https://doi.org/10.22331/q-2021-06-17-479. https://doi.org/10.22331/q-2021-06-17-479 [17] E. Farhi, D. Gamarnik, and S. Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv:2004.09002, 2020. DOI: https://doi.org/10.48550/arXiv.2004.09002. https://doi.org/10.48550/arXiv.2004.09002 arXiv:2004.09002 [18] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4028, 2014. DOI: https://doi.org/10.48550/arXiv.1411.4028. https://doi.org/10.48550/arXiv.1411.4028 arXiv:1411.4028 [19] 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. DOI: https://doi.org/10.22331/q-2022-07-07-759. https://doi.org/10.22331/q-2022-07-07-759 [20] M. Foss-Feig, K. Hazzard, J. Bollinger, and A. Rey. Nonequilibrium dynamics of arbitrary-range Ising models with decoherence: An exact analytic solution. Physical Review A, 87(4):042101, 2013. DOI: https://doi.org/10.1103/PhysRevA.87.042101. https://doi.org/10.1103/PhysRevA.87.042101 [21] M. Goemans and D. Williamson. .879-approximation algorithms for MAX CUT and MAX 2SAT. In 26th ACM Symposium on Theory of Computing (STOC), pages 422–431, 1994. DOI: https://doi.org/10.1145/195058.195216. https://doi.org/10.1145/195058.195216 [22] L. Grover. A fast quantum mechanical algorithm for database search. In 28th ACM Symposium on Theory of Computing (STOC), pages 212–219, 1996. DOI: https://doi.org/10.1145/237814.237866. https://doi.org/10.1145/237814.237866 [23] S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal, and D. Greenberg. Formulating and solving routing problems on quantum computers. IEEE Transactions on Quantum Engineering, 2:1–17, 2021. DOI: https://doi.org/10.1109/TQE.2021.3049230. https://doi.org/10.1109/TQE.2021.3049230 [24] J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001. DOI: https://doi.org/10.1145/502090.502098. https://doi.org/10.1145/502090.502098 [25] D. Karger. Random sampling in cut, flow, and network design problems. In 26th ACM Symposium on Theory of Computing (STOC), pages 648–657, 1994. DOI: https://doi.org/10.1287/moor.24.2.383. https://doi.org/10.1287/moor.24.2.383 [26] H. Karloff. How good is the Goemans–Williamson MAX CUT algorithm? SIAM Journal on Computing, 29(1):336–350, 1999. DOI: https://doi.org/10.1137/S0097539797321481. https://doi.org/10.1137/S0097539797321481 [27] I. Kerenidis and A. Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1):5:1–5:32, 2020. DOI: https://doi.org/10.1145/3406306. https://doi.org/10.1145/3406306 [28] S. Khot. On the power of unique 2-prover 1-round games. In 34th ACM Symposium on Theory of Computing (STOC), pages 767–775, 2002. DOI: https://doi.org/10.1109/CCC.2002.1004334. https://doi.org/10.1109/CCC.2002.1004334 [29] S. Krinner, N. Lacroix, A. Remm, A. Di Paolo, E. Genois, C. Leroux, C. Hellings, S. Lazar, F. Swiadek, J. Herrmann, G. Norris, C. Andersen, M. Müller, A. Blais, C. Eichler, and A. Wallraff. Realizing repeated quantum error correction in a distance-three surface code. Nature, 605(7911):669–674, 2022. DOI: https://doi.org/10.1038/s41586-022-04566-8. https://doi.org/10.1038/s41586-022-04566-8 [30] X. Liu, R. Shaydulin, and I. Safro. Quantum approximate optimization algorithm with sparsified phase operator. In IEEE International Conference on Quantum Computing and Engineering (QCE), pages 133–141, 2022. DOI: https://doi.org/10.1109/QCE53715.2022.00032. https://doi.org/10.1109/QCE53715.2022.00032 [31] P. Lotshaw, K. Battles, B. Gard, G. Buchs, T. Humble, and C. Herold. Modeling noise in global Mølmer-Sørensen interactions applied to quantum approximate optimization. Physical Review A, 107(6):062406, 2023. DOI: https://doi.org/10.1103/PhysRevA.107.062406. https://doi.org/10.1103/PhysRevA.107.062406 [32] P. Lotshaw, T. Humble, R. Herrman, J. Ostrowski, and G. Siopsis. Empirical performance bounds for quantum approximate optimization.

Quantum Information Processing, 20(12):403, 2021. DOI: https://doi.org/10.1007/s11128-021-03342-3. https://doi.org/10.1007/s11128-021-03342-3 [33] P. Lotshaw, T. Nguyen, A. Santana, A. McCaskey, R. Herrman, J. Ostrowski, G. Siopsis, and T. Humble. Scaling quantum approximate optimization on near-term hardware. Scientific Reports, 12(1):12388, 2022. DOI: https://doi.org/10.1038/s41598-022-14767-w. https://doi.org/10.1038/s41598-022-14767-w [34] P. Lotshaw, B. Sawyer, C. Herold, and G. Buchs. Exactly solvable model of light-scattering errors in quantum simulations with metastable trapped-ion qubits. Physical Review A, 110(3):L030803, 2024. DOI: https://doi.org/10.1103/PhysRevA.110.L030803. https://doi.org/10.1103/PhysRevA.110.L030803 [35] P. Lotshaw, G. Siopsis, J. Ostrowski, R. Herrman, R. Alam, S. Powers, and T. Humble. Approximate Boltzmann distributions in quantum approximate optimization. Physical Review A, 108(4):042411, 2023. DOI: https://doi.org/10.1103/PhysRevA.108.042411. https://doi.org/10.1103/PhysRevA.108.042411 [36] P. Lotshaw, H. Xu, B. Khalid, G. Buchs, T. Humble, and A. Banerjee. Simulations of frustrated Ising Hamiltonians using quantum approximate optimization. Philosophical Transactions of the Royal Society A, 381(2241):20210414, 2023. DOI: https://doi.org/10.1098/rsta.2021.0414. https://doi.org/10.1098/rsta.2021.0414 [37] A. Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2:74887, 2014. DOI: https://doi.org/10.3389/fphy.2014.00005. https://doi.org/10.3389/fphy.2014.00005 [38] A. Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 3–12, 2009. DOI: https://doi.org/10.1109/FOCS.2009.28. https://doi.org/10.1109/FOCS.2009.28 [39] C. Monroe, W. Campbell, L.-M. Duan, Z.-X. Gong, A. Gorshkov, P. Hess, R. Islam, K. Kim, N. Linke, G. Pagano, et al. Programmable quantum simulations of spin systems with trapped ions. Reviews of Modern Physics, 93(2):025001, 2021. DOI: https://doi.org/10.1103/RevModPhys.93.025001. https://doi.org/10.1103/RevModPhys.93.025001 [40] J. Moondra, P. Lotshaw, G. Mohler, and S. Gupta. Source code for ``Promise of graph sparsification and decomposition for noise reduction in QAOA: Analysis for trapped-ion compilations'', 2026. DOI: https://doi.org/10.5281/zenodo.20669870. https://doi.org/10.5281/zenodo.20669870 [41] T. Morris and P. Lotshaw. Performant near-term quantum combinatorial optimization. arXiv:2404.16135, 2024. DOI: https://doi.org/10.48550/arXiv.2404.16135. https://doi.org/10.48550/arXiv.2404.16135 arXiv:2404.16135 [42] G. Nannicini. Fast quantum subroutines for the simplex method. Operations Research, 72(2):763–780, 2024. DOI: https://doi.org/10.1287/opre.2022.2341. https://doi.org/10.1287/opre.2022.2341 [43] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. 2001. [44] A. Ozaeta, W. van Dam, and P. McMahon. Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems. Quantum Science and Technology, 7(4):045036, 2022. DOI: https://doi.org/10.1088/2058-9565/ac9013. https://doi.org/10.1088/2058-9565/ac9013 [45] 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. DOI: https://doi.org/10.48550/arXiv.1906.02700. https://doi.org/10.48550/arXiv.1906.02700 [46] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. Love, A. Aspuru-Guzik, and J. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(1):4213, 2014. DOI: https://doi.org/10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 [47] J. Pino, J. Dreiling, C. Figgatt, J. Gaebler, S. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, et al. Demonstration of the trapped-ion quantum CCD computer architecture. Nature, 592(7853):209–213, 2021. DOI: https://doi.org/10.1038/s41586-021-03318-4. https://doi.org/10.1038/s41586-021-03318-4 [48] M. Plenio and P. Knight. The quantum-jump approach to dissipative dynamics in quantum optics. Reviews of Modern Physics, 70(1):101, 1998. DOI: https://doi.org/10.1103/RevModPhys.70.101. https://doi.org/10.1103/RevModPhys.70.101 [49] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018. DOI: https://doi.org/10.22331/q-2018-08-06-79. https://doi.org/10.22331/q-2018-08-06-79 [50] J. Rajakumar, J. Moondra, B. Gard, S. Gupta, and C. Herold. Generating target graph couplings for the quantum approximate optimization algorithm from native quantum hardware couplings. Physical Review A, 106(2):022606, 2022. DOI: https://doi.org/10.1103/PhysRevA.106.022606. https://doi.org/10.1103/PhysRevA.106.022606 [51] C. Ryan-Anderson, J. Bohnet, K. Lee, D. Gresh, A. Hankin, J. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. Brown, T. Gatterman, S. Halit, K. Gilmore, J. Gerber, B. Neyenhuis, D. Hayes, and R. Stutz. Realization of real-time fault-tolerant quantum error correction. Physical Review X, 11(4):041058, 2021. DOI: https://doi.org/10.1103/PhysRevX.11.041058. https://doi.org/10.1103/PhysRevX.11.041058 [52] S. Sack. Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation.

Physical Review Research, 6(1), 2024. DOI: https://doi.org/10.1103/PhysRevResearch.6.013223. https://doi.org/10.1103/PhysRevResearch.6.013223 [53] R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, 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 intractable problem. Science Advances, 10(22):eadm6761, 2024. DOI: https://doi.org/10.1126/sciadv.adm6761. https://doi.org/10.1126/sciadv.adm6761 [54] R. Shaydulin, P. Lotshaw, J. Larson, J. Ostrowski, and T. Humble. Parameter transfer for quantum approximate optimization of weighted MaxCut. ACM Transactions on Quantum Computing, 4(3):1–15, 2023. DOI: https://doi.org/10.1145/3584706. https://doi.org/10.1145/3584706 [55] R. Shaydulin, I. Safro, and J. Larson. Multistart methods for quantum approximate optimization. In IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8, 2019. DOI: https://doi.org/10.1109/HPEC.2019.8916288. https://doi.org/10.1109/HPEC.2019.8916288 [56] P. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52(4):R2493–R2496, 1995. DOI: https://doi.org/10.1103/PhysRevA.52.R2493. https://doi.org/10.1103/PhysRevA.52.R2493 [57] V. Sivak, A. Eickbusch, B. Royer, S. Singh, I. Tsioutsios, S. Ganjam, A. Miano, B. Brock, A. Ding, L. Frunzio, S. Girvin, R. Schoelkopf, and M. Devoret. Real-time quantum error correction beyond break-even. Nature, 616(7955):50–55, 2023. DOI: https://doi.org/10.1038/s41586-023-05782-6. https://doi.org/10.1038/s41586-023-05782-6 [58] D. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011. DOI: https://doi.org/10.1137/080734029. https://doi.org/10.1137/080734029 [59] D. Sutter, G. Nannicini, T. Sutter, and S. Woerner. Quantum speedups for convex dynamic programming. arXiv:2011.11654, 2021. DOI: https://doi.org/10.48550/arXiv.2011.11654. https://doi.org/10.48550/arXiv.2011.11654 arXiv:2011.11654 [60] B. Tasseff, T. Albash, Z. Morrell, M. Vuffray, A. Lokhov, S. Misra, and C. Coffrin. On the emerging potential of quantum annealing hardware for combinatorial optimization. arXiv:2210.04291, 2022. DOI: https://doi.org/10.48550/arXiv.2210.04291. https://doi.org/10.48550/arXiv.2210.04291 arXiv:2210.04291 [61] R. Tate, J. Moondra, B. Gard, G. Mohler, and S. Gupta. Warm-started QAOA with custom mixers provably converges and computationally beats Goemans–Williamson's Max-Cut at low circuit depths. Quantum, 7:1121, 2023. DOI: https://doi.org/10.22331/q-2023-09-26-1121. https://doi.org/10.22331/q-2023-09-26-1121 [62] H. Uys, M. Biercuk, A. VanDevender, C. Ospelkaus, D. Meiser, R. Ozeri, and J. Bollinger. Decoherence due to elastic Rayleigh scattering.

Physical Review Letters, 105(20):200401, 2010. DOI: https://doi.org/10.1103/PhysRevLett.105.200401. https://doi.org/10.1103/PhysRevLett.105.200401 [63] C. Valahu, I. Apostolatos, S. Weidt, and W. Hensinger. Quantum control methods for robust entanglement of trapped ions. Journal of Physics B: Atomic, Molecular and Optical Physics, 55(20):204003, 2022. DOI: https://doi.org/10.1088/1361-6455/ac8eff. https://doi.org/10.1088/1361-6455/ac8eff [64] V. Vazirani. Approximation Algorithms. 2003. [65] M. Wang, B. Fang, A. Li, and P. Nair. Red-QAOA: Efficient variational optimization through circuit reduction. In 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 980–998, 2024. DOI: https://doi.org/10.1145/3620665.3640363. https://doi.org/10.1145/3620665.3640363 [66] D. West. Introduction to Graph Theory. 2001. [67] D. Williamson and D. Shmoys. The Design of Approximation Algorithms. 2010. [68] J. Wurtz and D. Lykov. Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs. Physical Review A, 104(5):052419, 2021. DOI: https://doi.org/10.1103/PhysRevA.104.052419. https://doi.org/10.1103/PhysRevA.104.052419 [69] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2):021067, 2020. DOI: https://doi.org/10.1103/PhysRevX.10.021067. https://doi.org/10.1103/PhysRevX.10.021067Cited by[1] Brayden Goldstein-Gelb and Phillip C. Lotshaw, "Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz", arXiv:2409.18829, (2024). [2] Maxime Dupont, Tina Oberoi, and Bhuvanesh Sundar, "Optimization via quantum preconditioning", Physical Review Applied 24 4, 044013 (2025). [3] Gilles Buchs, Thomas Beck, Ryan Bennink, Daniel Claudino, Andrea Delgado, Nur Aiman Fadel, Peter Groszkowski, Kathleen Hamilton, Travis Humble, Neeraj Kumar, Ang Li, Phillip Lotshaw, Olli Mukkula, Ryousei Takano, Amit Saxena, In-Saeng Suh, Miwako Tsuji, Roel Van Beeumen, Ugo Varetto, Yan Wang, Kazuya Yamazaki, and Mikael P. Johansson, "The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute", arXiv:2508.11765, (2025). [4] Saber Dinpazhouh and Illya V. Hicks, "Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips", arXiv:2509.00170, (2025). [5] Maxime Dupont, Bhuvanesh Sundar, and Meenambika Gowrishankar, "Self-consistent mean-field quantum approximate optimization", arXiv:2603.09838, (2026). The above citations are from SAO/NASA ADS (last updated successfully 2026-08-07 13:50:26). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-08-07 13:50:24: Could not fetch cited-by data for 10.22331/q-2026-08-07-2185 from Crossref. This is normal if the DOI was registered recently.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractWe 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_{Ising}$ pulses, we show that for a $(1-\epsilon)$ factor loss in the Max-Cut approximation ($\epsilon \gt 0)$, our compilations improve the (worst-case) number of $H_{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. This is an asymptotic improvement for any constant $\epsilon \gt 0$. We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.Popular summaryQuantum devices hold promise for solving classically hard optimization problems with the advent of algorithms like the Quantum Approximate Optimization Algorithm (QAOA), but current quantum devices are noisy: longer quantum circuits accumulate higher noise and lead to higher error. We show that classically simplifying the problem before it reaches the quantum device can substantially reduce this noise. We focus on QAOA for the Max-Cut problem, a standard benchmark that seeks to partition a network's vertices into two parts to maximize the sum of edges connecting one part to the other. We use two classical pre-processing techniques: (1) sparsification, which removes connections while approximately preserving the solution, and (2) decomposition, which breaks a weighted network into a small number of unweighted pieces. We show that these techniques yield dramatically shorter quantum circuits on trapped-ion hardware as compared to the state-of-the-art, with only a small, controllable loss in solution quality. We provide both theoretical guarantees (the first such guarantees, to our knowledge) and empirical evidence for QAOA circuits based on trapped-ion hardware. We also show that our algorithms lead to smaller overall noise under a simple quantum noise model. Our results suggest that classical pre-processing can drastically reduce the impact of noise on current quantum hardware.► BibTeX data@article{Moondra2026promiseofgraph, doi = {10.22331/q-2026-08-07-2185}, url = {https://doi.org/10.22331/q-2026-08-07-2185}, title = {Promise of {G}raph {S}parsification and {D}ecomposition for {N}oise {R}eduction in {QAOA}: {A}nalysis for {T}rapped-{I}on {C}ompilations}, author = {Moondra, Jai and Lotshaw, Phillip C. and Mohler, Greg and Gupta, Swati}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2185}, month = aug, year = {2026} }► References [1] B. Augustino, M. Cain, E. Farhi, S. Gupta, S. Gutmann, D. Ranard, E. Tang, and K. Van Kirk. Strategies for running the QAOA at hundreds of qubits. arXiv:2410.03015, 2024. DOI: https://doi.org/10.48550/arXiv.2410.03015. https://doi.org/10.48550/arXiv.2410.03015 arXiv:2410.03015 [2] B. Augustino, G. Nannicini, T. Terlaky, and L. Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023. DOI: https://doi.org/10.22331/q-2023-09-11-1110. https://doi.org/10.22331/q-2023-09-11-1110 [3] 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 Cryptography (TQC), 2022. DOI: https://doi.org/10.4230/LIPIcs.TQC.2022.7. https://doi.org/10.4230/LIPIcs.TQC.2022.7 [4] J. Batson, D. Spielman, and N. Srivastava. Twice-Ramanujan sparsifiers. SIAM Review, 56(2):315–334, 2014. DOI: https://doi.org/10.1137/090772873. https://doi.org/10.1137/090772873 [5] L. Binkowski, G. Koßmann, T. Ziegler, and R. Schwonnek. Elementary proof of QAOA convergence. New Journal of Physics, 26(7):073001, 2024. DOI: https://doi.org/10.1088/1367-2630/ad59bb. https://doi.org/10.1088/1367-2630/ad59bb [6] R. Blümel, N. Grzesiak, N. Pisenti, K. Wright, and Y. Nam. Power-optimal, stabilized entangling gate between trapped-ion qubits. npj Quantum Information, 7(1):147, 2021. DOI: https://doi.org/10.1038/s41534-021-00489-w. https://doi.org/10.1038/s41534-021-00489-w [7] D. Bluvstein, S. Evered, A. Geim, S. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al. Logical quantum processor based on reconfigurable atom arrays. Nature, 626(7997):58–65, 2024. DOI: https://doi.org/10.1038/s41586-023-06927-3. https://doi.org/10.1038/s41586-023-06927-3 [8] J. Bohnet, B. Sawyer, J. Britton, M. Wall, A. Rey, M. Foss-Feig, and J. Bollinger. Quantum spin dynamics and entanglement generation with hundreds of trapped ions. Science, 352(6291):1297–1301, 2016. DOI: https://doi.org/10.1126/science.aad9958. https://doi.org/10.1126/science.aad9958 [9] S. Bravyi, O. Dial, J. Gambetta, D. Gil, and Z. Nazario. The future of quantum computing with superconducting qubits. Journal of Applied Physics, 132(16), 2022. DOI: https://doi.org/10.1063/5.0082975. https://doi.org/10.1063/5.0082975 [10] M. Charikar, T. Leighton, S. Li, and A. Moitra. Vertex sparsifiers and abstract rounding algorithms. In 51st IEEE Symposium on Foundations of Computer Science (FOCS), pages 265–274, 2010. DOI: https://doi.org/10.1109/FOCS.2010.32. https://doi.org/10.1109/FOCS.2010.32 [11] C. Clark, H. Tinkey, B. Sawyer, A. Meier, K. Burkhardt, C. Seck, C. Shappert, N. Guise, C. Volin, S. Fallek, H. Hayden, W. Rellergert, and K. Brown. High-fidelity Bell-state preparation with $^{40}\mathrm{Ca}^{+}$ optical qubits.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

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

Tags

Source Information