De-Signing Hamiltonians for Quantum Adiabatic Optimization

Elizabeth Crosson1, Tameem Albash1,2, Itay Hen3,4, and A. P. Young5

1Center for Quantum Information and Control (CQuIC), Department of Physics and Astronomy , University of New Mexico, Albuquerque, NM 87131, USA
2Electrical and Computer Engineering, University of New Mexico, Albuquerque, NM 87131, USA
3Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
4Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
5Department of Physics, University of California, Santa Cruz, California 95064, USA

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


Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.

Non-stoquastic Hamiltonians, defined as Hamiltonians with positive or non-real off-diagonal matrix elements in every choice of local basis, have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with quantum adiabatic optimization (QAO). This conjecture stems primarily from the fact that adiabatic computation based on non-stoquastic Hamiltonians can be universal for quantum computing and is not efficiently simulable by quantum Monte Carlo. However, in order for non-stoquastic Hamiltonians to provide a quantum advantage, they must enhance the minimum spectral gap along the Hamiltonian interpolation of the adiabatic algorithm relative to their stoquastic counterpart. In this work we define a locality-preserving mapping which takes every non-stoquastic QAO protocol to a corresponding stoquastic QAO protocol. Considering various ensembles (dense matrices, signed graphs, and local Hamiltonians) we find that the non-stoquastic adiabatic paths have smaller spectral gaps than the corresponding stoquastic adiabatic paths, with high probability. Our results call into question the promise attributed to non-stoquastic drivers to serve as generic catalysts of quantum speedups in QAO.

► BibTeX data

► References

[1] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Review, 50 (4): 755–787, 2008. https:/​/​​10.1137/​080734479.

[2] Abbas Al-Shimary and Jiannis K. Pachos. Energy gaps of Hamiltonians from graph Laplacians. arXiv e-prints, art. arXiv:1010.4130, October 2010.

[3] Tameem Albash. Role of nonstoquastic catalysts in quantum adiabatic optimization. Phys. Rev. A, 99: 042334, Apr 2019. https:/​/​​10.1103/​PhysRevA.99.042334.

[4] Tameem Albash, Gene Wagenbreth, and Itay Hen. Off-diagonal expansion quantum monte carlo. Phys. Rev. E, 96: 063309, Dec 2017. https:/​/​​10.1103/​PhysRevE.96.063309.

[5] M. H. S. Amin and V. Choi. First-order quantum phase transition in adiabatic quantum computation. Phys. Rev. A, 80: 062326, Dec 2009. https:/​/​​10.1103/​PhysRevA.80.062326.

[6] Evgeny Andriyash and Mohammad H. Amin. Can quantum Monte Carlo simulate quantum annealing? arXiv e-prints, art. arXiv:1703.09277, March 2017.

[7] Fatihcan M. Atay and Shiping Liu. Cheeger constants, structural balance, and spectral clustering analysis for signed graphs. Discrete Mathematics, 343 (1): 111616, 2020. ISSN 0012-365X. https:/​/​​10.1016/​j.disc.2019.111616.

[8] A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2000.

[9] Jacob D. Biamonte and Peter J. Love. Realizable hamiltonians for universal adiabatic quantum computers. Phys. Rev. A, 78: 012352, Jul 2008. https:/​/​​10.1103/​PhysRevA.78.012352.

[10] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani, Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad H. Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven. Computational multiqubit tunnelling in programmable quantum annealers. Nature Communications, 7: 10327, 01 2016. https:/​/​​10.1038/​ncomms10327.

[11] S. Bravyi and B. Terhal. Complexity of stoquastic frustration-free hamiltonians. SIAM Journal on Computing, 39 (4): 1462–1485, 2015/​05/​22 2009. https:/​/​​10.1137/​08072689X.

[12] Sergey Bravyi. Monte carlo simulation of stoquastic hamiltonians. Quantum Info. Comput., 15 (13–14): 1122–1140, October 2015. ISSN 1533-7146.

[13] Sergey Bravyi and David Gosset. Polynomial-time classical simulation of quantum ferromagnets. Phys. Rev. Lett., 119: 100503, Sep 2017. https:/​/​​10.1103/​PhysRevLett.119.100503.

[14] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal. Merlin-Arthur Games and Stoquastic Complexity. arXiv e-prints, art. quant-ph/​0611021, November 2006.

