Forbedret nøjagtighed for travsimuleringer ved hjælp af Chebyshev-interpolation

Genudgivet af Platon

Abonnenter: 0

Gumaro Rendon¹, Jacob Watkins², og Nathan Wiebe^3,4

¹Zapata Computing Inc., Boston, MA 02110, USA
²Facilitet for Rare Isotope Beams, Michigan State University, East Lansing, MI 48824, USA
³Department of Computer Science, University of Toronto, Toronto, ON M5S 2E4, Canada
⁴Pacific Northwest National Laboratory, Richland, WA 99352, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Kvantemetrologi giver mulighed for at måle egenskaber af et kvantesystem ved den optimale Heisenberg-grænse. Men når de relevante kvantetilstande er forberedt ved hjælp af digital Hamilton-simulering, vil de påløbne algoritmiske fejl forårsage afvigelser fra denne grundlæggende grænse. I dette arbejde viser vi, hvordan algoritmiske fejl på grund af Trotterized tidsevolution kan afbødes ved brug af standard polynomielle interpolationsteknikker. Vores tilgang er at ekstrapolere til nul Trotter-trinstørrelse, beslægtet med nul-støj-ekstrapolationsteknikker til at afbøde hardwarefejl. Vi udfører en streng fejlanalyse af interpolationstilgangen til estimering af egenværdier og tidsudviklede forventningsværdier og viser, at Heisenberg-grænsen er opnået op til polylogaritmiske faktorer i fejlen. Vores arbejde tyder på, at nøjagtigheder, der nærmer sig dem for avancerede simuleringsalgoritmer, kan opnås ved at bruge Trotter og klassiske ressourcer alene til en række relevante algoritmiske opgaver.

Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Udvalgt billede: De første fem Chebyshev polynomier. Interpolation ved Chebyshev-nullerne tjener som et robust skema til reduktion af travfejl.

[Indlejret indhold]

Populært resumé

Kvantecomputere har potentialet til at forbedre vores forståelse af kemi, materialer, kernefysik og andre videnskabelige discipliner gennem forbedret kvantesimulering. Der er flere tilgængelige kvantealgoritmer til denne opgave, og blandt disse foretrækkes Trotter-formler ofte på grund af deres enkelhed og lave forhåndsomkostninger. Trotter-formler er desværre i teorien relativt unøjagtige sammenlignet med deres nyere og mere sofistikerede konkurrenter. Selvom mere beregningstid kan hjælpe, bliver denne strategi hurtigt uoverskuelig på de støjende kvanteenheder i dag, med begrænset evne til at udføre lange, uafbrudte beregninger.

For at afbøde fejl i Trotter-simuleringer uden at øge kvantebehandlingstiden, bruger vi polynomier til at lære forholdet mellem fejl og trinstørrelse. Ved at indsamle data for forskellige valg af trinstørrelse, kan vi interpolere, dvs. tråde, dataene med et polynomium og derefter estimere den forventede adfærd for meget små trinstørrelser. Vi beviser matematisk, at vores tilgang giver asymptotiske nøjagtighedsforbedringer i forhold til standard Trotter til to grundlæggende opgaver: estimering af egenværdier og estimering af forventningsværdier.

Vores metode er enkel og praktisk og kræver kun standardteknikker inden for kvante- og klassisk beregning. Vi mener, at vores arbejde giver et stærkt teoretisk fodfæste til yderligere undersøgelser af algoritmisk fejlreduktion. Udvidelser af dette arbejde kan forekomme i flere retninger, fra at eliminere kunstige antagelser i vores analyse til at demonstrere forbedrede kvantesimuleringer.

► BibTeX-data

