Parameter Setting In Quantum Approximate Optimization Of Weighted Problems

Shree Hari Sureshbabu¹, Dylan Herman¹, Ruslan Shaydulin¹, Joao Basso², Shouvanik Chakrabarti¹, Yue Sun¹, and Marco Pistoia¹

¹Global Technology Applied Research, JPMorgan Chase, New York, NY 10017
²Department of Mathematics, University of California, Berkeley, CA 94720

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for $pgeq 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for $p=1$ the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only $1.1$ percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.

Featured image: Procedure for transferring optimal QAOA parameters from the Sherrington-Kirkpatrick (SK) model to a weighted MaxCut problem on a regular graph of the same size. The $gamma^{text{inf}}$ parameters are scaled according to the proposed method, while the $beta^{text{inf}}$ are fixed. The plot shows that QAOA with the novel scaling technique achieves higher approximation ratio than prior techniques and comparable to optimized parameters.

Popular summary

This work investigates parameter setting rules for QAOA, a leading quantum heuristic algorithm, applied to a general class of combinatorial optimization problems. Parameter optimization is a significant bottleneck towards near-term application. A general parameter-scaling heuristic for transferring QAOA parameters between weighted problem instances is proposed and rigorous results showing the effectiveness of this procedure on MaxCut is presented. Additionally, the numerics show that this procedure significantly reduces the training time of QAOA for portfolio optimization, which is an important problem in financial engineering

► BibTeX data

