Förbättrad noggrannhet för travsimuleringar med Chebyshev-interpolation

Förbättrad noggrannhet för travsimuleringar med Chebyshev-interpolation

Tidsstämpel: 26 februari 2024 9:34

Gumaro Rendon1, Jacob Watkins2och Nathan Wiebe3,4

1Zapata Computing Inc., Boston, MA 02110, USA
2Facility for Rare Isotope Beams, Michigan State University, East Lansing, MI 48824, USA
3Institutionen för datavetenskap, University of Toronto, Toronto, ON M5S 2E4, Kanada
4Pacific Northwest National Laboratory, Richland, WA 99352, USA

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Kvantmetrologi gör det möjligt att mäta egenskaper hos ett kvantsystem vid den optimala Heisenberg-gränsen. Men när de relevanta kvanttillstånden förbereds med hjälp av digital Hamilton-simulering, kommer de uppkomna algoritmiska felen att orsaka avvikelser från denna grundläggande gräns. I detta arbete visar vi hur algoritmiska fel på grund av Trotterized tidsevolution kan mildras genom användning av standardpolynominterpolationstekniker. Vårt tillvägagångssätt är att extrapolera till noll Trotter-stegstorlek, som liknar noll-brusextrapoleringstekniker för att mildra hårdvarufel. Vi utför en rigorös felanalys av interpolationsmetoden för att uppskatta egenvärden och tidsutvecklade förväntningsvärden, och visar att Heisenberg-gränsen uppnås upp till polylogaritmiska faktorer i felet. Vårt arbete tyder på att noggrannheter som närmar sig de för toppmoderna simuleringsalgoritmer kan uppnås med enbart Trotter och klassiska resurser för ett antal relevanta algoritmiska uppgifter.

Förbättrad noggrannhet för Trotter-simuleringar med Chebyshev Interpolation PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: De fem första Chebyshev-polynomen. Interpolation vid Chebyshev-nollorna fungerar som ett robust schema för att lindra Trotter-fel.

[Inbäddat innehåll]

Populär sammanfattning

Kvantdatorer har potential att förbättra vår förståelse av kemi, material, kärnfysik och andra vetenskapliga discipliner genom förbättrad kvantsimulering. Det finns flera tillgängliga kvantalgoritmer för denna uppgift, och bland dessa är Trotter-formler ofta att föredra på grund av deras enkelhet och låga initiala kostnader. Tyvärr är Trotter-formler i teorin relativt felaktiga jämfört med sina nyare och mer sofistikerade konkurrenter. Även om mer beräkningstid kan hjälpa, blir denna strategi snabbt ohanterlig på dagens bullriga kvantenheter, med begränsad förmåga att utföra långa, oavbrutna beräkningar.

För att mildra fel i Trotter-simuleringar utan att öka kvantbehandlingstiden använder vi polynom för att lära oss sambandet mellan fel och stegstorlek. Genom att samla in data för olika val av stegstorlek kan vi interpolera, dvs tråda, data med ett polynom och sedan uppskatta det förväntade beteendet för mycket små stegstorlekar. Vi bevisar matematiskt att vårt tillvägagångssätt ger asymptotiska noggrannhetsförbättringar jämfört med standard Trotter för två grundläggande uppgifter: att uppskatta egenvärden och att uppskatta förväntade värden.

Vår metod är enkel och praktisk och kräver endast standardtekniker inom kvantberäkning och klassisk beräkning. Vi tror att vårt arbete ger ett starkt teoretiskt fotfäste för ytterligare undersökningar av algoritmisk felreducering. Utvidgningar av detta arbete kan ske i flera riktningar, från att eliminera artificiella antaganden i vår analys till att demonstrera förbättrade kvantsimuleringar.

► BibTeX-data

► Referenser

[1] S. Lloyd, Universal quantum simulators, Science 273 (1996) 1073.
https: / / doi.org/ 10.1126 / science.273.5278.1073

[2] M. Reiher, N. Wiebe, KM Svore, D. Wecker och M. Troyer, Belysande reaktionsmekanismer på kvantdatorer, Proceedings of the National Academy of Sciences 114 (2017) 7555.
https: / / doi.org/ 10.1073 / pnas.161915211

[3] JD Whitfield, J. Biamonte och A. Asspuru-Guzik, Simulering av elektronisk struktur hamiltonians med hjälp av kvantdatorer, Molecular Physics 109 (2011) 735.
https: / / doi.org/ 10.1080 / 00268976.2011.552441