[15] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal. The complexity of stoquastic local hamiltonian problems. Quantum Info. Comput., 8 (5): 361–385, May 2008. ISSN 1533-7146.

[16] J. Brooke, D. Bitko, T. F., Rosenbaum, and G. Aeppli. Quantum annealing of a disordered magnet. Science, 284 (5415): 779–781, 1999. https:/​/​​10.1126/​science.284.5415.779.

[17] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92 in CBMS Regional Conference Series. American Mathematical Society, 1997.

[18] Elizabeth Crosson and John Bowen. Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians. arXiv e-prints, art. arXiv:1703.10133, March 2017.

[19] Elizabeth Crosson and Aram W Harrow. Simulated quantum annealing can be exponentially faster than classical simulated annealing. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 714–723. IEEE, 2016. https:/​/​​10.1109/​FOCS.2016.81.

[20] Elizabeth Crosson and Aram W. Harrow. Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians. arXiv e-prints, art. arXiv:1812.02144, December 2018.

[21] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, and Peter Shor. Different Strategies for Optimization Using the Quantum Adiabatic Algorithm. arXiv e-prints, art. arXiv:1401.7320, January 2014.

[22] Gabriel A. Durkin. Quantum speedup at zero temperature via coherent catalysis. Phys. Rev. A, 99: 032315, Mar 2019. https:/​/​​10.1103/​PhysRevA.99.032315.

[23] Alexander Elgart and George A. Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53 (10): 102202, 2012. https:/​/​​10.1063/​1.4748968.

[24] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum Computation by Adiabatic Evolution. arXiv e-prints, art. quant-ph/​0001106, January 2000.

[25] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Quantum Adiabatic Evolution Algorithms versus Simulated Annealing. arXiv e-prints, art. quant-ph/​0201031, January 2002.

[26] Edward Farhi, David Gosset, Itay Hen, A. W. Sandvik, Peter Shor, A. P. Young, and Francesco Zamponi. Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Phys. Rev. A, 86: 052334, Nov 2012. https:/​/​​10.1103/​PhysRevA.86.052334.

[27] Delphine Féral and Sandrine Péché. The largest eigenvalue of rank one deformation of large wigner matrices. Communications in Mathematical Physics, 272 (1): 185–228, 2007. https:/​/​​10.1007/​s00220-007-0209-3.

[28] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 219 (5–6): 343–348, 3 1994. https:/​/​​10.1016/​0009-2614(94)00117-0.

[29] Joel. N Franklin. Matrix Theory (Dover Books on Mathematics). Dover Publications, Inc., Mineola, NY, USA, 1993.

[30] Antoine Gournay. An isoperimetric constant for signed graphs. Expositiones Mathematicae, 34 (3): 339 – 351, 2016. ISSN 0723-0869. https:/​/​​10.1016/​j.exmath.2015.10.002.

[31] Lalit Gupta and Itay Hen. Elucidating the interplay between non-stoquasticity and the sign problem. Advanced Quantum Technologies, 3 (1): 1900108, 2020. https:/​/​​10.1002/​qute.201900108.

[32] Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. arXiv e-prints, art. arXiv:1910.09071, October 2019.

[33] Matthew B. Hastings. Obstructions to classically simulating the quantum adiabatic algorithm. Quantum Info. Comput., 13 (11–12): 1038–1076, November 2013. ISSN 1533-7146.

[34] Itay Hen. Excitation gap from optimized correlation functions in quantum monte carlo simulations. Phys. Rev. E, 85: 036705, Mar 2012. https:/​/​​10.1103/​PhysRevE.85.036705.

[35] Itay Hen and Marcelo S. Sarandy. Driver hamiltonians for constrained optimization in quantum annealing. Phys. Rev. A, 93: 062312, Jun 2016. https:/​/​​10.1103/​PhysRevA.93.062312.

[36] Itay Hen and Federico M. Spedalieri. Quantum annealing for constrained optimization. Phys. Rev. Applied, 5: 034007, Mar 2016. https:/​/​​10.1103/​PhysRevApplied.5.034007.

[37] Itay Hen and A. P. Young. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E, 84: 061152, Dec 2011. https:/​/​​10.1103/​PhysRevE.84.061152.

