1London Centre for Nanotechnology, UCL, London WC1H 0AH, UK
2Newham Collegiate Sixth Form Centre, 326 Barking Rd, London, E6 2BB, UK
3Department of Physics and Astronomy, UCL, London WC1E 6BT, UK
4Department of Electronic & Electrical Engineering, UCL, London WC1E 7JE, UK
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
By exploiting the link between time-independent Hamiltonians and thermalisation, heuristic predictions on the performance of continuous-time quantum walks for MAX-CUT are made. The resulting predictions depend on the number of triangles in the underlying MAX-CUT graph. We extend these results to the time-dependent setting with multi-stage quantum walks and Floquet systems. The approach followed here provides a novel way of understanding the role of unitary dynamics in tackling combinatorial optimisation problems with continuous-time quantum algorithms.
Popular summary
Continuous-time quantum walks contain a free parameter. A well-optimised parameter results in a better quality of solution. In order to optimise the quantum walk, we utilise the well-established hypothesis that closed systems can thermalise. The associated temperature turns out to be high. By effectively modelling the density of states for the quantum walk we can reliably estimate the optimal choice of free parameter without a (classical) variational outer-loop. Importantly, the estimated optimal choice of the free parameter can be tied to properties of the underlying MAX-CUT graph.
This work presents a novel approach, combining statistical physics with quantum optimization. Future work might involve extending the insights in this paper to a broader range of quantum approaches to optimisation.
► BibTeX data
► References
[1] Edward Farhi and Sam Gutmann. “Quantum computation and decision trees”. Phys. Rev. A 58, 915–928 (1998).
https://doi.org/10.1103/PhysRevA.58.915
[2] Andrew M. Childs. “Universal computation by quantum walk”. Phys. Rev. Lett. 102, 180501 (2009).
https://doi.org/10.1103/PhysRevLett.102.180501
[3] Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yogesh N. Joglekar, and Peng Xue. “Experimental realization of continuous-time quantum walks on directed graphs and their application in pagerank”. Optica 7, 1524–1530 (2020).
https://doi.org/10.1364/OPTICA.396228
[4] Yunkai Wang, Shengjun Wu, and Wei Wang. “Controlled quantum search on structured databases”. Phys. Rev. Res. 1, 033016 (2019).
https://doi.org/10.1103/PhysRevResearch.1.033016
[5] Yang Wang, Shichuan Xue, Junjie Wu, and Ping Xu. “Continuous-time quantum walk based centrality testing on weighted graphs”. Scientific Reports 12, 6001 (2022).
https://doi.org/10.1038/s41598-022-09915-1
[6] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. “Exponential algorithmic speedup by a quantum walk”. In ACM (2003).
https://doi.org/10.1145/780542.780552
[7] Josh A. Izaac, Xiang Zhan, Zhihao Bian, Kunkun Wang, Jian Li, Jingbo B. Wang, and Peng Xue. “Centrality measure based on continuous-time quantum walks and experimental realization”. Phys. Rev. A 95, 032318 (2017).
https://doi.org/10.1103/PhysRevA.95.032318
[8] T. Loke, J. W. Tang, J. Rodriguez, M. Small, and J. B. Wang. “Comparing classical and quantum pageranks”. Quantum Information Processing 16, 25 (2016).
https://doi.org/10.1007/s11128-016-1456-z
[9] Andrew M. Childs and Jeffrey Goldstone. “Spatial search by quantum walk”. Phys. Rev. A 70, 022314 (2004).
https://doi.org/10.1103/PhysRevA.70.022314
[10] Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon. “Finding spin glass ground states using quantum walks”. New Journal of Physics 21, 123022 (2019).
https://doi.org/10.1088/1367-2630/ab5ca2
[11] Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chancellor, and Viv Kendon. “Comparing the hardness of max 2-sat problem instances for quantum and classical algorithms”. Phys. Rev. Res. 5, 023151 (2023).
https://doi.org/10.1103/PhysRevResearch.5.023151
[12] Adam Callison. “Continuous-time quantum computing”. PhD thesis. Imperial College London. (2021).
https://doi.org/10.25560/91503
[13] 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 (2021).
https://doi.org/10.1103/PRXQuantum.2.010338
[14] J. M. Deutsch. “Quantum statistical mechanics in a closed system”. Phys. Rev. A 43, 2046–2049 (1991).
https://doi.org/10.1103/PhysRevA.43.2046
[15] Mark Srednicki. “Chaos and quantum thermalization”. Phys. Rev. E 50, 888–901 (1994).
https://doi.org/10.1103/PhysRevE.50.888
[16] Joshua M Deutsch. “Eigenstate thermalization hypothesis”. Reports on Progress in Physics 81, 082001 (2018).
https://doi.org/10.1088/1361-6633/aac9f1
[17] Marcos Rigol. “Breakdown of thermalization in finite one-dimensional systems”. Phys. Rev. Lett. 103, 100403 (2009).
https://doi.org/10.1103/PhysRevLett.103.100403
[18] Fabian H L Essler and Maurizio Fagotti. “Quench dynamics and relaxation in isolated integrable quantum spin chains”. Journal of Statistical Mechanics: Theory and Experiment 2016, 064002 (2016).
https://doi.org/10.1088/1742-5468/2016/06/064002
[19] Marlon Brenes, Tyler LeBlond, John Goold, and Marcos Rigol. “Eigenstate thermalization in a locally perturbed integrable system”. Phys. Rev. Lett. 125, 070605 (2020).
https://doi.org/10.1103/PhysRevLett.125.070605
[20] Jae Dong Noh. “Eigenstate thermalization hypothesis and eigenstate-to-eigenstate fluctuations”. Phys. Rev. E 103, 012129 (2021).
https://doi.org/10.1103/PhysRevE.103.012129
[21] David A. Huse, Rahul Nandkishore, Vadim Oganesyan, Arijeet Pal, and S. L. Sondhi. “Localization-protected quantum order”. Phys. Rev. B 88, 014206 (2013).
https://doi.org/10.1103/PhysRevB.88.014206
[22] Rahul Nandkishore and David A. Huse. “Many-body localization and thermalization in quantum statistical mechanics”. Annual Review of Condensed Matter Physics 6, 15–38 (2015). arXiv:https://doi.org/10.1146/annurev-conmatphys-031214-014726.
https://doi.org/10.1146/annurev-conmatphys-031214-014726
arXiv:https://doi.org/10.1146/annurev-conmatphys-031214-014726
[23] Ehud Altman. “Many-body localization and quantum thermalization”. Nature Physics 14, 979–983 (2018).
https://doi.org/10.1038/s41567-018-0305-7
[24] Marcos Rigol, Vanja Dunjko, and Maxim Olshanii. “Thermalization and its mechanism for generic isolated quantum systems”. Nature 452, 854–858 (2008).
https://doi.org/10.1038/nature06838
[25] Giulio Biroli, Corinna Kollath, and Andreas M. Läuchli. “Effect of rare fluctuations on the thermalization of isolated quantum systems”. Phys. Rev. Lett. 105, 250401 (2010).
https://doi.org/10.1103/PhysRevLett.105.250401
[26] Lea F. Santos and Marcos Rigol. “Onset of quantum chaos in one-dimensional bosonic and fermionic systems and its relation to thermalization”. Phys. Rev. E 81, 036206 (2010).
https://doi.org/10.1103/PhysRevE.81.036206
[27] R. Steinigeweg, J. Herbrych, and P. Prelovšek. “Eigenstate thermalization within isolated spin-chain systems”. Phys. Rev. E 87, 012118 (2013).
https://doi.org/10.1103/PhysRevE.87.012118
[28] Hyungwon Kim, Tatsuhiko N. Ikeda, and David A. Huse. “Testing whether all eigenstates obey the eigenstate thermalization hypothesis”. Phys. Rev. E 90, 052105 (2014).
https://doi.org/10.1103/PhysRevE.90.052105
[29] R. Steinigeweg, A. Khodja, H. Niemeyer, C. Gogolin, and J. Gemmer. “Pushing the limits of the eigenstate thermalization hypothesis towards mesoscopic quantum systems”. Phys. Rev. Lett. 112, 130403 (2014).
https://doi.org/10.1103/PhysRevLett.112.130403
[30] Keith R. Fratus and Mark Srednicki. “Eigenstate thermalization in systems with spontaneously broken symmetry”. Phys. Rev. E 92, 040103 (2015).
https://doi.org/10.1103/PhysRevE.92.040103
[31] Abdellah Khodja, Robin Steinigeweg, and Jochen Gemmer. “Relevance of the eigenstate thermalization hypothesis for thermal relaxation”. Phys. Rev. E 91, 012120 (2015).
https://doi.org/10.1103/PhysRevE.91.012120
[32] Rubem Mondaini and Marcos Rigol. “Eigenstate thermalization in the two-dimensional transverse field ising model. ii. off-diagonal matrix elements of observables”. Phys. Rev. E 96, 012157 (2017).
https://doi.org/10.1103/PhysRevE.96.012157
[33] Toru Yoshizawa, Eiki Iyoda, and Takahiro Sagawa. “Numerical large deviation analysis of the eigenstate thermalization hypothesis”. Phys. Rev. Lett. 120, 200604 (2018).
https://doi.org/10.1103/PhysRevLett.120.200604
[34] David Jansen, Jan Stolpp, Lev Vidmar, and Fabian Heidrich-Meisner. “Eigenstate thermalization and quantum chaos in the holstein polaron model”. Phys. Rev. B 99, 155130 (2019).
https://doi.org/10.1103/PhysRevB.99.155130
[35] S. Trotzky, Y-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch. “Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional bose gas”. Nature Physics 8, 325–330 (2012).
https://doi.org/10.1038/nphys2232
[36] Govinda Clos, Diego Porras, Ulrich Warring, and Tobias Schaetz. “Time-resolved observation of thermalization in an isolated quantum system”. Phys. Rev. Lett. 117, 170401 (2016).
https://doi.org/10.1103/PhysRevLett.117.170401
[37] Adam M. Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, and Markus Greiner. “Quantum thermalization through entanglement in an isolated many-body system”. Science 353, 794–800 (2016).
https://doi.org/10.1126/science.aaf6725
[38] G. Kucsko, S. Choi, J. Choi, P. C. Maurer, H. Zhou, R. Landig, H. Sumiya, S. Onoda, J. Isoya, F. Jelezko, E. Demler, N. Y. Yao, and M. D. Lukin. “Critical thermalization of a disordered dipolar spin system in diamond”. Phys. Rev. Lett. 121, 023601 (2018).
https://doi.org/10.1103/PhysRevLett.121.023601
[39] Yijun Tang, Wil Kao, Kuan-Yu Li, Sangwon Seo, Krishnanand Mallayya, Marcos Rigol, Sarang Gopalakrishnan, and Benjamin L. Lev. “Thermalization near integrability in a dipolar quantum newton’s cradle”. Phys. Rev. X 8, 021030 (2018).
https://doi.org/10.1103/PhysRevX.8.021030
[40] J.R. Johansson, P.D. Nation, and Franco Nori. “Qutip: An open-source python framework for the dynamics of open quantum systems”. Computer Physics Communications 183, 1760–1772 (2012).
https://doi.org/10.1016/j.cpc.2012.02.021
[41] J.R. Johansson, P.D. Nation, and Franco Nori. “Qutip 2: A python framework for the dynamics of open quantum systems”. Computer Physics Communications 184, 1234–1240 (2013).
https://doi.org/10.1016/j.cpc.2012.11.019
[42] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. “Exploring network structure, dynamics, and function using networkx”. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference. Pages 11 – 15. Pasadena, CA USA (2008). url: https://conference.scipy.org/proceedings/SciPy2008/paper_2/.
https://conference.scipy.org/proceedings/SciPy2008/paper_2/
[43] Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. “Random walks: A review of algorithms and applications”. IEEE Transactions on Emerging Topics in Computational Intelligence 4, 95–107 (2020).
https://doi.org/10.1109/tetci.2019.2952908
[44] Henrik Wilming, Thiago R. de Oliveira, Anthony J. Short, and Jens Eisert. “Equilibration times in closed quantum many-body systems”. Page 435–455. Springer International Publishing. (2018).
https://doi.org/10.1007/978-3-319-99046-0_18
[45] James R. Garrison and Tarun Grover. “Does a single eigenstate encode the full hamiltonian?”. Physical Review X 8 (2018).
https://doi.org/10.1103/physrevx.8.021026
[46] Peter Reimann. “Eigenstate thermalization: Deutsch’s approach and beyond”. New Journal of Physics 17, 055025 (2015).
https://doi.org/10.1088/1367-2630/17/5/055025
[47] Tameem Albash and Daniel A. Lidar. “Adiabatic quantum computation”. Reviews of Modern Physics 90 (2018).
https://doi.org/10.1103/revmodphys.90.015002
[48] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. “Perspectives of quantum annealing: methods and implementations”. Reports on Progress in Physics 83, 054401 (2020).
https://doi.org/10.1088/1361-6633/ab85b8
[49] 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”. Phys. Rev. X 10, 021067 (2020).
https://doi.org/10.1103/PhysRevX.10.021067
[50] Laba and Tkachuk. “Geometric characteristics of quantum evolution: curvature and torsion”. Condensed Matter Physics 20, 13003 (2017).
https://doi.org/10.5488/cmp.20.13003
[51] Kh.P. Gnatenko, H.P. Laba, and V.M. Tkachuk. “Geometric properties of evolutionary graph states and their detection on a quantum computer”. Physics Letters A 452, 128434 (2022).
https://doi.org/10.1016/j.physleta.2022.128434
[52] Luca D’Alessio, Yariv Kafri, Anatoli Polkovnikov, and Marcos Rigol. “From quantum chaos and eigenstate thermalization to statistical mechanics and thermodynamics”. Advances in Physics 65, 239–362 (2016).
https://doi.org/10.1080/00018732.2016.1198134
[53] 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”. Physical Review A 86 (2012).
https://doi.org/10.1103/physreva.86.052334
[54] Mark Jeansonne and Joe Foley. “Review of the exponentially modified gaussian (emg) function since 1983”. Journal of Chromatographic Science 29, 258–266 (1991).
https://doi.org/10.1093/chromsci/29.6.258
[55] Yuri Kalambet, Yuri Kozmin, Ksenia Mikhailova, Igor Nagaev, and Pavel Tikhonov. “Reconstruction of chromatographic peaks using the exponentially modified gaussian function”. Journal of Chemometrics 25, 352–356 (2011).
https://doi.org/10.1002/cem.1343
[56] Stephen J. Blundell and Katherine M. Blundell. “Concepts in Thermal Physics”. Oxford University Press. (2009).
https://doi.org/10.1093/acprof:oso/9780199562091.001.0001
[57] Elizabeth Crosson and Samuel Slezak. “Classical simulation of high temperature quantum ising models” (2020). arXiv:2002.02232.
arXiv:2002.02232
[58] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor. “Entanglement perspective on the quantum approximate optimization algorithm”. Physical Review A 106 (2022).
https://doi.org/10.1103/physreva.106.022423
[59] J M Deutsch. “Thermodynamic entropy of a many-body energy eigenstate”. New Journal of Physics 12, 075021 (2010).
https://doi.org/10.1088/1367-2630/12/7/075021
[60] J. M. Deutsch, Haibin Li, and Auditya Sharma. “Microscopic origin of thermodynamic entropy in isolated systems”. Phys. Rev. E 87, 042135 (2013).
https://doi.org/10.1103/PhysRevE.87.042135
[61] Lea F. Santos, Anatoli Polkovnikov, and Marcos Rigol. “Entropy of isolated quantum systems after a quench”. Phys. Rev. Lett. 107, 040601 (2011).
https://doi.org/10.1103/PhysRevLett.107.040601
[62] Michael A. Nielsen and Isaac L. Chuang. “Quantum computation and quantum information: 10th anniversary edition”. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667
[63] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028.
arXiv:1411.4028
[64] Milena Grifoni and Peter Hänggi. “Driven quantum tunneling”. Physics Reports 304, 229–354 (1998).
https://doi.org/10.1016/S0370-1573(98)00022-2
[65] Masahito Ueda. “Quantum equilibration, thermalization and prethermalization in ultracold atoms”. Nature Reviews Physics 2, 669–681 (2020).
https://doi.org/10.1038/s42254-020-0237-x
[66] Luca D’Alessio and Anatoli Polkovnikov. “Many-body energy localization transition in periodically driven systems”. Annals of Physics 333, 19–33 (2013).
https://doi.org/10.1016/j.aop.2013.02.011
[67] Luca D’Alessio and Marcos Rigol. “Long-time behavior of isolated periodically driven interacting lattice systems”. Physical Review X 4 (2014).
https://doi.org/10.1103/physrevx.4.041048
[68] Achilleas Lazarides, Arnab Das, and Roderich Moessner. “Equilibrium states of generic quantum systems subject to periodic driving”. Phys. Rev. E 90, 012110 (2014).
https://doi.org/10.1103/PhysRevE.90.012110
[69] Keith R. Fratus and Mark Allen Srednicki. “Eigenstate thermalization and spontaneous symmetry breaking in the one-dimensional transverse-field ising model with power-law interactions” (2016). arXiv:1611.03992.
arXiv:1611.03992
[70] Attila Felinger, Tamás Pap, and János Inczédy. “Curve fitting to asymmetrical chromatograms by the extended kalman filter in frequency domain”. Talanta 41, 1119–1126 (1994).
https://doi.org/10.1016/0039-9140(94)80081-2
[71] K. F. Riley, M. P. Hobson, and S. J. Bence. “Mathematical methods for physics and engineering: A comprehensive guide”. Cambridge University Press. (2006). 3 edition.
https://doi.org/10.1017/CBO9780511810763
[72] Brian C. Hall. “An elementary introduction to groups and representations” (2000). arXiv:math-ph/0005032.
arXiv:math-ph/0005032
[73] Michael M. Wolf, Frank Verstraete, Matthew B. Hastings, and J. Ignacio Cirac. “Area laws in quantum systems: Mutual information and correlations”. Phys. Rev. Lett. 100, 070502 (2008).
https://doi.org/10.1103/PhysRevLett.100.070502
[74] Martin Kliesch and Arnau Riera. “Properties of thermal quantum states: Locality of temperature, decay of correlations, and more”. In Fundamental Theories of Physics. Pages 481–502. Springer International Publishing (2018).
https://doi.org/10.1007/978-3-319-99046-0_20
[75] S.H. Simon. “The oxford solid state basics”. OUP Oxford. (2013).
Cited by
[1] R. Au-Yeung, B. Camino, O. Rathore, and V. Kendon, “Quantum algorithms for scientific applications”, arXiv:2312.14904, (2023).
[2] Sebastian Schulz, Dennis Willsch, and Kristel Michielsen, “Guided quantum walk”, arXiv:2308.05418, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2024-02-14 02:07:09). 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 2024-02-14 02:07:08).
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-02-13-1254/