[4] J. Lee, DW Berry, C. Gidney, WJ Huggins, JR McClean, N. Wiebe et al., Ännu effektivare kvantberäkningar av kemi genom tensorhyperkontraktion, PRX Quantum 2 (2021) 030305.
https: / / doi.org/ 10.1103 / PRXQuantum.2.030305

[5] V. von Burg, GH Low, T. Häner, DS Steiger, M. Reiher, M. Roetteler et al., Quantum computing enhanced computational catalysis, Physical Review Research 3 (2021) 033055.
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033055

[6] SP Jordan, KS Lee och J. Preskill, Quantum algorithms for quantum field theories, Science 336 (2012) 1130.
https: / / doi.org/ 10.1126 / science.1217069

[7] AF Shaw, P. Lougovski, JR Stryker och N. Wiebe, Kvantalgoritmer för simulering av schwinger-nätmodellen, Quantum 4 (2020) 306.
https:/​/​doi.org/​10.22331/​q-2020-08-10-306

[8] N. Klco, MJ Savage och JR Stryker, Su (2) icke-abelsk mätfältteori i en dimension på digitala kvantdatorer, Physical Review D 101 (2020) 074512.
https: / / doi.org/ 10.1103 / PhysRevD.101.074512

[9] AM Childs och N. Wiebe, Hamiltonsimulering med linjära kombinationer av enhetsoperationer, Quantum Info. Comput. 12 (2012) 901–924.
https: / / doi.org/ 10.26421 / QIC12.11-12-1

[10] GH Low, V. Kliuchnikov och N. Wiebe, Well-conditioned multiproduct hamiltonian simulation, arXiv:1907.11679 (2019).
https://​/​doi.org/​10.48550/​arXiv.1907.11679
arXiv: 1907.11679

[11] DW Berry, AM Childs, R. Cleve, R. Kothari och RD Somma, Simulering av hamiltonsk dynamik med en trunkerad taylor-serie, Physical review letters 114 (2015) 090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

[12] GH Low och N. Wiebe, Hamiltonsk simulering i interaktionsbilden, arXiv:1805.00675 (2018).
https://​/​doi.org/​10.48550/​arXiv.1805.00675
arXiv: 1805.00675

[13] M. Kieferová, A. Scherer och DW Berry, Simulering av dynamiken hos tidsberoende hamiltonianer med en trunkerad dysonserie, Physical Review A 99 (2019) 042314.
https: / / doi.org/ 10.1103 / PhysRevA.99.042314

[14] GH Low och IL Chuang, Hamiltonian Simulation by Qubitization, Quantum 3 (2019) 163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[15] R. Babbush, C. Gidney, DW Berry, N. Wiebe, J. McClean, A. Paler et al., Encoding electronic spectra in quantum circuits with linear t complexity, Physical Review X 8 (2018) 041015.
https: / / doi.org/ 10.1103 / PhysRevX.8.041015

[16] DW Berry, G. Ahokas, R. Cleve och BC Sanders, Effektiva kvantalgoritmer för att simulera glesa hamiltonianer, Communications in Mathematical Physics 270 (2006) 359–371.
https: / / doi.org/ 10.1007 / s00220-006-0150-x

[17] N. Wiebe, DW Berry, P. Høyer och BC Sanders, Simulering av kvantdynamik på en kvantdator, Journal of Physics A: Mathematical and Theoretical 44 (2011) 445308.
https:/​/​doi.org/​10.1088/​1751-8113/​44/​44/​445308

[18] AM Childs, Y. Su, MC Tran, N. Wiebe och S. Zhu, Theory of traver error with commutator scaling, Physical Review X 11 (2021) 011020.
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[19] J. Haah, MB Hastings, R. Kothari och GH Low, Kvantalgoritm för simulering av realtidsutveckling av hamiltonians gitter, SIAM Journal on Computing (2021) FOCS18.
https: / / doi.org/ 10.1137 / 18M12315

[20] M. Hagan och N. Wiebe, Composite quantum simulations, arXiv:2206.06409 (2022).
https:/​/​doi.org/​10.22331/​q-2023-11-14-1181
arXiv: 2206.06409

[21] GH Low, Y. Su, Y. Tong och MC Tran, Om komplexiteten i att implementera travsteg, arXiv:2211.09133 (2022).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020323
arXiv: 2211.09133

