Reinforcement learning assisted recursive QAOA
Tóm tắt
In recent years, variational quantum algorithms such as the Quantum Approximation Optimization Algorithm (QAOA) have gained popularity as they provide the hope of using NISQ devices to tackle hard combinatorial optimization problems. It is, however, known that at low depth, certain locality constraints of QAOA limit its performance. To go beyond these limitations, a non-local variant of QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of approximate solutions. The RQAOA has been studied comparatively less than QAOA, and it is less understood, for instance, for what family of instances it may fail to provide high-quality solutions. However, as we are tackling NP-hard problems (specifically, the Ising spin model), it is expected that RQAOA does fail, raising the question of designing even better quantum algorithms for combinatorial optimization. In this spirit, we identify and analyze cases where (depth-1) RQAOA fails and, based on this, propose a reinforcement learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly better on these identified instances where RQAOA underperforms and is similarly performing on instances where RQAOA is near-optimal. Our work exemplifies the potentially beneficial synergy between reinforcement learning and quantum (inspired) optimization in the design of new, even better heuristics for complex problems.
Tài liệu tham khảo
Google AI Quantum and Collaborators, Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Boixo S, Broughton M, Buckley BB et al.. Hartree-Fock on a superconducting qubit quantum computer. Science. 2020;369(6507):1084–9. https://doi.org/10.1126/science.abb9811.
Jurcevic P, Javadi-Abhari A, Bishop LS, Lauer I, Bogorin DF, Brink M, Capelluto L, Günlük O, Itoko T, Kanazawa N, Kandala A, Keefe GA, Krsulich K, Landers W, Lewandowski EP, McClure DT, Nannicini G, Narasgond A, Nayfeh HM, Pritchett E, Rothwell MB, Srinivasan S, Sundaresan N, Wang C, Wei KX, Wood CJ, Yau J-B, Zhang EJ, Dial OE, Chow JM, Gambetta JM. Demonstration of quantum volume 64 on a superconducting quantum computing system. Quantum Sci Technol. 2021;6(2):025020. https://doi.org/10.1088/2058-9565/abe519.
Ebadi S, Wang TT, Levine H, Keesling A, Semeghini G, Omran A, Bluvstein D, Samajdar R, Pichler H, Ho WW, Choi S, Sachdev S, Greiner M, Vuletić V, Lukin MD. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature. 2021;595(7866):227–32. https://doi.org/10.1038/s41586-021-03582-4.
Gong M, Wang S, Zha C, Chen M-C, Huang H-L, Wu Y, Zhu Q, Zhao Y, Li S, Guo S, Qian H, Ye Y, Chen F, Ying C, Yu J, Fan D, Wu D, Su H, Deng H, Rong H, Zhang K, Cao S, Lin J, Xu Y, Sun L, Guo C, Li N, Liang F, Bastidas VM, Nemoto K, Munro WJ, Huo Y-H, Lu C-Y, Peng C-Z, Zhu X, Pan J-W. Quantum walks on a programmable two-dimensional 62-qubit superconducting processor. Science. 2021;372(6545):948–52. https://doi.org/10.1126/science.abg7812.
Moll N, Barkoutsos P, Bishop LS, Chow JM, Cross A, Egger DJ, Filipp S, Fuhrer A, Gambetta JM, Ganzhorn M, Kandala A, Mezzacapo A, Müller P, Riess W, Salis G, Smolin J, Tavernelli I, Temme K. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci Technol. 2018;3(3):030503. https://doi.org/10.1088/2058-9565/aab822.
Benedetti M, Lloyd E, Sack S, Fiorentini M. Parameterized quantum circuits as machine learning models. Quantum Sci Technol. 2019;4(4):043001. https://doi.org/10.1088/2058-9565/ab4eb5.
Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm. 2014. arXiv preprint. arXiv:1411.4028.
Hastings MB. Classical and quantum bounded depth approximation algorithms. 2019. arXiv preprint. arXiv:1905.07047.
Marwaha K. Local classical max-cut algorithm outperforms \(p= 2\) qaoa on high-girth regular graphs. Quantum. 2021;5:437. https://doi.org/10.22331/q-2021-04-20-437.
Barak B, Marwaha K. Classical algorithms and quantum limitations for maximum cut on high-girth graphs. 2022. https://doi.org/10.4230/LIPICS.ITCS.2022.14.
Bravyi S, Kliesch A, Koenig R, Tang E. Obstacles to variational quantum optimization from symmetry protection. Phys Rev Lett. 2020;125(26). https://doi.org/10.1103/physrevlett.125.260505.
Farhi E, Gamarnik D, Gutmann S. The quantum approximate optimization algorithm needs to see the whole graph: a typical case. 2020. arXiv preprint. arXiv:2004.09002.
Farhi E, Gamarnik D, Gutmann S. The quantum approximate optimization algorithm needs to see the whole graph: worst case examples. 2020. arXiv preprint. arXiv:2005.08747.
Chou C-N, Love PJ, Sandhu JS, Shi J. Limitations of local quantum algorithms on random max-k-xor and beyond. 2021. arXiv preprint. arXiv:2108.06049.
Marwaha K, Hadfield S. Bounds on approximating max k xor with quantum and classical local algorithms. 2021. arXiv preprint. arXiv:2109.10833.
Bravyi S, Kliesch A, Koenig R, Tang E. Hybrid quantum-classical algorithms for approximate graph colouring. Quantum. 2022;6:678. https://doi.org/10.22331/q-2022-03-30-678.
Bravyi S, Gosset D, Grier D. Classical algorithms for forrelation. 2021. arXiv preprint. arXiv:2102.06963.
McClean JR, Harrigan MP, Mohseni M, Rubin NC, Jiang Z, Boixo S, Smelyanskiy VN, Babbush R, Neven H. Low-depth mechanisms for quantum optimization. PRX Quantum. 2021;2(3). https://doi.org/10.1103/prxquantum.2.030312.
Sutton RS, Barto AG. Reinforcement learning: an introduction. 2018.
Yao J, Bukov M, Lin L. Policy gradient based quantum approximate optimization algorithm. In: Mathematical and scientific machine learning. 2020. p. 605–34. PMLR.
Sung KJ, Yao J, Harrigan MP, Rubin NC, Jiang Z, Lin L, Babbush R, McClean JR. Using models to improve optimizers for variational quantum algorithms. Quantum Sci Technol. 2020;5(4):044008. https://doi.org/10.1088/2058-9565/abb6d9.
Yao J, Lin L, Bukov M. Reinforcement learning for many-body ground-state preparation inspired by counterdiabatic driving. Phys Rev X. 2021;11(3). https://doi.org/10.1103/physrevx.11.031070.
Yao J, Lin L, Bukov M. Rl-qaoa: a reinforcement learning approach to many-body ground state preparation. Bull Am Phys Soc. 2021;66.
Yao J, Kottering P, Gundlach H, Lin L, Bukov M. Noise-robust end-to-end quantum control using deep autoregressive policy networks. In: Mathematical and scientific machine learning. 2022. p. 1044–81. PMLR.
Jerbi S, Gyurik C, Marshall S, Briegel H, Dunjko V. Parametrized quantum policies for reinforcement learning. Adv Neural Inf Process Syst. 2021;34.
Wauters MM, Panizon E, Mbeng GB, Santoro GE. Reinforcement-learning-assisted quantum optimization. Phys Rev Res. 2020;2(3). https://doi.org/10.1103/physrevresearch.2.033446.
Khairy S, Shaydulin R, Cincio L, Alexeev Y, Balaprakash P. Learning to optimize variational quantum circuits to solve combinatorial problems. Proc AAAI Conf Artif Intell. 2020;34(03):2367–75. https://doi.org/10.1609/aaai.v34i03.5616.
Brady LT, Hadfield S. Iterative quantum algorithms for maximum independent set: a tale of low-depth quantum algorithms. 2023. arXiv:2309.13110.
Finžgar JR, Kerschbaumer A, Schuetz MJ, Mendl CB, Katzgraber HG. Quantum-informed recursive optimization algorithms. 2023. arXiv preprint. arXiv:2308.13607.
Dupont M, Evert B, Hodson MJ, Sundar B, Jeffrey S, Yamaguchi Y, Feng D, Maciejewski FB, Hadfield S, Alam MS et al.. Quantum-enhanced greedy combinatorial optimization solver. Sci Adv. 2023;9(45):0487.
Håstad J. Some optimal inapproximability results. J ACM. 2001;48(4):798–859.
Khot S, Kindler G, Mossel E, O’Donnell R. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J Comput. 2007;37(1):319–57.
Ozaeta A, van Dam W, McMahon PL. Expectation values from the single-layer quantum approximate optimization algorithm on ising problems. 2021. arXiv preprint. arXiv:2012.03421.
Sutton RS, McAllester D, Singh S, Mansour Y. Policy gradient methods for reinforcement learning with function approximation. Adv Neural Inf Process Syst. 1999;12.
Kakade SM. On the sample complexity of reinforcement learning. 2003.
Williams RJ. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach Learn. 1992;8(3–4):229–56. https://doi.org/10.1007/bf00992696.
Konda V, Tsitsiklis J. Actor-critic algorithms. Adv Neural Inf Process Syst. 1999;12.
Bittel L, Kliesch M. Training variational quantum algorithms is NP-hard. Phys Rev Lett. 2021;127(12). https://doi.org/10.1103/physrevlett.127.120502.
Brandao FG, Broughton M, Farhi E, Gutmann S, Neven H. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. 2018. arXiv preprint. arXiv:1812.04170.
Lotshaw PC, Humble TS, Herrman R, Ostrowski J, Siopsis G. Empirical performance bounds for quantum approximate optimization. Quantum Inf Process. 2021;20(12):403. https://doi.org/10.1007/s11128-021-03342-3.
Wurtz J, Lykov D. Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs. Phys Rev A. 2021;104(5). https://doi.org/10.1103/physreva.104.052419.
Shaydulin R, Lotshaw PC, Larson J, Ostrowski J, Humble TS. Parameter transfer for quantum approximate optimization of weighted maxcut. 2022. arXiv preprint. arXiv:2201.11785.
Moussa C, Wang H, Bäck T, Dunjko V. Unsupervised strategies for identifying optimal parameters in quantum approximate optimization algorithm. EPJ Quantum Technol. 2022;9(1). https://doi.org/10.1140/epjqt/s40507-022-00131-4.
Kingma DP, Ba J. Adam: a method for stochastic optimization. 2014. arXiv preprint. arXiv:1412.6980.