[38] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo, and Matthias Troyer. Nonstoquastic hamiltonians and quantum annealing of an ising spin glass. Phys. Rev. B, 95: 184416, May 2017. https:/​/​​10.1103/​PhysRevB.95.184416.

[39] Roger A Horn, Roger A Horn, and Charles R Johnson. Matrix analysis. Cambridge university press, 1990.

[40] Sergei V. Isakov, Guglielmo Mazzola, Vadim N. Smelyanskiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, and Matthias Troyer. Understanding quantum tunneling through quantum monte carlo simulations. Phys. Rev. Lett., 117: 180402, Oct 2016. https:/​/​​10.1103/​PhysRevLett.117.180402.

[41] Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys., 48 (10): –, 2007. https:/​/​​10.1063/​1.2798382.

[42] Michael Jarret. Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices. arXiv e-prints, art. arXiv:1804.06857, April 2018.

[43] Michael Jarret and Stephen P. Jordan. Adiabatic optimization without local minima. Quantum Info. Comput., 15 (3–4): 181–199, March 2015. ISSN 1533-7146.

[44] Michael Jarret, Stephen P. Jordan, and Brad Lackey. Adiabatic optimization versus diffusion monte carlo methods. Phys. Rev. A, 94: 042318, Oct 2016. https:/​/​​10.1103/​PhysRevA.94.042318.

[45] Michael Jarret, Brad Lackey, Aike Liu, and Kianna Wan. Quantum adiabatic optimization without heuristics. arXiv e-prints, art. arXiv:1810.04686, October 2018.

[46] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Phys. Rev. E, 58: 5355–5363, Nov 1998. https:/​/​​10.1103/​PhysRevE.58.5355.

[47] T. Kato. On the adiabatic theorem of quantum mechanics. J. Phys. Soc. Jap., 5: 435, 1950. https:/​/​​10.1143/​JPSJ.5.435.

[48] Joel Klassen and Barbara M. Terhal. Two-local qubit Hamiltonians: when are they stoquastic? Quantum, 3: 139, May 2019. ISSN 2521-327X. https:/​/​​10.22331/​q-2019-05-06-139.

[49] Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, and Barbara Terhal. Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians. arXiv e-prints, art. arXiv:1906.08800, Jun 2019.

[50] Daniel A. Lidar, Ali T. Rezakhani, and Alioscia Hamma. Adiabatic approximation with exponential accuracy for many-body systems and quantum computation. Journal of Mathematical Physics, 50 (10): 102106, 2009. https:/​/​​10.1063/​1.3236685.

[51] Cheng-Wei Liu, Anatoli Polkovnikov, and Anders W. Sandvik. Quantum versus classical annealing: Insights from scaling theory and results for spin glasses on 3-regular graphs. Phys. Rev. Lett., 114: 147203, Apr 2015. https:/​/​​10.1103/​PhysRevLett.114.147203.

[52] E. Y. Loh, J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar. Sign problem in the numerical simulation of many-electron systems. Phys. Rev. B, 41: 9301–9307, May 1990. https:/​/​​10.1103/​PhysRevB.41.9301.

[53] Florian Martin. Frustration and isoperimetric inequalities for signed graphs. Discrete Applied Mathematics, 217: 276 – 285, 2017. ISSN 0166-218X. https:/​/​​10.1016/​j.dam.2016.09.015.

[54] Milad Marvian, Daniel A. Lidar, and Itay Hen. On the computational complexity of curing non-stoquastic hamiltonians. Nature Communications, 10 (1): 1571, 2019. https:/​/​​10.1038/​s41467-019-09501-6.

[55] Wenxing Nie, Hosho Katsura, and Masaki Oshikawa. Ground-state energies of spinless free fermions and hard-core bosons. Phys. Rev. Lett., 111: 100402, Sep 2013. https:/​/​​10.1103/​PhysRevLett.111.100402.

[56] Wenxing Nie, Hosho Katsura, and Masaki Oshikawa. Particle statistics, frustration, and ground-state energy. Phys. Rev. B, 97: 125153, Mar 2018. https:/​/​​10.1103/​PhysRevB.97.125153.

[57] Hideyoshi Nishimori and Kabuki Takada. Exponential enhancement of the efficiency of quantum annealing by non-stoquastic hamiltonians. Frontiers in ICT, 4: 2, 2017. ISSN 2297-198X. https:/​/​​10.3389/​fict.2017.00002.