[22] GH Low och IL Chuang, Optimal Hamilton-simulering genom kvantsignalbehandling, Physical Review Letters 118 (2017).
https: / / doi.org/ 10.1103 / physrevlett.118.010501

[23] S. Endo, Q. Zhao, Y. Li, S. Benjamin och X. Yuan, Mitigating algorithmic errors in a Hamiltonian simulation, Phys. Rev. A 99 (2019) 012334.
https: / / doi.org/ 10.1103 / PhysRevA.99.012334

[24] AC Vazquez, R. Hiptmair och S. Woerner, Förbättra algoritmen för kvantlinjära system med richardson-extrapolation, ACM Transactions on Quantum Computing 3 (2022).
https: / / doi.org/ 10.1145 / 3490631

[25] AC Vazquez, DJ Egger, D. Ochsner och S. Woerner, Välkonditionerade multiproduktformler för hårdvaruvänlig Hamiltonsimulering, Quantum 7 (2023) 1067.
https:/​/​doi.org/​10.22331/​q-2023-07-25-1067

[26] M. Suzuki, General theory of fraktal path integrals with applications to many-body theorys and statistical physics, Journal of Mathematical Physics 32 (1991) 400.
https: / / doi.org/ 10.1063 / 1.529425

[27] A. Gilyén, Y. Su, GH Low och N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix aritmetics, i Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, s. 193–204, 2019 , DOI.
https: / / doi.org/ 10.1145 / 3313276.3316366

[28] C. Yi och E. Crosson, Spektralanalys av produktformler för kvantsimulering, npj Quantum Information 8 (2022) 37.
https: / / doi.org/ 10.1038 / s41534-022-00548-w

[29] A. Quarteroni, R. Sacco och F. Saleri, Numerical mathematics, vol. 37, Springer Science & Business Media (2010), 10.1007/​b98885.
https: / / doi.org/ 10.1007 / b98885

[30] F. Piazzon och M. Vianello, Stability inequalities for lebesgue constants via markov-like inequalities, Dolomites Research Notes on Approximation 11 (2018).

[31] AP de Camargo, Om den numeriska stabiliteten av Newtons formel för lagrangeinterpolation, Journal of Computational and Applied Mathematics 365 (2020) 112369.
https://doi.org/ 10.1016/j.cam.2019.112369

[32] L. Trefethen, Sex myter om polynominterpolation och kvadratur, (2011).

[33] W. Gautschi, Hur (o)stabila är vandermonde-system? asymptotisk och beräkningsanalys, i Lecture Notes in Pure and Applied Mathematics, s. 193–210, Marcel Dekker, Inc., 1990.

[34] NJ Higham, Den numeriska stabiliteten av barycentrisk lagrangeinterpolation, IMA Journal of Numerical Analysis 24 (2004) 547.
https://​/​doi.org/​10.1093/​imanum/​24.4.547

[35] JC Mason och DC Handscomb, Chebyshev polynomials, CRC press (2002), 10.1201/​9781420036114.
https: / / doi.org/ 10.1201 / 9781420036114

[36] G. Rendon, T. Izubuchi och Y. Kikuchi, Effects of cosine tapering window on quantum phase estimation, Physical Review D 106 (2022) 034503.
https: / / doi.org/ 10.1103 / PhysRevD.106.034503

[37] LN Trefethen, Approximation Theory and Approximation Practice, Extended Edition, SIAM (2019), 10.1137/​1.9781611975949.
https: / / doi.org/ 10.1137 / 1.9781611975949

[38] FL Bauer och CT Fike, Normer och uteslutningssatser, Numer. Matematik. 2 (1960) 137-141.
https: / / doi.org/ 10.1007 / BF01386217

[39] S. Blanes, F. Casas, J.-A. Oteo och J. Ros, The magnus expansion and some of its applications, Physics reports 470 (2009) 151.
https: / / doi.org/ 10.1016 / j.physrep.2008.11.001

[40] N. Klco och MJ Savage, Minimalt intrasslad tillståndsberedning av lokaliserade vågfunktioner på kvantdatorer, Physical Review A 102 (2020).
https: / ⠀ </ ⠀ <doi.org/†<10.1103 / ⠀ <physreva.102.012612

[41] JJ García-Ripoll, Quantum-inspirerade algoritmer för multivariat analys: från interpolation till partiella differentialekvationer, Quantum 5 (2021) 431.
https:/​/​doi.org/​10.22331/​q-2021-04-15-431