@article{Rendon2024forbedret nøjagtighed, doi = {10.22331/q-2024-02-26-1266}, url = {https://doi.org/10.22331/q-2024-02-26-1266}, title = {Forbedret {A}nøjagtighed for {T}rotter {S}imuleringer {U}sing {C}hebyshev {I}nterpolation}, forfatter = {Rendon, Gumaro og Watkins, Jacob og Wiebe, Nathan}, journal = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F{“{o}}rderung des Open Access Publizierens in the Quantenwissenschaften}}, volumen = {8}, sider = {1266}, måned = feb, år = {2024} }

► Referencer

[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, Belysning af reaktionsmekanismer på kvantecomputere, 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 af elektronisk struktur hamiltonians ved hjælp af kvantecomputere, 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., Endnu mere effektive kvanteberegninger af kemi gennem 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 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 til simulering af 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 dimension på digitale kvantecomputere, Physical Review D 101 (2020) 074512.
https:///doi.org/10.1103/PhysRevD.101.074512

[9] AM Childs og N. Wiebe, Hamiltonsk simulering ved hjælp af lineære kombinationer af enhedsoperationer, 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 af hamiltonsk dynamik med en trunkeret 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 interaktionsbilledet, arXiv:1805.00675 (2018).
https:///doi.org/10.48550/arXiv.1805.00675
arXiv: 1805.00675

[13] M. Kieferová, A. Scherer og DW Berry, Simulering af dynamikken i tidsafhængige hamiltonianere med en trunkeret 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., Kodning af elektroniske spektre i kvantekredsløb med lineær t-kompleksitet, 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 til simulering af 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 af kvantedynamik på en kvantecomputer, 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, Teori om travfejl med kommutatorskalering, 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 til simulering af realtidsudvikling af lattice hamiltonians, 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 at implementere travskridt, arXiv:2211.09133 (2022).
https:///doi.org/10.1103/PRXQuantum.4.020323
arXiv: 2211.09133

[22] GH Low og IL Chuang, Optimal Hamilton-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, Afhjælpning af algoritmiske fejl 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 algoritme ved hjælp af richardson ekstrapolation, ACM Transactions on Quantum Computing 3 (2022).
https:///doi.org/10.1145/3490631

[25] AC Vazquez, DJ Egger, D. Ochsner og S. Woerner, Velkonditionerede multiproduktformler til hardwarevenlig Hamilton-simulering, Quantum 7 (2023) 1067.
https://doi.org/10.22331/q-2023-07-25-1067

[26] M. Suzuki, Generel teori om fraktale sti-integraler med anvendelser til mange-legeme-teorier og statistisk fysik, 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 kvantematrixaritmetik, 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 og E. Crosson, Spektral analyse af produktformler til 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 matematik, vol. 37, Springer Science & Business Media (2010), 10.1007/b98885.
https://doi.org/10.1007/b98885

[30] F. Piazzon og M. Vianello, Stabilitetsuligheder for lebesgue-konstanter via markov-lignende uligheder, Dolomites Research Notes on Approximation 11 (2018).

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

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

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

[34] NJ Higham, Den numeriske stabilitet af barycentrisk lagrange-interpolation, IMA Journal of Numerical Analysis 24 (2004) 547.
https:///doi.org/10.1093/imanum/24.4.547

[35] JC Mason og DC Handscomb, Chebyshev-polynomier, CRC-presse (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 udelukkelsesteoremer, Numer. Matematik. 2 (1960) 137-141.
https:///doi.org/10.1007/BF01386217

[39] S. Blanes, F. Casas, J.-A. Oteo og J. Ros, Magnus-udvidelsen og nogle af dens anvendelser, Physics-rapporter 470 (2009) 151.
https:///doi.org/10.1016/j.physrep.2008.11.001

[40] N. Klco og MJ Savage, Minimalt entangled state-forberedelse af lokaliserede bølgefunktioner på kvantecomputere, Physical Review A 102 (2020).
https:///doi.org/10.1103/physreva.102.012612

[41] JJ García-Ripoll, Kvante-inspirerede algoritmer til multivariat analyse: fra interpolation til partielle differentialligninger, 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$-korrigeret heisenberg-grænse, 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, Højere ordens dekomponeringer af ordnede operatoreksponentialer, 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, Matrixanalyse, Cambridge University Press (2012), 10.1017/CBO9780511810817.
https:///doi.org/10.1017/CBO9780511810817

[46] M. Chiani, D. Dardari og MK Simon, Nye eksponentielle grænser og tilnærmelser til beregning af fejlsandsynlighed 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 og generalforsamlingen: en undersøgelse i analytisk talteori og beregningsmæssig kompleksitet, 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, Kvantealgoritme der giver eksponentiel hastighedsforøgelse til at finde egenværdier 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, Tidsafhængig hamiltonsk simulering ved hjælp af diskrete urkonstruktioner, arXiv:2203.11353 (2022).
https:///doi.org/10.48550/arXiv.2203.11353
arXiv: 2203.11353

[53] TD Ahle, Skarpe og enkle grænser for de rå momenter af binomial- og poissonfordelingen, 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).

Citeret af

[1] Dean Lee, "Kvanteteknikker til egenværdiproblemer", European Physical Journal A 59 11, 275 (2023).

[2] Tatsuhiko N. Ikeda, Hideki Kono og 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 og Bálint Koczor, "Algorithmic Shadow Spectroscopy", arXiv: 2212.11036, (2022).

[4] Sergiy Zhuk, Niall Robertson og Sergey Bravyi, "Trotter-fejlgrænser og dynamiske multi-produktformler til Hamilton-simulering", arXiv: 2306.12569, (2023).

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

[6] Lea M. Trenkwalder, Eleanor Scerri, Thomas E. O'Brien og Vedran Dunjko, "Compilation of product-formel Hamiltonian simulation via reinforcement learning", 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 Parallelisation of LCU via Commuting Operators", arXiv: 2312.00696, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-02-27 02:40:25). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-02-27 02:40:24).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.