{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T07:39:24Z","timestamp":1747208364807,"version":"3.40.5"},"reference-count":56,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Evolutions of local Hamiltonians in short times are expected to remain local and thus limited. In this paper, we validate this intuition by proving some limitations on short-time evolutions of local time-dependent Hamiltonians. We show that the distribution of the measurement output of short-time (at most logarithmic) evolutions of local Hamiltonians are <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>c<\/mml:mi><mml:mi>o<\/mml:mi><mml:mi>n<\/mml:mi><mml:mi>c<\/mml:mi><mml:mi>e<\/mml:mi><mml:mi>n<\/mml:mi><mml:mi>t<\/mml:mi><mml:mi>r<\/mml:mi><mml:mi>a<\/mml:mi><mml:mi>t<\/mml:mi><mml:mi>e<\/mml:mi><mml:mi>d<\/mml:mi><\/mml:math> and satisfy an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">isoperimetric inequality<\/mml:mtext><\/mml:mrow><\/mml:math>. To showcase explicit applications of our results, we study the <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>M<\/mml:mi><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mstyle mathsize=\"0.85em\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>A<\/mml:mi><mml:mi>X<\/mml:mi><\/mml:mrow><\/mml:mstyle><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>C<\/mml:mi><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mstyle mathsize=\"0.85em\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>U<\/mml:mi><mml:mi>T<\/mml:mi><\/mml:mrow><\/mml:mstyle><\/mml:math> problem and conclude that quantum annealing needs at least a run-time that scales logarithmically in the problem size to beat classical algorithms on <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>M<\/mml:mi><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mstyle mathsize=\"0.85em\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>A<\/mml:mi><mml:mi>X<\/mml:mi><\/mml:mrow><\/mml:mstyle><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>C<\/mml:mi><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mstyle mathsize=\"0.85em\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>U<\/mml:mi><mml:mi>T<\/mml:mi><\/mml:mrow><\/mml:mstyle><\/mml:math>. To establish our results, we also prove a Lieb-Robinson bound that works for time-dependent Hamiltonians which might be of independent interest.<\/jats:p>","DOI":"10.22331\/q-2022-06-27-744","type":"journal-article","created":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T13:39:02Z","timestamp":1656337142000},"page":"744","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Limits of Short-Time Evolution of Local Hamiltonians"],"prefix":"10.22331","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1818-5037","authenticated-orcid":false,"given":"Ali Hamed","family":"Moosavian","sequence":"first","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seyed Sajad","family":"Kahani","sequence":"additional","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3588-4662","authenticated-orcid":false,"given":"Salman","family":"Beigi","sequence":"additional","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"T. Kadowaki and H. Nishimori. Quantum annealing in the transverse Ising model. Physical Review E 58, 5355\u20135363 (1998).","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"1","doi-asserted-by":"publisher","unstructured":"E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. Quantum Computation by Adiabatic Evolution. arXiv:0001106 [quant-ph] (2000).","DOI":"10.48550\/arXiv.quant-ph\/0001106"},{"key":"2","doi-asserted-by":"publisher","unstructured":"T. Kato. On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan 5, 435\u2013439 (1950).","DOI":"10.1143\/JPSJ.5.435"},{"key":"3","doi-asserted-by":"publisher","unstructured":"M. Born and V. Fock. Beweis des adiabatensatzes. Zeitschrift f\u00fcr Physik 51, 165\u2013180 (1928).","DOI":"10.1007\/BF01343193"},{"key":"4","doi-asserted-by":"publisher","unstructured":"T. Albash and D. A. Lidar. Adiabatic quantum computation. Reviews of Modern Physics 90, 015002 (2018).","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"5","doi-asserted-by":"publisher","unstructured":"I. Hen and F. M. Spedalieri. Quantum Annealing for Constrained Optimization. Physical Review Applied 5, 034007 (2016).","DOI":"10.1103\/PhysRevApplied.5.034007"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. Puri, C. K. Andersen, A. L. Grimsmo, and A. Blais. Quantum annealing with all-to-all connected nonlinear oscillators. Nature Communications 8, 15785 (2017).","DOI":"10.1038\/ncomms15785"},{"key":"7","doi-asserted-by":"publisher","unstructured":"W. Lechner, P. Hauke, and P. Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances 1, e1500838 (2015).","DOI":"10.1126\/sciadv.1500838"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais. Quantum Annealing for Prime Factorization. Scientific Reports 8, 17667 (2018).","DOI":"10.1038\/s41598-018-36058-z"},{"key":"9","doi-asserted-by":"publisher","unstructured":"R. Y. Li, R. Di Felice, R. Rohs, and D. A. Lidar. Quantum annealing versus classical machine learning applied to a simplified computational biology problem. NPJ quantum information 4, 1\u201310 (2018).","DOI":"10.1038\/s41534-018-0060-8"},{"key":"10","doi-asserted-by":"publisher","unstructured":"L. Stella, G. E. Santoro, and E. Tosatti. Optimization by quantum annealing: Lessons from simple cases. Physical Review B 72, 014303 (2005).","DOI":"10.1103\/PhysRevB.72.014303"},{"key":"11","doi-asserted-by":"publisher","unstructured":"O. Titiloye and A. Crispin. Quantum annealing of the graph coloring problem. Discrete Optimization 8, 376\u2013384 (2011).","DOI":"10.1016\/j.disopt.2010.12.001"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. Mott, J. Job, J.-R. Vlimant, D. Lidar, and M. Spiropulu. Solving a Higgs optimization problem with quantum annealing for machine learning. Nature 550, 375\u2013379 (2017).","DOI":"10.1038\/nature24047"},{"key":"13","doi-asserted-by":"publisher","unstructured":"K. L. Pudenz, T. Albash, and D. A Lidar. Quantum annealing correction for random Ising problems. Physical Review A 91, 042302 (2015).","DOI":"10.1103\/PhysRevA.91.042302"},{"key":"14","doi-asserted-by":"publisher","unstructured":"A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik. Finding low-energy conformations of lattice protein models by quantum annealing. Scientific reports 2, 571 (2012).","DOI":"10.1038\/srep00571"},{"key":"15","doi-asserted-by":"publisher","unstructured":"K. L. Pudenz, T. Albash, and D. A Lidar. Error-corrected quantum annealing with hundreds of qubits. Nature communications 5, 1\u201310 (2014).","DOI":"10.1038\/ncomms4243"},{"key":"16","doi-asserted-by":"publisher","unstructured":"R. Marto\u0148\u00e1k, G. E. Santoro, and E. Tosatti. Quantum annealing of the traveling-salesman problem. Physical Review E 70, 057701 (2004).","DOI":"10.1103\/PhysRevE.70.057701"},{"key":"17","doi-asserted-by":"publisher","unstructured":"S. H. Adachi and M. P. Henderson. Application of quantum annealing to training of deep neural networks. arXiv:1510.06356 [quant-ph] (2015).","DOI":"10.48550\/arXiv.1510.06356"},{"key":"18","doi-asserted-by":"publisher","unstructured":"M. W Johnson, et al. Quantum annealing with manufactured spins. Nature 473, 194\u2013198 (2011).","DOI":"10.1038\/nature10012"},{"key":"19","doi-asserted-by":"publisher","unstructured":"S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor, and D. A. Lidar. Experimental signature of programmable quantum annealing. Nature communications 4, 1\u20138 (2013).","DOI":"10.1038\/ncomms3067"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. D. King, et al. Coherent quantum annealing in a programmable 2000-qubit Ising chain. arXiv:2202.05847 [quant-ph] (2022).","DOI":"10.48550\/arXiv.2202.05847"},{"key":"21","doi-asserted-by":"publisher","unstructured":"B. Foxen, et al. Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms. Physical Review Letters 125, 120504 (2020).","DOI":"10.1103\/PhysRevLett.125.120504"},{"key":"22","doi-asserted-by":"publisher","unstructured":"K. Wright, et al. Benchmarking an 11-qubit quantum computer. Nature communications 10, 1\u20136 (2019).","DOI":"10.1038\/s41467-019-13534-2"},{"key":"23","doi-asserted-by":"publisher","unstructured":"E. J. Crosson and D. A. Lidar. Prospects for quantum enhancement with diabatic quantum annealing. Nature Reviews Physics 3, 466\u2013489 (2021).","DOI":"10.1038\/s42254-021-00313-6"},{"key":"24","doi-asserted-by":"publisher","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph] (2014).","DOI":"10.48550\/arXiv.1411.4028"},{"key":"25","doi-asserted-by":"publisher","unstructured":"E. Farhi, D. Gamarnik, and S. Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples. arXiv:2005.08747 [quant-ph] (2020).","DOI":"10.48550\/arXiv.2005.08747"},{"key":"26","doi-asserted-by":"publisher","unstructured":"E. Farhi, D. Gamarnik, and S. Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv:2004.09002 [quant-ph] (2020).","DOI":"10.48550\/arXiv.2004.09002"},{"key":"27","doi-asserted-by":"publisher","unstructured":"S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. Obstacles to Variational Quantum Optimization from Symmetry Protection. Physical Review Letters 125, 260505 (2020).","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"28","doi-asserted-by":"publisher","unstructured":"S. Bravyi, D. Gosset, and R. Movassagh. Classical algorithms for quantum mean values. Nature Physics 17, 337\u2013341 (2021).","DOI":"10.1038\/s41567-020-01109-8"},{"key":"29","doi-asserted-by":"publisher","unstructured":"S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. Hybrid quantum-classical algorithms for approximate graph coloring. Quantum 6, 678 (2022).","DOI":"10.22331\/q-2022-03-30-678"},{"key":"30","doi-asserted-by":"publisher","unstructured":"L. Eldar and A. W. Harrow. Local Hamiltonians Whose Ground States are Hard to Approximate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 427\u2013438 (2017).","DOI":"10.1109\/FOCS.2017.46"},{"key":"31","doi-asserted-by":"publisher","unstructured":"L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov. Optimal Protocols in Quantum Annealing and Quantum Approximate Optimization Algorithm Problems. Physical Review Letters 126, 070505 (2021).","DOI":"10.1103\/PhysRevLett.126.070505"},{"key":"32","doi-asserted-by":"publisher","unstructured":"L. T. Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov, and A. V. Gorshkov. Behavior of Analog Quantum Algorithms. arXiv:2107.01218 [quant-ph] (2021).","DOI":"10.48550\/arXiv.2107.01218"},{"key":"33","doi-asserted-by":"publisher","unstructured":"L. C. Venuti, D. D&apos;Alessandro, and D. A. Lidar. Optimal Control for Quantum Optimization of Closed and Open Systems. Physical Review Applied 16, 054023 (2021).","DOI":"10.1103\/PhysRevApplied.16.054023"},{"key":"34","doi-asserted-by":"publisher","unstructured":"A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. Theory of Trotter Error with Commutator Scaling. Physical Review X 11, 011020 (2021).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"35","doi-asserted-by":"publisher","unstructured":"B. Nachtergaele, Y. Ogata, and R. Sims. Propagation of correlations in quantum lattice systems. Journal of Statistical Physics 124, 1\u201313 (2006).","DOI":"10.1007\/s10955-006-9143-6"},{"key":"36","doi-asserted-by":"publisher","unstructured":"B. Nachtergaele and R. Sims. Lieb-Robinson bounds in quantum many-body physics. Contemporary Mathematics 529, 141\u2013176 (2010).","DOI":"10.1090\/conm\/529\/10429"},{"key":"37","doi-asserted-by":"publisher","unstructured":"S. Bravyi, M. B. Hastings, and F. Verstraete. Lieb-robinson bounds and the generation of correlations and topological quantum order. Physical Review Letters 97, 050401 (2006).","DOI":"10.1103\/PhysRevLett.97.050401"},{"key":"38","doi-asserted-by":"publisher","unstructured":"C.-F. Chen and A. Lucas. Operator growth bounds from graph theory. Communications in Mathematical Physics 385, pages1273\u20131323 (2021).","DOI":"10.1007\/s00220-021-04151-6"},{"key":"39","doi-asserted-by":"publisher","unstructured":"E.H. Lieb and D.W. Robinson. The finite group velocity of quantum spin systems. Communications in Mathematical Physics 28, 251\u2013257 (1972).","DOI":"10.1007\/BF01645779"},{"key":"40","doi-asserted-by":"publisher","unstructured":"J. Haah, M. B. Hastings, R. Kothari, and G. H. Low. Quantum algorithm for simulating real time evolution of lattice Hamiltonians. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350\u2013360 (2018).","DOI":"10.1109\/FOCS.2018.00041"},{"key":"41","doi-asserted-by":"publisher","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica 8, 261\u2013277 (1988).","DOI":"10.1007\/BF02126799"},{"key":"42","doi-asserted-by":"publisher","unstructured":"B. Mohar. Isoperimetric numbers of graphs. Journal of Combinatorial Theory, Series B 47, 274\u2013291 (1989).","DOI":"10.1016\/0095-8956(89)90029-4"},{"key":"43","doi-asserted-by":"publisher","unstructured":"A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358\u20131377 (2015).","DOI":"10.1109\/FOCS.2015.87"},{"key":"44","doi-asserted-by":"publisher","unstructured":"A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. SIAM Journal on Computing 47, 2488\u20132509 (2018).","DOI":"10.1137\/16M106176X"},{"key":"45","doi-asserted-by":"publisher","unstructured":"C. Hall, D. Puder, and W. F. Sawin. Ramanujan coverings of graphs. Advances in Mathematics 323, 367\u2013410 (2018).","DOI":"10.1016\/j.aim.2017.10.042"},{"key":"46","doi-asserted-by":"publisher","unstructured":"M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42, 1115\u20131145 (1995).","DOI":"10.1145\/227683.227684"},{"key":"47","doi-asserted-by":"publisher","unstructured":"R. D. Somma, D. Nagaj, and M. Kieferov\u00e1. Quantum Speedup by Quantum Annealing. Physical Review Letters 109, 050501 (2012).","DOI":"10.1103\/PhysRevLett.109.050501"},{"key":"48","doi-asserted-by":"publisher","unstructured":"M. B. Hastings. The Power of Adiabatic Quantum Computation with No Sign Problem. Quantum 5, 597 (2021).","DOI":"10.22331\/q-2021-12-06-597"},{"key":"49","doi-asserted-by":"publisher","unstructured":"A. Gily\u00e9n, M. B. Hastings, and U. Vazirani. (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357\u20131369 (2021).","DOI":"10.1145\/3406325.3451060"},{"key":"50","doi-asserted-by":"publisher","unstructured":"R. Bhatia. Matrix analysis. Graduate Texts in Mathematics. Springer New York (1996).","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"51","doi-asserted-by":"publisher","unstructured":"R. Bhatia. Positive definite matrices. Princeton University Press, (2007).","DOI":"10.1515\/9781400827787"},{"key":"52","doi-asserted-by":"publisher","unstructured":"B.D. McKay, N.C. Wormald, and B. Wysocka. Short Cycles in Random Regular Graphs. The Electronic Journal of Combinatorics 11, 1\u201312 (2004).","DOI":"10.37236\/1819"},{"key":"53","doi-asserted-by":"publisher","unstructured":"F. Kardo\u0161, D. Kr\u00e1l, and J. Volec. Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs. Random Structures & Algorithms 41, 506\u2013520 (2012).","DOI":"10.1002\/rsa.20471"},{"key":"54","doi-asserted-by":"publisher","unstructured":"D. Coppersmith, D. Gamarnik, M.T. Hajiaghayi, and G.B. Sorkin. Random MAX SAT, random MAX CUT, and their phase transitions. Random Structures and Algorithms 24, 502\u2013545 (2004).","DOI":"10.1002\/rsa.20015"},{"key":"55","doi-asserted-by":"publisher","unstructured":"A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs. Annals of Probability 45, 1190\u20131217 (2017).","DOI":"10.1214\/15-AOP1084"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-27-744\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T13:39:06Z","timestamp":1656337146000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-27-744\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,27]]},"references-count":56,"URL":"https:\/\/doi.org\/10.22331\/q-2022-06-27-744","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2022,6,27]]},"article-number":"744"}}