[42] W. Górecki, R. Demkowicz-Dobrzański, HM Wiseman och DW Berry, $pi$-korrigerad heisenberg limit, Physical review letters 124 (2020) 030501.
https: / / doi.org/ 10.1103 / PhysRevLett.124.030501

[43] D. Grinko, J. Gacon, C. Zoufal och S. Woerner, Iterativ kvantamplituduppskattning, npj Quantum Information 7 (2021) 52 [1912.05559].
https:/​/​doi.org/​10.1038/​s41534-021-00379-1
arXiv: 1912.05559

[44] N. Wiebe, D. Berry, P. Høyer och BC Sanders, Högre ordningsupplösningar av ordnade operatorexponentialer, Journal of Physics A: Mathematical and Theoretical 43 (2010) 065203.
https:/​/​doi.org/​10.1088/​1751-8113/​43/​6/​065203

[45] RA Horn och CR Johnson, Matrixanalys, Cambridge university press (2012), 10.1017/​CBO9780511810817.
https: / / doi.org/ 10.1017 / CBO9780511810817

[46] M. Chiani, D. Dardari och MK Simon, Nya exponentiella gränser och approximationer för beräkning av felsannolikhet i fädningskanaler, IEEE Transactions on Wireless Communications 2 (2003) 840.
https://​/​doi.org/​10.1109/​TWC.2003.814350

[47] JM Borwein och PB Borwein, Pi and the AGM: a study in the analytic number theory and computational complexity, Wiley-Interscience (1987).

[48] BL Higgins, DW Berry, SD Bartlett, HM Wiseman och GJ Pryde, Entanglement-free Heisenberg-limited phase estimering, Nature 450 (2007) 393.
https: / / doi.org/ 10.1038 / nature06257

[49] RB Griffiths och C.-S. Niu, Semiclassical Fourier Transform for Quantum Computation, Physical Review Letters 76 (1996) 3228.
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

[50] AY Kitaev, Quantum measurements and the abelian stabilizer problem, quant-ph/​9511026 (1995).
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: kvant-ph / 9511026

[51] DS Abrams och S. Lloyd, Quantum Algorithm Providing Exponential Speed ​​Ökning för att hitta egenvärden och egenvektorer, Physical Review Letters 83 (1999) 5162.
https: / / doi.org/ 10.1103 / PhysRevLett.83.5162

[52] J. Watkins, N. Wiebe, A. Roggero och D. Lee, Tidsberoende hamiltonisk simulering med användning av diskreta klockkonstruktioner, arXiv:2203.11353 (2022).
https://​/​doi.org/​10.48550/​arXiv.2203.11353
arXiv: 2203.11353

[53] TD Ahle, Skarpa och enkla gränser för de råa momenten i binomial- och poissonfördelningen, Statistics & Probability Letters 182 (2022) 109306.
https://​/​doi.org/​10.1016/​j.spl.2021.109306

[54] T. Rivlin, Chebyshev Polynomials, Dover Books on Mathematics, Dover Publications (2020).

Citerad av

[1] Dean Lee, "Kvanttekniker för egenvärdeproblem", European Physical Journal A 59 11, 275 (2023).

[2] Tatsuhiko N. Ikeda, Hideki Kono och Keisuke Fujii, "Trotter24: A precision-garanteed adaptive stepsize Trotterization for Hamiltonian simulations", arXiv: 2307.05406, (2023).

[3] Hans Hon Sang Chan, Richard Meister, Matthew L. Goh och Bálint Koczor, "Algorithmic Shadow Spectroscopy", arXiv: 2212.11036, (2022).

[4] Sergiy Zhuk, Niall Robertson och Sergey Bravyi, "Trotter error bounds and dynamic multi-product formles for Hamiltonian simulation", arXiv: 2306.12569, (2023).

[5] Zhicheng Zhang, Qisheng Wang och Mingsheng Ying, "Parallell Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).

[6] Lea M. Trenkwalder, Eleanor Scerri, Thomas E. O'Brien och Vedran Dunjko, "Kompilering av produktformel Hamiltonsimulering via förstärkningsinlärning", arXiv: 2311.04285, (2023).

[7] Gumaro Rendon och Peter D. Johnson, "Low-depth Gaussian State Energy Estimation", arXiv: 2309.16790, (2023).

[8] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv: 2312.00696, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-02-27 02:40:25). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2024-02-27 02:40:24).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal