CoChat
Sign Up
Cited by 57Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchComplexity and Algorithms in Graphs

Multilevel Combinatorial Optimization across Quantum Architectures

Open access
Ushijima-Mwesigwa, Hayato, Shaydulin, Ruslan, Negre, Christian F. A., Mniszewski, Susan M., Alexeev, Yuri, Safro, Ilya·2021·ACM Transactions on Quantum Computing
DOI 10.1145/3425607
Open this paper in CoChat — free accountOpen PDF

Abstract

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3425607

Cites

46 of 46 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The proposed method allows to formulate and evaluate sub-QUBOs without the need of constructing the QUBO for the entire problem.

    “The proposed method allows to formulate and evaluate sub-QUBOs without the need of constructing the QUBO for the entire problem.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [139]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 50

  1. [10][10] David A Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. 2013. Graph partitioning and graph clustering . Vol. 588. American Mathematical Society Providence, RI. -
  2. [13][13] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. 2018. For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances. arXiv preprint arXiv:1812.04170 (2018). - · arXiv
  3. [14][14] A. Brandt. 2002. Multiscale Scientific Computation: Review 2001. In Multiscale and Multiresolution Methods . LNCSE, Vol. 20. Springer, 3-95. http://dx.doi.org/10.1007/978-3-642-56205-1\_1 - · DOI
  4. [16][16] Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent advances in graph partitioning. In Algorithm Engineering: Selected Results and Surveys. LNCS 9220, Springer-Verlag . Springer, 117-158. -
  5. [17][17] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. 2020. Cost-Function-Dependent Barren Plateaus in Shallow Quantum Neural Networks. arXiv:arXiv:2001.00550 - · arXiv
  6. [18][18] J. Cong and J. R. Shinnerl (Eds.). 2003. Multilevel Optimization and VLSICAD . Kluwer. -
  7. [19][19] Gavin E Crooks. 2018. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv:1811.08419 (2018). - · arXiv
  8. [22][22] Timothy A Davis, William W Hager, Scott P Kolodziej, and S Nuri Yeralan. 2019. Algorithm XXX: Mongoose, a graph coarsening and partitioning library. ACM Trans. Math. Software (2019). -
  9. [24][24] Yongcheng Ding, Lucas Lamata, José D. Martín-Guerrero, Enrique Lizaso, Samuel Mugel, et al. 2019. Towards Prediction of Financial Crashes with a D-Wave Quantum Computer. arXiv:arXiv:1904.05808 - · arXiv
  10. [25][25] Alexander Elgart and George A. Hagedorn. 2012. A note on the switching adiabatic theorem. J. Math. Phys. 53, 10 (Oct. 2012), 102202. https: //doi.org/10.1063/1.4748968 - · DOI
  11. [26][26] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, et al. 2001. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. (2001). https://doi.org/10.1126/science.1057726 arXiv:quant-ph/0104129 - · DOI · Paper page
  12. [27][27] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106 - · arXiv
  13. [28][28] Artur Garcia-Saez and Jordi Riu. 2019. Quantum Observables for continuous control of the Quantum Approximate Optimization Algorithm via Reinforcement Learning. arXiv preprint arXiv:1911.09682 (2019). - · arXiv
  14. [29][29] E Gelman and J Mandel. 1990. On multilevel iterative methods for optimization problems. Mathematical Programming 48, 1-3 (1990), 1-17. -
  15. [32][32] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy 2008) , Gaël Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11-15. -
  16. [34][34] Ryan Hamerly, Takahiro Inagaki, Peter L. McMahon, Davide Venturelli, Alireza Marandi, et al. 2019. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Science Advances 5, 5 (2019), eaau0823. -
  17. [35][35] William E Hart, Carl D Laird, Jean-Paul Watson, David L Woodruff, Gabriel A Hackebeil, et al. 2017. Pyomo-optimization modeling in python . Vol. 67. Springer. Manuscript submitted to ACM -
  18. [36][36] Manuel Holtgrewe, Peter Sanders, and Christian Schulz. 2010. Engineering a scalable high quality graph partitioner. In 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) . IEEE. https://doi.org/10.1109/ipdps.2010.5470485 - · DOI
  19. [37][37] Reiner Horst, Panos M Pardalos, and Nguyen Van Thoai. 2000. Introduction to global optimization . Springer Science & Business Media. -
  20. [38][38] Cupjin Huang, Mario Szegedy, Fang Zhang, Xun Gao, Jianxin Chen, et al. 2019. Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design. arXiv:arXiv:1909.02559 - · arXiv
  21. [44][44] Tosio Kato. 1950. On the Adiabatic Theorem of Quantum Mechanics. Journal of the Physical Society of Japan 5, 6 (Nov. 1950), 435-439. https://doi.org/10.1143/jpsj.5.435 - · DOI
  22. [47][47] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. 2019. Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems. Proceedings of the Thirty-Forth AAAI Conference on Artificial Intelligence (AAAI-20) (2019). -
  23. [48][48] Andrew D King, Jack Raymond, Trevor Lanting, Sergei V Isakov, Masoud Mohseni, et al. 2019. Scaling advantage in quantum simulation of geometrically frustrated magnets. arXiv preprint arXiv:1911.03446 (2019). - · arXiv
  24. [50][50] Jérôme Kunegis. 2013. KONECT - The Koblenz Network Collection. In Web Observatory Workshop . 1343-1350. -
  25. [51][51] Jérôme Kunegis. 2013. Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web . ACM, 1343-1350. -
  26. [57][57] Athanasios Migdalas, Panos M Pardalos, and Peter Värbrand. 2013. Multilevel optimization: algorithms and applications . Vol. 20. Springer Science & Business Media. -
  27. [60][60] John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, and Aram W. Harrow. 2019. Efficient classical simulation of random shallow 2D quantum circuits. arXiv:arXiv:2001.00021 - · arXiv
  28. [61][61] Christian F. A. Negre, Hayato Ushijima-Mwesigwa, and Susan M. Mniszewski. 2020. Detecting multiple communities using quantum annealing on the D-Wave system. PLOS ONE 15 (02 2020), 1-14. https://doi.org/10.1371/journal.pone.0227538 - · DOI · Paper page
  29. [63][63] Sergey Novikov, Robert Hinkey, Steven Disseler, James I Basham, Tameem Albash, et al. 2018. Exploring More-Coherent Quantum Annealing. arXiv preprint arXiv:1809.04485 (2018). - · arXiv
  30. [65][65] JS Otterbach, R Manenti, N Alidoust, A Bestwick, M Block, et al. 2017. Unsupervised Machine Learning on a Hybrid Quantum Computer. arXiv preprint arXiv:1712.05771 (2017). - · arXiv
  31. [66][66] G Pagano, A Bapat, P Becker, KS Collins, A De, et al. 2019. Quantum Approximate Optimization with a Trapped-Ion Quantum Simulator. arXiv preprint arXiv:1906.02700 (2019). - · arXiv
  32. [67][67] Ferran Parés, Dario Garcia Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguadé, et al. 2017. Fluid communities: a competitive, scalable and diverse community detection algorithm. In International Conference on Complex Networks and their Applications . Springer, 229-240. -
  33. [70][70] Hannes Pichler, Sheng-Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail D Lukin. 2018. Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays. arXiv preprint arXiv:1808.10816 (2018). - · arXiv
  34. [73][73] Thomas Harvey Rowan. 1990. Functional stability analysis of numerical algorithms. Ph.D. Dissertation. University of Texas at Austin. -
  35. [75][75] Ehsan Sadrfaridpour, Jeereddy Sandeep, Ken Kennedy, Andre Luckow, Talayeh Razzaghi, et al. 2017. Algebraic multigrid support vector machines. In ESANN 2017 proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning . ESANN, Bruges, Belgium. https://www.elen.ucl.ac.be/Proceedings/esann/esannpdf/es2017-37.pdf -
  36. [77][77] Ilya Safro, Dorit Ron, and Achi Brandt. 2008. Multilevel algorithms for linear ordering problems. ACM Journal of Experimental Algorithmics 13 (2008). -
  37. [78][78] Ilya Safro, Peter Sanders, and Christian Schulz. 2015. Advanced coarsening schemes for graph partitioning. ACM Journal of Experimental Algorithmics (JEA) 19 (2015), 2-2. -
  38. [82][82] Ruslan Shaydulin and Yuri Alexeev. 2019. Evaluating Quantum Approximate Optimization Algorithm: A Case Study. In 2019 Tenth International Green and Sustainable Computing Conference (IGSC) . IEEE. https://doi.org/10.1109/igsc48788.2019.8957201 - · DOI · Paper page
  39. [84][84] Ruslan Shaydulin and Ilya Safro. 2018. Aggregative Coarsening for Multilevel Hypergraph Partitioning. In 17th International Symposium on Experimental Algorithms (SEA 2018) (Leibniz International Proceedings in Informatics (LIPIcs)) , Gianlorenzo D'Angelo (Ed.), Vol. 103. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2:1-2:15. https://doi.org/10.4230/LIPIcs.SEA.2018.2 - · DOI
  40. [85][85] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. 2019. Multistart Methods for Quantum Approximate optimization. In 2019 IEEE High Performance Extreme Computing Conference (HPEC) . IEEE. https://doi.org/10.1109/hpec.2019.8916288 · DOI · Paper page
  41. [87][87] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Ilya Safro, Susan Mniszewski, and Yuri Alexeev. 2018. Community Detection Across Emerging Quantum Architectures. Proceedings of the 3rd International Workshop on Post Moore's Era Supercomputing (2018). -
  42. [92][92] Mario Szegedy. 2019. What do QAOA energies reveal about graphs? arXiv:arXiv:1912.12277 - · arXiv
  43. [95][95] Hayato Ushijima-Mwesigwa, Christian F. A. Negre, and Susan M. Mniszewski. 2017. Graph partitioning using quantum annealing on the D-Wave system. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing . ACM, 22-29. -
  44. [96][96] Hayato M Ushijima-Mwesigwa, Christian F A Negre, Susan M Mniszewski, and Ilya Safro. 2018. Multilevel Quantum Annealing For Graph Partitioning. Qubits 2018 D-Wave Users Conference (2018). -
  45. [97][97] Wim van Dam, Michele Mosca, and Umesh Vazirani. 2002. How Powerful is Adiabatic Quantum Computation? Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 279-287 (2001). (2002). https://doi.org/10.1109/SFCS.2001.959902 arXiv:arXiv:quantph/0206003 - · DOI · Paper page
  46. [98][98] Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung, Ryan Babbush, et al. 2019. Learning to learn with quantum neural networks via classical neural networks. arXiv preprint arXiv:1907.05415 (2019). - · arXiv
  47. [100][100] Stefan Voß, Silvano Martello, Ibrahim H Osman, and Catherine Roucairol. 2012. Meta-heuristics: Advances and trends in local search paradigms for optimization . Springer Science & Business Media. -
  48. [103][103] Xin-Chuan Wu, Sheng Di, Emma Maitreyee Dasgupta, Franck Cappello, Hal Finkel, et al. 2019. Full-State Quantum Circuit Simulationby Using Data Compression. In Proceedings of the High Performance Computing,Networking, Storage and Analysis International Conference (SC19) . IEEE Computer Society, Denver, CO, USA. -
  49. [104][104] M.-H. Yung, J. Casanova, A. Mezzacapo, J. McClean, L. Lamata, et al. 2014. From transistor to trapped-ion computers for quantum chemistry. Scientific Reports 4, 1 (Jan. 2014). https://doi.org/10.1038/srep03589 - · DOI · Paper page
  50. [105][105] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. 2018. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices. arXiv preprint arXiv:1812.01041 (2018). · arXiv

Cited by

Sorted by citations

Authors
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I.
Affiliations
  • Fujitsu (United States) (US)
  • Clemson University (US)
  • Los Alamos National Laboratory (US)
  • Argonne National Laboratory (US)
Venue
ACM Transactions on Quantum Computing
Publisher
Association for Computing Machinery (ACM)
Published
2021-02-13
Volume
2
Issue
1
Pages
1-29
ISSN
  • 2643-6809 (ISSN-L)
  • 2643-6817
DOI
10.1145/3425607
OpenAlex
W2981590007
Cited by
57
References
46
Citations by year
2026: 6 · 2025: 8 · 2024: 14 · 2023: 12 · 2022: 13 · 2021: 4
FWCI
3.80
Type
journal article
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM Transactions on Quantum Computing (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University)
Funders
Department of Energy, Labor and Economic Growth (-)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
hybrid quantum-classical algorithms, quantum annealing, D-Wave quantum annealer, graph partitioning, community detection, large-scale optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review