@article{Sureshbabu2024parametersettingin, doi = {10.22331/q-2024-01-18-1231}, url = {https://doi.org/10.22331/q-2024-01-18-1231}, title = {Parameter {S}etting in {Q}uantum {A}pproximate {O}ptimization of {W}eighted {P}roblems}, author = {Sureshbabu, Shree Hari and Herman, Dylan and Shaydulin, Ruslan and Basso, Joao and Chakrabarti, Shouvanik and Sun, Yue and Pistoia, Marco}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1231}, month = jan, year = {2024}<br /> }

► References

[1] Michael A Nielsen and Isaac L Chuang. “Quantum computation and quantum information”. Cambridge university press. (2010).
https://doi.org/10.1017/CBO9780511976667

[2] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev. “A survey of quantum computing for finance” (2022). url: https://doi.org/10.48550/arXiv.2201.02773.
https://doi.org/10.48550/arXiv.2201.02773

[3] Tad Hogg and Dmitriy Portnov. “Quantum optimization”. Information Sciences 128, 181–197 (2000).
https://doi.org/10.1016/s0020-0255(00)00052-9

[4] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). url: https://doi.org/10.48550/arXiv.1411.4028.
https://doi.org/10.48550/arXiv.1411.4028

[5] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. “From the quantum approximate optimization algorithm to a quantum alternating operator ansatz”. Algorithms 12, 34 (2019). url: https://doi.org/10.3390/a12020034.
https://doi.org/10.3390/a12020034

[6] Sami Boulebnane and Ashley Montanaro. “Solving boolean satisfiability problems with the quantum approximate optimization algorithm” (2022). url: https://doi.org/10.48550/arXiv.2208.06909.
https://doi.org/10.48550/arXiv.2208.06909

[7] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. “The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model”. Proceedings of the Conference on the Theory of Quantum Computation, Communication and Cryptography 7, 1–21 (2022).
https://doi.org/10.4230/LIPICS.TQC.2022.7

[8] Matthew B. Hastings. “A classical algorithm which also beats $frac{1}{2}+frac{2}{pi}frac{1}{sqrt{d}}$ for high girth max-cut” (2021). url: https://doi.org/10.48550/arXiv.2111.12641.
https://doi.org/10.48550/arXiv.2111.12641

[9] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble. “Parameter transfer for quantum approximate optimization of weighted MaxCut”. ACM Transactions on Quantum Computing 4, 1–15 (2023).
https://doi.org/10.1145/3584706

[10] Sami Boulebnane, Xavier Lucas, Agnes Meyder, Stanislaw Adaszewski, and Ashley Montanaro. “Peptide conformational sampling using the quantum approximate optimization algorithm”. npj Quantum Information 9, 70 (2023). url: https://doi.org/10.1038/s41534-023-00733-5.
https://doi.org/10.1038/s41534-023-00733-5

[11] Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia, and Thomas Wellens. “Benchmarking the performance of portfolio optimization with qaoa”. Quantum Information Processing 22, 25 (2022).
https://doi.org/10.1007/s11128-022-03766-5

[12] Sami Boulebnane and Ashley Montanaro. “Predicting parameters for the quantum approximate optimization algorithm for max-cut from the infinite-size limit” (2021). url: https://doi.org/10.48550/arXiv.2110.10685.
https://doi.org/10.48550/arXiv.2110.10685

[13] 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 (2022).
https://doi.org/10.22331/q-2022-07-07-759

[14] Amir Dembo, Andrea Montanari, and Subhabrata Sen. “Extremal cuts of sparse random graphs”. The Annals of Probability 45 (2017).
https://doi.org/10.1214/15-aop1084

[15] Gavin E Crooks. “Performance of the quantum approximate optimization algorithm on the maximum cut problem” (2018). url: https://doi.org/10.48550/arXiv.1811.08419.
https://doi.org/10.48550/arXiv.1811.08419

[16] Michael Streif and Martin Leib. “Training the quantum approximate optimization algorithm without access to a quantum processing unit”. Quantum Science and Technology 5, 034008 (2020).
https://doi.org/10.1088/2058-9565/ab8c2b

[17] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices”. Physical Review X 10, 021067 (2020).
https://doi.org/10.1103/PhysRevX.10.021067

[18] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. “Multistart methods for quantum approximate optimization”. In IEEE High Performance Extreme Computing Conference. Pages 1–8. (2019).
https://doi.org/10.1109/hpec.2019.8916288

[19] Xinwei Lee, Yoshiyuki Saito, Dongsheng Cai, and Nobuyoshi Asai. “Parameters fixing strategy for quantum approximate optimization algorithm”. 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (2021).
https://doi.org/10.1109/qce52317.2021.00016

[20] Stefan H. Sack and Maksym Serbyn. “Quantum annealing initialization of the quantum approximate optimization algorithm”. Quantum 5, 491 (2021).
https://doi.org/10.22331/q-2021-07-01-491

[21] Ohad Amosy, Tamuz Danzig, Ely Porat, Gal Chechik, and Adi Makmal. “Iterative-free quantum approximate optimization algorithm using neural networks” (2022). url: https://doi.org/10.48550/arXiv.2208.09888.
https://doi.org/10.48550/arXiv.2208.09888

[22] Danylo Lykov, Roman Schutski, Alexey Galda, Valeri Vinokur, and Yuri Alexeev. “Tensor network quantum simulator with step-dependent parallelization”. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 582–593. (2022).
https://doi.org/10.1109/QCE53715.2022.00081

[23] Matija Medvidović and Giuseppe Carleo. “Classical variational simulation of the quantum approximate optimization algorithm”. npj Quantum Information 7 (2021).
https://doi.org/10.1038/s41534-021-00440-z

[24] Ruslan Shaydulin and Stefan M. Wild. “Exploiting symmetry reduces the cost of training QAOA”. IEEE Transactions on Quantum Engineering 2, 1–9 (2021).
https://doi.org/10.1109/tqe.2021.3066275

[25] Ruslan Shaydulin and Yuri Alexeev. “Evaluating quantum approximate optimization algorithm: A case study”. Tenth International Green and Sustainable Computing Conference (2019).
https://doi.org/10.1109/IGSC48788.2019.8957201

[26] Fernando G. S. L. Brandão, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. “For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances” (2018). url: https://doi.org/10.48550/arXiv.1812.04170.
https://doi.org/10.48550/arXiv.1812.04170

[27] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte. “Parameter concentrations in quantum approximate optimization”. Physical Review A 104 (2021).
https://doi.org/10.1103/physreva.104.l010401

[28] Phillip C. Lotshaw, Travis S. Humble, Rebekah Herrman, James Ostrowski, and George Siopsis. “Empirical performance bounds for quantum approximate optimization”. Quantum Information Processing 20, 403 (2021).
https://doi.org/10.1007/s11128-021-03342-3

[29] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. “Transferability of optimal qaoa parameters between random graphs”. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 171–180. (2021).
https://doi.org/10.1109/QCE52317.2021.00034

[30] Xinwei Lee, Ningyi Xie, Dongsheng Cai, Yoshiyuki Saito, and Nobuyoshi Asai. “A depth-progressive initialization strategy for quantum approximate optimization algorithm”. Mathematics 11, 2176 (2023).
https://doi.org/10.3390/math11092176

[31] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. “Learning to optimize variational quantum circuits to solve combinatorial problems”. Proceedings of the AAAI Conference on Artificial Intelligence 34, 2367–2375 (2020).
https://doi.org/10.1609/aaai.v34i03.5616

[32] Guillaume Verdon, Michael Broughton, Jarrod R. McClean, Kevin J. Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni. “Learning to learn with quantum neural networks via classical neural networks” (2019). url: https://doi.org/10.48550/arXiv.1907.05415.
https://doi.org/10.48550/arXiv.1907.05415

[33] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. “Reinforcement-learning-based variational quantum circuits optimization for combinatorial problems” (2019). url: https://doi.org/10.48550/arXiv.1911.04574.
https://doi.org/10.48550/arXiv.1911.04574

[34] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro. “Reinforcement-learning-assisted quantum optimization”. Physical Review Research 2 (2020).
https://doi.org/10.1103/physrevresearch.2.033446

[35] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh. “Accelerating quantum approximate optimization algorithm using machine learning”. 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE) (2020).
https://doi.org/10.23919/date48585.2020.9116348

