Forbedret nøyaktighet for travsimuleringer ved bruk av Chebyshev-interpolasjon

Forbedret nøyaktighet for travsimuleringer ved bruk av Chebyshev-interpolasjon

Tidsstempel: 26. februar 2024 9:34

Gumaro Rendon1, Jacob Watkins2, og Nathan Wiebe3,4

1Zapata Computing Inc., Boston, MA 02110, USA
2Fasilitet for Rare Isotope Beams, Michigan State University, East Lansing, MI 48824, USA
3Institutt for informatikk, University of Toronto, Toronto, ON M5S 2E4, Canada
4Pacific Northwest National Laboratory, Richland, WA 99352, USA

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Kvantemetrologi gjør det mulig å måle egenskapene til et kvantesystem ved den optimale Heisenberg-grensen. Men når de relevante kvantetilstandene er forberedt ved bruk av digital Hamilton-simulering, vil de påløpte algoritmiske feilene forårsake avvik fra denne grunnleggende grensen. I dette arbeidet viser vi hvordan algoritmiske feil på grunn av Trotterized tidsevolusjon kan reduseres ved bruk av standard polynomial interpolasjonsteknikker. Vår tilnærming er å ekstrapolere til null Trotter-trinnstørrelse, i likhet med null-støy-ekstrapolasjonsteknikker for å redusere maskinvarefeil. Vi utfører en streng feilanalyse av interpolasjonstilnærmingen for å estimere egenverdier og tidsutviklede forventningsverdier, og viser at Heisenberg-grensen oppnås opp til polylogaritmiske faktorer i feilen. Vårt arbeid antyder at nøyaktigheter som nærmer seg de til toppmoderne simuleringsalgoritmer kan oppnås ved å bruke Trotter og klassiske ressurser alene for en rekke relevante algoritmiske oppgaver.

Forbedret nøyaktighet for travsimuleringer ved bruk av Chebyshev Interpolation PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Utvalgt bilde: De fem første Chebyshev-polynomene. Interpolering ved Chebyshev-nullene fungerer som et robust opplegg for å redusere Trotter-feil.

[Innebygd innhold]

Populært sammendrag

Kvantedatamaskiner har potensial til å forbedre vår forståelse av kjemi, materialer, kjernefysikk og andre vitenskapelige disipliner gjennom forbedret kvantesimulering. Det er flere tilgjengelige kvantealgoritmer for denne oppgaven, og blant disse foretrekkes ofte Trotter-formler på grunn av deres enkelhet og lave forhåndskostnader. Dessverre er Trotter-formler i teorien relativt unøyaktige sammenlignet med deres nyere og mer sofistikerte konkurrenter. Selv om mer beregningstid kan hjelpe, blir denne strategien raskt uhåndterlig på dagens støyende kvanteenheter, med begrenset evne til å utføre lange, uavbrutt beregninger.

For å redusere feil i Trotter-simuleringer uten å øke kvantebehandlingstiden, bruker vi polynomer for å lære forholdet mellom feil og trinnstørrelse. Ved å samle inn data for ulike valg av trinnstørrelse, kan vi interpolere, dvs. tråde, dataene med et polynom, og deretter estimere forventet oppførsel for svært små trinnstørrelser. Vi beviser matematisk at vår tilnærming gir asymptotiske nøyaktighetsforbedringer i forhold til standard Trotter for to grunnleggende oppgaver: estimering av egenverdier og estimering av forventningsverdier.

Metoden vår er enkel og praktisk, og krever kun standardteknikker innen kvanteberegning og klassisk beregning. Vi mener arbeidet vårt gir et sterkt teoretisk fotfeste for videre undersøkelser av algoritmisk feilredusering. Utvidelser av dette arbeidet kan skje i flere retninger, fra å eliminere kunstige antagelser i vår analyse til å demonstrere forbedrede kvantesimuleringer.

► BibTeX-data

► Referanser

