The quantum annealing gap and quench dynamics in the exact cover problem

Bernhard Irsigler and Tobias Grass

ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain

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


Quenching and annealing are extreme opposites in the time evolution of a quantum system: Annealing explores equilibrium phases of a Hamiltonian with slowly changing parameters and can be exploited as a tool for solving complex optimization problems. In contrast, quenches are sudden changes of the Hamiltonian, producing a non-equilibrium situation. Here, we investigate the relation between the two cases. Specifically, we show that the minimum of the annealing gap, which is an important bottleneck of quantum annealing algorithms, can be revealed from a dynamical quench parameter which describes the dynamical quantum state after the quench. Combined with statistical tools including the training of a neural network, the relation between quench and annealing dynamics can be exploited to reproduce the full functional behavior of the annealing gap from the quench data. We show that the partial or full knowledge about the annealing gap which can be gained in this way can be used to design optimized quantum annealing protocols with a practical time-to-solution benefit. Our results are obtained from simulating random Ising Hamiltonians, representing hard-to-solve instances of the exact cover problem.

Quantum annealing is a method to solve optimization problems via Hamiltonian engineering and quantum state preparation. The method requires that, at any time during the preparation process, the annealing is slow compared to the energy gap above the ground state. Unfortunately, for complex problems small gaps are a common bottleneck of quantum annealing. In this paper, we present strategies to gain knowledge of the gap function for specific computational problems by performing quench experiments and applying machine learning techniques. This knowledge is then shown to facilitate the design of optimized annealing algorithms. As compared to the usual homogeneous protocol, these protocols show an enhanced performance with increased annealing fidelities (see Figure).

► BibTeX data

► References

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

[2] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90 (1): 015002, Jan 2018. 10.1103/​revmodphys.90.015002.

[3] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. Perspectives of quantum annealing: methods and implementations. Rep. Prog. Phys., 83 (5): 054401, May 2020. 10.1088/​1361-6633/​ab85b8.

[4] M. Lewenstein, A. Sanpera, and V. Ahufinger. Ultracold Atoms in Optical Lattices: Simulating Quantum Many-body Systems. OUP Oxford, 2012. ISBN 9780199573127.

[5] R. Blatt and C. F. Roos. Quantum simulations with trapped ions. Nat. Phys., 8 (4): 277–284, Apr 2012. 10.1038/​nphys2252.

[6] Alán Aspuru-Guzik and Philip Walther. Photonic quantum simulators. Nat. Phys., 8 (4): 285–291, Apr 2012. 10.1038/​nphys2253.

[7] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. 10.22331/​q-2018-08-06-79.

[8] F Barahona. On the computational complexity of Ising spin glass models. J. Phys. A Math. Theor., 15 (10): 3241, 1982. 10.1088/​0305-4470/​15/​10/​028.

[9] 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. Quantum annealing with manufactured spins. Nature, 473 (7346): 194, May 2011. 10.1038/​nature10012.

[10] Philipp Hauke, Lars Bonnes, Markus Heyl, and Wolfgang Lechner. Probing entanglement in adiabatic quantum optimization with trapped ions. Front. Phys., 3: 21, 2015. 10.3389/​fphy.2015.00021.

[11] Tobias Graß, David Raventós, Bruno Juliá-Díaz, Christian Gogolin, and Maciej Lewenstein. Quantum annealing for the number-partitioning problem using a tunable spin glass of ions. Nat. Commun., 7: 11524, May 2016. 10.1038/​ncomms11524.

[12] A. W. Glaetzle, R. M. W. van Bijnen, P. Zoller, and W. Lechner. A coherent quantum annealer with Rydberg atoms. Nat. Commun., 8: 15813, Jun 2017. 10.1038/​ncomms15813.

[13] Valentin Torggler, Sebastian Krämer, and Helmut Ritsch. Quantum annealing with ultracold atoms in a multimode optical resonator. Phys. Rev. A, 95: 032310, Mar 2017. 10.1103/​PhysRevA.95.032310.

[14] Xingze Qiu, Peter Zoller, and Xiaopeng Li. Programmable quantum annealing architectures with ising quantum wires. PRX Quantum, 1: 020311, Nov 2020. 10.1103/​PRXQuantum.1.020311.

[15] 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 (5516): 472, Apr 2001. 10.1126/​science.1057726.

[16] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Phys. Rev. E, 58 (5): 5355, Nov 1998. 10.1103/​physreve.58.5355.

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

[18] Thomas Jörg, Florent Krzakala, Jorge Kurchan, and A. C. Maggs. Simple Glass Models and Their Quantum Annealing. Phys. Rev. Lett., 101: 147204, Oct 2008. 10.1103/​PhysRevLett.101.147204.

[19] 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. 10.1103/​PhysRevLett.104.020502.

[20] Thomas Jörg, Florent Krzakala, Guilhem Semerjian, and Francesco Zamponi. First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems. Phys. Rev. Lett., 104: 207206, May 2010. 10.1103/​PhysRevLett.104.207206.

[21] Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proc. Nat. Acad. Sci. USA, 107 (28): 12446, 2010. 10.1073/​pnas.1002116107.

[22] Sergey Knysh. Zero-temperature quantum annealing bottlenecks in the spin-glass phase. Nat. Commun., 7 (1): 12370, Aug 2016. 10.1038/​ncomms12370.

[23] Neil G. Dickson and M. H. S. Amin. Does Adiabatic Quantum Optimization Fail for NP-Complete Problems? Phys. Rev. Lett., 106: 050502, Feb 2011. 10.1103/​PhysRevLett.106.050502.

[24] Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, and Peter Shor. Quantum adiabatic algorithms, small gaps, and different paths. Quant. Inf. Comput., 11: 181, 2011.

[25] Neil G. Dickson and Mohammad H. Amin. Algorithmic approach to adiabatic quantum optimization. Phys. Rev. A, 85: 032303, Mar 2012. 10.1103/​PhysRevA.85.032303.

[26] Trevor Lanting, Andrew D. King, Bram Evert, and Emile Hoskinson. Experimental demonstration of perturbative anticrossing mitigation using nonuniform driver Hamiltonians. Phys. Rev. A, 96: 042322, Oct 2017. 10.1103/​PhysRevA.96.042322.

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

[28] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, and Peter Shor. Different strategies for optimization using the quantum adiabatic algorithm. arXiv, 1401.7320, 2014. https:/​/​​abs/​1401.7320v1.

[29] 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. 10.1103/​PhysRevB.95.184416.

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

[31] I. Ozfidan et al. Demonstration of a nonstoquastic hamiltonian in coupled superconducting flux qubits. Phys. Rev. Appl., 13: 034037, Mar 2020. 10.1103/​PhysRevApplied.13.034037.

[32] Alejandro Perdomo-Ortiz, Salvador E. Venegas-Andraca, and Alán Aspuru-Guzik. A study of heuristic guesses for adiabatic quantum computation. Quantum Inf. Process., 10 (1): 33, Feb 2011. 10.1007/​s11128-010-0168-z.

[33] Masaki Ohkuwa, Hidetoshi Nishimori, and Daniel A. Lidar. Reverse annealing for the fully connected $p$-spin model. Phys. Rev. A, 98: 022314, Aug 2018. 10.1103/​PhysRevA.98.022314.

[34] C. L. Baldwin and C. R. Laumann. Quantum algorithm for energy matching in hard optimization problems. Phys. Rev. B, 97: 224201, Jun 2018. 10.1103/​PhysRevB.97.224201.

[35] Tobias Graß. Quantum annealing with longitudinal bias fields. Phys. Rev. Lett., 123: 120501, Sep 2019. 10.1103/​PhysRevLett.123.120501.

[36] Zhijie Tang and Eliot Kapit. Unconventional quantum annealing methods for difficult trial problems. Phys. Rev. A, 103: 032612, Mar 2021. 10.1103/​PhysRevA.103.032612.

[37] Nicholas Chancellor. Modernizing quantum annealing using local searches. New J. Phys., 19 (2): 023024, Feb 2017. 10.1088/​1367-2630/​aa59c4.

[38] Tobias Graß and Maciej Lewenstein. Hybrid annealing: Coupling a quantum simulator to a classical computer. Phys. Rev. A, 95: 052309, May 2017. 10.1103/​PhysRevA.95.052309.

[39] James G. Morley, Nicholas Chancellor, Sougato Bose, and Viv Kendon. Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise. Phys. Rev. A, 99: 022339, Feb 2019. 10.1103/​PhysRevA.99.022339.

[40] Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon. Finding spin glass ground states using quantum walks. New J. Phys., 21 (12): 123022, Dec 2019. 10.1088/​1367-2630/​ab5ca2.

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

[42] Jeffrey Marshall, Davide Venturelli, Itay Hen, and Eleanor G. Rieffel. Power of pausing: Advancing understanding of thermalization in experimental quantum annealers. Phys. Rev. Appl., 11 (4): 044083, Apr 2019. 10.1103/​physrevapplied.11.044083.

[43] Huo Chen and Daniel A. Lidar. Why and when pausing is beneficial in quantum annealing. Phys. Rev. Appl., 14 (1): 014100, Jul 2020. 10.1103/​physrevapplied.14.014100.

[44] Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon, and Nicholas Chancellor. Energetic perspective on rapid quenches in quantum annealing. PRX Quantum, 2: 010338, Mar 2021. 10.1103/​PRXQuantum.2.010338.

[45] Lucas T. Brady, Christopher L. Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov. Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems. Phys. Rev. Lett., 126: 070505, Feb 2021. 10.1103/​PhysRevLett.126.070505.

[46] Emil A. Yuzbashyan, Oleksandr Tsyplyatyev, and Boris L. Altshuler. Relaxation and persistent oscillations of the order parameter in fermionic condensates. Phys. Rev. Lett., 96: 097005, Mar 2006. 10.1103/​PhysRevLett.96.097005.

[47] Bruno Sciolla and Giulio Biroli. Quantum quenches and off-equilibrium dynamical transition in the infinite-dimensional bose-hubbard model. Phys. Rev. Lett., 105: 220401, Nov 2010. 10.1103/​PhysRevLett.105.220401.

[48] Jad C. Halimeh, Valentin Zauner-Stauber, Ian P. McCulloch, Inés de Vega, Ulrich Schollwöck, and Michael Kastner. Prethermalization and persistent order in the absence of a thermal phase transition. Phys. Rev. B, 95: 024302, Jan 2017. 10.1103/​PhysRevB.95.024302.

[49] Jad C. Halimeh and Valentin Zauner-Stauber. Dynamical phase diagram of quantum spin chains with long-range interactions. Phys. Rev. B, 96: 134427, Oct 2017. 10.1103/​PhysRevB.96.134427.

[50] Ingo Homrighausen, Nils O. Abeling, Valentin Zauner-Stauber, and Jad C. Halimeh. Anomalous dynamical phase in quantum spin chains with long-range interactions. Phys. Rev. B, 96: 104436, Sep 2017. 10.1103/​PhysRevB.96.104436.

[51] Bojan Žunkovič, Markus Heyl, Michael Knap, and Alessandro Silva. Dynamical quantum phase transitions in spin chains with long-range interactions: Merging different concepts of nonequilibrium criticality. Phys. Rev. Lett., 120 (13): 130601, Mar 2018. 10.1103/​physrevlett.120.130601.

[52] R. Jafari. Dynamical quantum phase transition and quasi particle excitation. Sci. Rep., 9 (1), Feb 2019. 10.1038/​s41598-019-39595-3.

[53] Utkarsh Mishra, R Jafari, and Alireza Akbari. Disordered kitaev chain with long-range pairing: Loschmidt echo revivals and dynamical phase transitions. J. Phys. A Math. Theor., 53 (37): 375301, Aug 2020. 10.1088/​1751-8121/​ab97de.

[54] J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V. Gorshkov, Z.-X. Gong, and C. Monroe. Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator. Nature, 551 (7682): 601, Nov 2017. 10.1038/​nature24654.

[55] Marin Bukov, Alexandre G. R. Day, Dries Sels, Phillip Weinberg, Anatoli Polkovnikov, and Pankaj Mehta. Reinforcement learning in different phases of quantum control. Phys. Rev. X, 8: 031086, Sep 2018. 10.1103/​PhysRevX.8.031086.

[56] Jian Lin, Zhong Yuan Lai, and Xiaopeng Li. Quantum adiabatic algorithm design using reinforcement learning. Phys. Rev. A, 101: 052327, May 2020. 10.1103/​PhysRevA.101.052327.

[57] Phillip Weinberg and Marin Bukov. QuSpin: a python package for dynamics and exact diagonalisation of quantum many body systems part i: spin chains. SciPost Physics, 2 (1), Feb 2017. 10.21468/​scipostphys.2.1.003.

[58] Phillip Weinberg and Marin Bukov. QuSpin: a python package for dynamics and exact diagonalisation of quantum many body systems. part II: bosons, fermions and higher spins. SciPost Physics, 7 (2), Aug 2019. 10.21468/​scipostphys.7.2.020.

[59] Bernhard Irsigler. annealingGapAndQuenchDynamics. https:/​/​​b-irsigler/​annealingGapAndQuenchDynamics, 2021.

[60] Pankaj Mehta, Marin Bukov, Ching-Hao Wang, Alexandre G.R. Day, Clint Richardson, Charles K. Fisher, and David J. Schwab. A high-bias, low-variance introduction to machine learning for physicists. Phys. Rep., 810: 1–124, May 2019. 10.1016/​j.physrep.2019.03.001.

[61] François Chollet et al. Keras. https:/​/​, 2015.

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-28 21:22:12). On SAO/NASA ADS no data on citing works was found (last attempt 2022-05-28 21:22:13).