[36] Jiahao Yao, Lin Lin, and Marin Bukov. “Reinforcement learning for many-body ground-state preparation inspired by counterdiabatic driving”. Physical Review X 11 (2021).
https://doi.org/10.1103/physrevx.11.031070

[37] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. “Quantum approximate optimization algorithm for MaxCut: A fermionic view”. Physical Review A 97 (2018).
https://doi.org/10.1103/physreva.97.022304

[38] Jonathan Wurtz and Danylo Lykov. “The fixed angle conjecture for QAOA on regular MaxCut graphs” (2021). url: https://doi.org/10.48550/arXiv.2107.00677.
https://doi.org/10.48550/arXiv.2107.00677

[39] Stuart Hadfield. “Quantum algorithms for scientific computing and approximate optimization” (2018). url: https://doi.org/10.48550/1805.03265.
https://doi.org/10.48550/1805.03265

[40] Paul Glasserman. “Monte carlo methods in financial engineering”. Volume 53. Springer. (2004).
https://doi.org/10.1007/978-0-387-21617-1

[41] Walter Rudin. “Real and complex analysis”. McGraw-Hill. (1974).

[42] Walter Rudin. “Principles of mathematical analysis”. McGraw-hill. (1976).

[43] Colin McDiarmid. “On the method of bounded differences”. Page 148–188. London Mathematical Society Lecture Note Series. Cambridge University Press. (1989).
https://doi.org/10.1017/CBO9781107359949.008

[44] Lutz Warnke. “On the method of typical bounded differences”. Combinatorics, Probability and Computing 25, 269–299 (2016).
https://doi.org/10.1017/S0963548315000103

[45] Roman Vershynin. “High-dimensional probability: An introduction with applications in data science”. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press. (2018).
https://doi.org/10.1017/9781108231596

[46] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. “Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models”. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022).
https://doi.org/10.1109/focs54457.2022.00039

[47] G Parisi. “A sequence of approximated solutions to the s-k model for spin glasses”. Journal of Physics A: Mathematical and General 13, L115 (1980).
https://doi.org/10.1088/0305-4470/13/4/009

[48] Michel Talagrand. “The Parisi formula”. Annals of Mathematics (2006).
https://doi.org/10.4007/annals.2006.163.221

[49] Dmitry Panchenko. “The Sherrington-Kirkpatrick model”. Springer Science & Business Media. (2013).
https://doi.org/10.1007/978-1-4614-6289-7

[50] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C Lotshaw. “QAOAKit: A toolkit for reproducible study, application, and verification of QAOA”. Second International Workshop on Quantum Computing Software (2021).
https://doi.org/10.1109/QCS54837.2021.00011

[51] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. “The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model” (2021). url: https://doi.org/10.48550/arXiv.2110.14206.
https://doi.org/10.48550/arXiv.2110.14206

[52] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia. “Constrained optimization via quantum zeno dynamics”. Communications Physics 6, 219 (2023).
https://doi.org/10.1038/s42005-023-01331-9

[53] N. Slate, E. Matwiejew, S. Marsh, and J. B. Wang. “Quantum walk-based portfolio optimisation”. Quantum 5, 513 (2021).
https://doi.org/10.22331/q-2021-07-28-513