[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 og M. Troyer, Klargjøring av reaksjonsmekanismer på kvantedatamaskiner, Proceedings of the National Academy of Sciences 114 (2017) 7555.
https: / / doi.org/ 10.1073 / pnas.161915211

[3] JD Whitfield, J. Biamonte og A. Aspuru-Guzik, Simulering av elektronisk struktur hamiltonians ved bruk av kvantedatamaskiner, 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., Enda mer effektive kvanteberegninger av kjemi gjennom tensorhyperkontraksjon, 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 og 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 og N. Wiebe, Kvantealgoritmer for simulering av gitter-schwinger-modellen, Quantum 4 (2020) 306.
https:/​/​doi.org/​10.22331/​q-2020-08-10-306

[8] N. Klco, MJ Savage og JR Stryker, Su (2) ikke-abelsk målefeltteori i én dimensjon på digitale kvantedatamaskiner, Physical Review D 101 (2020) 074512.
https: / / doi.org/ 10.1103 / PhysRevD.101.074512

[9] AM Childs og N. Wiebe, Hamiltonsk simulering ved bruk av lineære kombinasjoner av enhetlige operasjoner, Quantum Info. Comput. 12 (2012) 901–924.
https: / / doi.org/ 10.26421 / QIC12.11-12-1

[10] GH Low, V. Kliuchnikov og 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 og RD Somma, Simulering av hamiltonsk dynamikk med en trunkert taylor-serie, Physical review letters 114 (2015) 090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

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

[13] M. Kieferová, A. Scherer og DW Berry, Simulering av dynamikken til tidsavhengige hamiltonianere med en trunkert dyson-serie, Physical Review A 99 (2019) 042314.
https: / / doi.org/ 10.1103 / PhysRevA.99.042314

[14] GH Low og 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 og BC Sanders, Effektive kvantealgoritmer for simulering av sparsomme hamiltonianere, 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 og BC Sanders, Simulering av kvantedynamikk på en kvantedatamaskin, 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 og 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 og GH Low, Kvantealgoritme for simulering av sanntidsevolusjon av gitterhamiltonians, SIAM Journal on Computing (2021) FOCS18.
https: / / doi.org/ 10.1137 / 18M12315

[20] M. Hagan og 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 og MC Tran, Om kompleksiteten ved å implementere travsteg, arXiv:2211.09133 (2022).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020323
arxiv: 2211.09133

[22] GH Low og IL Chuang, Optimal Hamiltonsk simulering ved kvantesignalbehandling, Physical Review Letters 118 (2017).
https: / / doi.org/ 10.1103 / physrevlett.118.010501

[23] S. Endo, Q. Zhao, Y. Li, S. Benjamin og X. Yuan, Reduserende algoritmiske feil i en hamiltonsk simulering, Phys. Rev. A 99 (2019) 012334.
https: / / doi.org/ 10.1103 / PhysRevA.99.012334

[24] AC Vazquez, R. Hiptmair og S. Woerner, Enhancing the quantum linear systems algorithm using richardson extrapolation, ACM Transactions on Quantum Computing 3 (2022).
https: / / doi.org/ 10.1145 / 3490631

[25] AC Vazquez, DJ Egger, D. Ochsner og S. Woerner, Velkondisjonerte multiproduktformler for maskinvarevennlig hamiltonsk simulering, Quantum 7 (2023) 1067.
https:/​/​doi.org/​10.22331/​q-2023-07-25-1067

[26] M. Suzuki, Generell teori om fraktale baneintegraler med anvendelser til mangekroppsteorier og statistisk fysikk, Journal of Mathematical Physics 32 (1991) 400.
https: / / doi.org/ 10.1063 / 1.529425

[27] A. Gilyén, Y. Su, GH Low og N. Wiebe, Quantum singular value transformation and beyond: eksponentielle forbedringer for kvantematrisearitmetikk, i Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, s. 193–204, 2019 , GJØR JEG.
https: / / doi.org/ 10.1145 / 3313276.3316366

[28] C. Yi og E. Crosson, Spektralanalyse av produktformler for kvantesimulering, npj Quantum Information 8 (2022) 37.
https: / / doi.org/ 10.1038 / s41534-022-00548-w

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

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

[31] AP de Camargo, Om den numeriske stabiliteten til Newtons formel for lagrange-interpolering, Journal of Computational and Applied Mathematics 365 (2020) 112369.
https://doi.org/ 10.1016/j.cam.2019.112369

[32] L. Trefethen, Seks myter om polynominterpolasjon og kvadratur, (2011).

[33] W. Gautschi, Hvor (u)stabile er vandermonde-systemer? asymptotisk og beregningsmessig analyse, i Lecture Notes in Pure and Applied Mathematics, s. 193–210, Marcel Dekker, Inc., 1990.

[34] NJ Higham, Den numeriske stabiliteten til barysentrisk lagrange-interpolasjon, IMA Journal of Numerical Analysis 24 (2004) 547.
https://​/​doi.org/​10.1093/​imanum/​24.4.547

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

[36] G. Rendon, T. Izubuchi og Y. Kikuchi, Effects of cosinus tapering window on quantum phase estimering, 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 og CT Fike, normer og eksklusjonsteoremer, tall. Matte. 2 (1960) 137-141.
https: / / doi.org/ 10.1007 / BF01386217

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

[40] N. Klco og MJ Savage, Minimalt entangled state preparering av lokaliserte bølgefunksjoner på kvantedatamaskiner, Physical Review A 102 (2020).
https: / / doi.org/ 10.1103 / physreva.102.012612

[41] JJ García-Ripoll, Quantum-inspirerte algoritmer for multivariat analyse: fra interpolasjon til partielle differensialligninger, Quantum 5 (2021) 431.
https:/​/​doi.org/​10.22331/​q-2021-04-15-431

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

[43] D. Grinko, J. Gacon, C. Zoufal og S. Woerner, Iterativ kvanteamplitudeestimering, 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 og BC Sanders, Higher order decompositions of ordered operator exponentials, Journal of Physics A: Mathematical and Theoretical 43 (2010) 065203.
https:/​/​doi.org/​10.1088/​1751-8113/​43/​6/​065203

[45] RA Horn og CR Johnson, Matriseanalyse, Cambridge University Press (2012), 10.1017/​CBO9780511810817.
https: / / doi.org/ 10.1017 / CBO9780511810817

[46] M. Chiani, D. Dardari og MK Simon, Nye eksponentielle grenser og tilnærminger for beregning av feilsannsynlighet i fadingkanaler, IEEE Transactions on Wireless Communications 2 (2003) 840.
https://​/​doi.org/​10.1109/​TWC.2003.814350

[47] JM Borwein og 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 og GJ Pryde, Entanglement-free Heisenberg-limited phase estimering, Nature 450 (2007) 393.
https: / / doi.org/ 10.1038 / nature06257

[49] RB Griffiths og C.-S. Niu, Semiklassisk 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: Quant-ph / 9511026

[51] DS Abrams og S. Lloyd, Quantum Algorithm Providing Eksponentiell hastighetsøkning for å finne egenverdier og egenvektorer, Physical Review Letters 83 (1999) 5162.
https: / / doi.org/ 10.1103 / PhysRevLett.83.5162

[52] J. Watkins, N. Wiebe, A. Roggero og D. Lee, Tidsavhengig hamiltonsk simulering ved bruk av diskrete klokkekonstruksjoner, arXiv:2203.11353 (2022).
https://​/​doi.org/​10.48550/​arXiv.2203.11353
arxiv: 2203.11353

[53] TD Ahle, Skarpe og enkle grenser for de rå momentene til binomial- og giftfordelingen, 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).

Sitert av

[1] Dean Lee, "Kvanteteknikker for egenverdiproblemer", European Physical Journal A 59 11, 275 (2023).

[2] Tatsuhiko N. Ikeda, Hideki Kono og Keisuke Fujii, "Trotter24: En presisjonsgarantert adaptiv stepsize Trotterization for Hamiltonian simulations", arxiv: 2307.05406, (2023).

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

[4] Sergiy Zhuk, Niall Robertson og Sergey Bravyi, "Trotter-feilgrenser og dynamiske flerproduktformler for Hamilton-simulering", arxiv: 2306.12569, (2023).

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

[6] Lea M. Trenkwalder, Eleanor Scerri, Thomas E. O'Brien og Vedran Dunjko, "Samstilling av produktformel Hamilton-simulering via forsterkningslæring", arxiv: 2311.04285, (2023).

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

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

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2024-02-27 02:40:25). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2024-02-27 02:40:24).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal