Counterdiabaticity and the quantum approximate optimization algorithm

Jonathan Wurtz and Peter J. Love

Department of Physics and Astronomy, Tufts University, Medford, Massachusetts 02155, USA

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

Abstract

The quantum approximate optimization algorithm (QAOA) is a near-term hybrid algorithm intended to solve combinatorial optimization problems, such as MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the $p\to\infty$ limit the final state is an exact maximal eigenstate in accordance with the adiabatic theorem. In this work, the connection between QAOA and adiabaticity is made explicit by inspecting the regime of $p$ large but finite. By connecting QAOA to counterdiabatic (CD) evolution, we construct CD-QAOA angles which mimic a counterdiabatic schedule by matching Trotter "error" terms to approximate adiabatic gauge potentials which suppress diabatic excitations arising from finite ramp speed. In our construction, these "error" terms are helpful, not detrimental, to QAOA. Using this matching to link QAOA with quantum adiabatic algorithms (QAA), we show that the approximation ratio converges to one at least as $1-C(p)\sim 1/p^{\mu}$. We show that transfer of parameters between graphs, and interpolating angles for $p+1$ given $p$ are both natural byproducts of CD-QAOA matching. Optimization of CD-QAOA angles is equivalent to optimizing a continuous adiabatic schedule. Finally, we show that, using a property of variational adiabatic gauge potentials, QAOA is at least counterdiabatic, not just adiabatic, and has better performance than finite time adiabatic evolution. We demonstrate the method on three examples: a 2 level system, an Ising chain, and the MaxCut problem.

► BibTeX data

► References

[1] E. Farhi, J. Goldstone, and S. Gutmann, (2014), arXiv:1411.4028 [quant-ph].
arXiv:1411.4028

[2] J. Preskill, Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[3] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, (2021), arXiv:2101.08448 [quant-ph].
arXiv:2101.08448

[4] A. Lucas, Frontiers in Physics 2 (2014), 10.3389/​fphy.2014.00005.
https:/​/​doi.org/​10.3389/​fphy.2014.00005

[5] T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018).
https:/​/​doi.org/​10.1103/​RevModPhys.90.015002

[6] M. H. S. Amin, Phys. Rev. Lett. 102, 220401 (2009).
https:/​/​doi.org/​10.1103/​PhysRevLett.102.220401

[7] S. H. Sack and M. Serbyn, (2021), arXiv:2101.05742 [quant-ph].
https:/​/​doi.org/​10.22331/​q-2021-07-01-491
arXiv:2101.05742

[8] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Rev. Mod. Phys. 91, 045001 (2019).
https:/​/​doi.org/​10.1103/​RevModPhys.91.045001

[9] G. Rigolin, G. Ortiz, and V. H. Ponce, Phys. Rev. A 78, 052508 (2008).
https:/​/​doi.org/​10.1103/​PhysRevA.78.052508

[10] S. Bachmann, W. De Roeck, and M. Fraas, Phys. Rev. Lett. 119, 060201 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.060201

[11] A. del Campo and W. H. Zurek, International Journal of Modern Physics A 29, 1430018 (2014).
https:/​/​doi.org/​10.1142/​s0217751x1430018x

[12] J. I. Latorre and R. Orús, Phys. Rev. A 69, 062302 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.062302

[13] R. Barankov and A. Polkovnikov, Physical Review Letters 101 (2008), 10.1103/​physrevlett.101.076801.
https:/​/​doi.org/​10.1103/​physrevlett.101.076801

[14] B. F. Schiffer, J. Tura, and J. I. Cirac, (2021), arXiv:2103.01226 [quant-ph].
arXiv:2103.01226

[15] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X 10 (2020), 10.1103/​physrevx.10.021067.
https:/​/​doi.org/​10.1103/​physrevx.10.021067

[16] F. G. S. L. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, (2018), arXiv:1812.04170 [quant-ph].
arXiv:1812.04170

[17] Z.-C. Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon, Physical Review X 7 (2017), 10.1103/​physrevx.7.021027.
https:/​/​doi.org/​10.1103/​physrevx.7.021027

[18] L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov, Phys. Rev. Lett. 126, 070505 (2021a).
https:/​/​doi.org/​10.1103/​PhysRevLett.126.070505

[19] M. Streif and M. Leib, Quantum Science and Technology 5, 034008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8c2b

[20] M. Born and V. Fock, Zeitschrift für Physik 51, 165 (1928).
https:/​/​doi.org/​10.1007/​BF01343193

[21] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, (2000), arXiv:quant-ph/​0001106 [quant-ph].
arXiv:quant-ph/0001106

[22] A. T. Rezakhani, W.-J. Kuo, A. Hamma, D. A. Lidar, and P. Zanardi, Phys. Rev. Lett. 103, 080502 (2009).
https:/​/​doi.org/​10.1103/​PhysRevLett.103.080502

[23] C. Brif, M. D. Grace, M. Sarovar, and K. C. Young, New Journal of Physics 16, 065013 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​6/​065013

[24] L. T. Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov, and A. V. Gorshkov, (2021b), arXiv:2107.01218 [quant-ph].
arXiv:2107.01218

[25] S. Bao, S. Kleer, R. Wang, and A. Rahmani, Phys. Rev. A 97, 062343 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.97.062343

[26] T. Chasseur, L. S. Theis, Y. R. Sanders, D. J. Egger, and F. K. Wilhelm, Phys. Rev. A 91, 043421 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.91.043421

[27] P. W. Claeys, M. Pandey, D. Sels, and A. Polkovnikov, Phys. Rev. Lett. 123, 090602 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.123.090602

[28] S. Sachdev, Quantum Phase Transitions, 2nd ed. (Cambridge University Press, 2011).

[29] H. Nishimori and K. Takada, Frontiers in ICT 4, 2 (2017).
https:/​/​doi.org/​10.3389/​fict.2017.00002

[30] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Nature 473, 194 (2011).
https:/​/​doi.org/​10.1038/​nature10012

[31] S. Sugiura, P. W. Claeys, A. Dymarsky, and A. Polkovnikov, Phys. Rev. Research 3, 013102 (2021).
https:/​/​doi.org/​10.1103/​PhysRevResearch.3.013102

[32] M. V. Berry, Journal of Physics A: Mathematical and Theoretical 42, 365303 (2009).
https:/​/​doi.org/​10.1088/​1751-8113/​42/​36/​365303

[33] M. Kolodrubetz, D. Sels, P. Mehta, and A. Polkovnikov, Physics Reports 697, 1 (2017).
https:/​/​doi.org/​10.1016/​j.physrep.2017.07.001

[34] M. Pandey, P. W. Claeys, D. K. Campbell, A. Polkovnikov, and D. Sels, Phys. Rev. X 10, 041017 (2020).
https:/​/​doi.org/​10.1103/​PhysRevX.10.041017

[35] D. Sels and A. Polkovnikov, Proceedings of the National Academy of Sciences 114, E3909 (2017).
https:/​/​doi.org/​10.1073/​pnas.1619826114

[36] M. B. Hastings and X.-G. Wen, Phys. Rev. B 72, 045141 (2005).
https:/​/​doi.org/​10.1103/​PhysRevB.72.045141

[37] J. Wurtz and A. Polkovnikov, Phys. Rev. B 101, 195138 (2020).
https:/​/​doi.org/​10.1103/​PhysRevB.101.195138

[38] N. Hatano and M. Suzuki, Lecture Notes in Physics , 37–68 (2005).
https:/​/​doi.org/​10.1007/​11526216_2

[39] S. Blanes, F. Casas, J. Oteo, and J. Ros, Physics Reports 470, 151–238 (2009).
https:/​/​doi.org/​10.1016/​j.physrep.2008.11.001

[40] X. Chen, I. Lizuain, A. Ruschhaupt, D. Guéry-Odelin, and J. G. Muga, Phys. Rev. Lett. 105, 123003 (2010).
https:/​/​doi.org/​10.1103/​PhysRevLett.105.123003

[41] J. Dziarmaga, Phys. Rev. Lett. 95, 245701 (2005).
https:/​/​doi.org/​10.1103/​PhysRevLett.95.245701

[42] M. Kolodrubetz, B. K. Clark, and D. A. Huse, Physical Review Letters 109 (2012), 10.1103/​physrevlett.109.015701.
https:/​/​doi.org/​10.1103/​physrevlett.109.015701

[43] A. Dutta, G. Aeppli, B. K. Chakrabarti, U. Divakaran, T. F. Rosenbaum, and D. Sen, (2015), arXiv:1012.0653 [cond-mat.stat-mech].
arXiv:1012.0653

[44] D. J. Egger, J. Mareček, and S. Woerner, Quantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[45] A. G. R. Day, M. Bukov, P. Weinberg, P. Mehta, and D. Sels, Phys. Rev. Lett. 122, 020601 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.122.020601

[46] G. B. Mbeng, R. Fazio, and G. Santoro, (2019), arXiv:1906.08948 [quant-ph].
arXiv:1906.08948

[47] V. Viswanath and G. Müller, The Recursion Method (Springer US, 2008).

[48] J. Wurtz and P. Love, Phys. Rev. A 103, 042612 (2021).
https:/​/​doi.org/​10.1103/​PhysRevA.103.042612

Cited by

[1] Yahui Chai, Yong-Jian Han, Yu-Chun Wu, Ye Li, Menghan Dou, and Guo-Ping Guo, "Shortcuts to the quantum approximate optimization algorithm", Physical Review A 105 4, 042415 (2022).

[2] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and Xi Chen, "Digitized-counterdiabatic quantum approximate optimization algorithm", Physical Review Research 4 1, 013141 (2022).

[3] Vladimir Kremenetski, Tad Hogg, Stuart Hadfield, Stephen J. Cotton, and Norm M. Tubman, "Quantum Alternating Operator Ansatz (QAOA) Phase Diagrams and Applications for Quantum Chemistry", arXiv:2108.13056.

[4] Jiahao Yao, Lin Lin, and Marin Bukov, "Reinforcement Learning for Many-Body Ground-State Preparation Inspired by Counterdiabatic Driving", Physical Review X 11 3, 031070 (2021).

[5] Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble, "Scaling Quantum Approximate Optimization on Near-term Hardware", arXiv:2201.02247.

[6] Narendra N. Hegade, Xi Chen, and Enrique Solano, "Digitized-Counterdiabatic Quantum Optimization", arXiv:2201.00790.

[7] Jiahao Yao, Haoya Li, Marin Bukov, Lin Lin, and Lexing Ying, "Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum Circuits", arXiv:2203.16707.

[8] N. N. Hegade, P. Chandarana, K. Paul, X. Chen, F. Albarrán-Arriagada, and E. Solano, "Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms", arXiv:2112.08347.

[9] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J. Egger, "Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware", arXiv:2202.03459.

[10] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale, "Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA", arXiv:2111.04572.

[11] Lucas T. Brady, Lucas Kocia, Przemyslaw Bienias, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov, "Behavior of Analog Quantum Algorithms", arXiv:2107.01218.

[12] Jonathan Wurtz and Danylo Lykov, "Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs", Physical Review A 104 5, 052419 (2021).

[13] Changhao Yi, "Success of digital adiabatic simulation with large Trotter step", Physical Review A 104 5, 052603 (2021).

[14] Jonathan Wurtz and Danylo Lykov, "The fixed angle conjecture for QAOA on regular MaxCut graphs", arXiv:2107.00677.

[15] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble, "Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut", arXiv:2201.11785.

[16] Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao, "QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines", arXiv:2205.11762.

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-28 19:03:17) and SAO/NASA ADS (last updated successfully 2022-05-28 19:03:18). The list may be incomplete as not all publishers provide suitable and complete citation data.