[54] Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin, and Stefan Dulman. “Portfolio rebalancing experiments using the quantum alternating operator ansatz” (2019). url: https://doi.org/10.48550/arXiv.1911.05296.
https://doi.org/10.48550/arXiv.1911.05296

[55] Tianyi Hao, Ruslan Shaydulin, Marco Pistoia, and Jeffrey Larson. “Exploiting in-constraint energy in constrained variational quantum optimization”. 2022 IEEE/ACM Third International Workshop on Quantum Computing Software (QCS) (2022).
https://doi.org/10.1109/qcs56647.2022.00017

[56] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, and Marco Pistoia. “Alignment between initial state and mixer improves qaoa performance for constrained optimization”. npj Quantum Information 9, 121 (2023).
https://doi.org/10.1038/s41534-023-00787-5

[57] “Qiskit finance”. https://qiskit.org/documentation/finance/.
https://qiskit.org/documentation/finance/

[58] Steven G. Johnson. “The NLopt nonlinear-optimization package” (2022). http://github.com/stevengj/nlopt.
http://github.com/stevengj/nlopt

[59] Michael JD Powell. “The BOBYQA algorithm for bound constrained optimization without derivatives”. Cambridge NA Report NA2009/06 26 (2009).

[60] Ruslan Shaydulin and Stefan M. Wild. “Importance of kernel bandwidth in quantum machine learning”. Physical Review A 106 (2022).
https://doi.org/10.1103/physreva.106.042407

[61] Abdulkadir Canatar, Evan Peters, Cengiz Pehlevan, Stefan M. Wild, and Ruslan Shaydulin. “Bandwidth enables generalization in quantum kernel models” (2022). url: https://doi.org/10.48550/arXiv.2206.06686.
https://doi.org/10.48550/arXiv.2206.06686

[62] Kaining Zhang, Liu Liu, Min-Hsiu Hsieh, and Dacheng Tao. “Escaping from the barren plateau via gaussian initializations in deep variational quantum circuits”. In Advances in Neural Information Processing Systems. Volume 35, pages 18612–18627. Curran Associates, Inc. (2022).

Cited by

[1] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, “Quantum computing for finance”, Nature Reviews Physics 5 8, 450 (2023).

[2] Abid Khan, Bryan K. Clark, and Norm M. Tubman, “Pre-optimizing variational quantum eigensolvers with tensor networks”, arXiv:2310.12965, (2023).

[3] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia, “Constrained optimization via quantum Zeno dynamics”, Communications Physics 6 1, 219 (2023).

[4] Igor Gaidai and Rebekah Herrman, “Performance Analysis of Multi-Angle QAOA for p > 1”, arXiv:2312.00200, (2023).

[5] Filip B. Maciejewski, Stuart Hadfield, Benjamin Hall, Mark Hodson, Maxime Dupont, Bram Evert, James Sud, M. Sohaib Alam, Zhihui Wang, Stephen Jeffrey, Bhuvanesh Sundar, P. Aaron Lott, Shon Grabbe, Eleanor G. Rieffel, Matthew J. Reagor, and Davide Venturelli, “Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems”, arXiv:2308.12423, (2023).

[6] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia, “Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem”, arXiv:2308.02342, (2023).

[7] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele, and Procolo Lucignano, “Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters”, arXiv:2307.14079, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-01-18 12:27:11). 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 2024-01-18 12:27:09: Could not fetch cited-by data for 10.22331/q-2024-01-18-1231 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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-01-18-1231/

Generative Data Intelligence

Parameter Setting in Quantum Approximate Optimization of Weighted Problems

Abstract

Popular summary

► BibTeX data

► References

Cited by

Drake Threatened With Lawsuit Over Tupac AI Vocals

Shiba Inu Leads in Robinhood’s Crypto Performance

Latest Intelligence

Best Crypto Casinos of 2024: A comprehensive guide

DOJ Disputes Roman Storm’s Characterization of Tornado Cash Operations in New Filing

Best Players Available for Day 3 of the 2024 NFL Draft

Top 5 Crypto Presales: BDAG Leads the Pack with 30,000x ROI Potential

Forbes Unveils 20 Crypto ‘Zombies,’ Declares Ripple And XRP Among The Undead

Consob, Italy’s Watchdog, Bans Additional Forex And Cryptocurrency Trading Websites – CryptoInfoNet

Chat with us