[58] A. Bariş Özgüler, Robert Joynt, and Maxim G. Vavilov. Steering random spin systems to speed up the quantum adiabatic algorithm. Phys. Rev. A, 98: 062311, Dec 2018. https:/​/​​10.1103/​PhysRevA.98.062311.

[59] Jérémie Roland and Nicolas J. Cerf. Quantum search by local adiabatic evolution. Phys. Rev. A, 65 (4): 042308–, 03 2002. https:/​/​​10.1103/​PhysRevA.65.042308.

[60] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, 07 2014. https:/​/​​10.1126/​science.1252319.

[61] Giuseppe E. Santoro, Roman Martoňák, Erio Tosatti, and Roberto Car. Theory of quantum annealing of an Ising spin glass. Science, 295 (5564): 2427–2430, 2002. https:/​/​​10.1126/​science.1068774.

[62] Yuya Seki and Hidetoshi Nishimori. Quantum annealing with antiferromagnetic fluctuations. Phys. Rev. E, 85: 051112, May 2012. https:/​/​​10.1103/​PhysRevE.85.051112.

[63] Beatriz Seoane and Hidetoshi Nishimori. Many-body transverse interactions in the quantum annealing of the p -spin ferromagnet. J. Phys. A, 45 (43): 435301, 2012. https:/​/​​10.1088/​1751-8113/​45/​43/​435301.

[64] Yuki Susa, Johann F. Jadebeck, and Hidetoshi Nishimori. Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic hamiltonian. Phys. Rev. A, 95: 042321, Apr 2017. https:/​/​​10.1103/​PhysRevA.95.042321.

[65] Kabuki Takada, Yu Yamashiro, and Hidetoshi Nishimori. Mean-field solution of the weak-strong cluster problem for quantum annealing with stoquastic and non-stoquastic catalysts. Journal of the Physical Society of Japan, 89 (4): 044001, 2020. https:/​/​​10.7566/​JPSJ.89.044001.

[66] Terence Tao. Topics in random matrix theory. Graduate studies in Mathematics, 132: 46–47, 2012.

[67] Matthias Troyer and Uwe-Jens Wiese. Computational complexity and fundamental limitations to fermionic quantum monte carlo simulations. Phys. Rev. Lett., 94: 170201, May 2005. https:/​/​​10.1103/​PhysRevLett.94.170201.

[68] Walter Vinci and Daniel A. Lidar. Non-stoquastic hamiltonians in quantum annealing via geometric phases. npj Quantum Information, 3 (1): 38, 2017. https:/​/​​10.1038/​s41534-017-0037-z.

[69] Gregory H. Wannier. Probability of violation of the ehrenfest principle in fast passage. Physics Physique Fizika, 1: 251–253, May 1965. https:/​/​​10.1103/​PhysicsPhysiqueFizika.1.251.

[70] Eugene P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics, 67 (2): 325–327, 1958. ISSN 0003486X. https:/​/​​10.2307/​1970008.

[71] A. P. Young, S. Knysh, and V. N. Smelyanskiy. Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett., 101: 170503, Oct 2008. https:/​/​​10.1103/​PhysRevLett.101.170503.

[72] A. P. Young, S. Knysh, and V. N. Smelyanskiy. First-order phase transition in the quantum adiabatic algorithm. Phys. Rev. Lett., 104: 020502, Jan 2010. https:/​/​​10.1103/​PhysRevLett.104.020502.

Cited by

[1] E. J. Crosson and D. A. Lidar, "Prospects for Quantum Enhancement with Diabatic Quantum Annealing", arXiv:2008.09913.

[2] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low depth mechanisms for quantum optimization", arXiv:2008.08615.

[3] Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, and Barbara M. Terhal, "Sign-curing local Hamiltonians: termwise versus global stoquasticity and the use of Clifford transformations", arXiv:2007.11964.

[4] Eleni Marina Lykiardopoulou, Alex Zucca, Sam A. Scivier, and Mohammad H. Amin, "Improving nonstoquastic quantum annealing with spin-reversal transformations", arXiv:2010.00065.

The above citations are from SAO/NASA ADS (last updated successfully 2020-10-19 19:10:43). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2020-10-19 18:56:05).