1Institutt for fysikk, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
2Institutt for fysikk, Institutt for elektroteknikk og informatikk, og Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Nyere arbeid viser at kvantesignalbehandling (QSP) og dens multi-qubit løftede versjon, quantum singular value transformation (QSVT), forener og forbedrer presentasjonen av de fleste kvantealgoritmer. QSP/QSVT karakteriserer evnen til, ved vekslende ansätze, å uvitende transformere entallsverdiene til undersystemer av enhetlige matriser ved hjelp av polynomfunksjoner; disse algoritmene er numerisk stabile og analytisk godt forstått. Når det er sagt, QSP/QSVT krever konsekvent tilgang til et $single$ orakel, og sier ingenting om å beregne $textit{joint properties}$ av to eller flere orakler; disse kan være langt billigere å bestemme gitt en evne til å sette orakler mot hverandre sammenhengende.
Dette arbeidet introduserer en tilsvarende teori om QSP over flere variabler: M-QSP. Overraskende nok, til tross for at algebraens fundamentalteorem for multivariable polynomer ikke eksisterer, eksisterer det nødvendige og tilstrekkelige forhold under hvilke en ønsket $stabil $ multivariabel polynomtransformasjon er mulig. Dessuten overlever de klassiske subrutinene som brukes av QSP-protokoller i den multivariable innstillingen av ikke-åpenbare grunner, og forblir numerisk stabile og effektive. Opp til en veldefinert formodning gir vi bevis på at familien av oppnåelige multivariable transformasjoner er så løst begrenset som man kunne forvente. Den unike evnen M-QSP har til å $obliviously$ tilnærme $textit{joint functions}$ til flere variabler, fører koherent til nye speedups som ikke samsvarer med andre kvantealgoritmer, og gir en bro fra kvantealgoritmer til algebraisk geometri.
Utvalgt bilde: En figurativ representasjon av kretsene vurdert i M-QSP; her kan querenten suksessivt bruke sine egne enhetsoperasjoner, sammenflettet mellom muligens begge to orakulære enhetsoperasjoner. Egenskapene til slike kretser, og funksjonene de oppnår i parameterne til hvert orakel, er hovedfokuset i teorien om M-QSP.
Populært sammendrag
Dette arbeidet tar den underliggende intuisjonen og det matematiske grunnlaget for standardsetningen til QSP og undersøker hvordan de kan utvides til en multivariabel setting. Dvs., hvis man i stedet ønsker å beregne felles funksjoner av flere signaler med alternerende kvantekrets ansätze, hva er de tilsvarende resultatene fra algebraisk geometri som er nødvendig for å konstituere en nyttig teori om multivariabel QSP/QSVT (M-QSP/M-QSVT)? I sin tur kan evnen til å beregne fellesfunksjoner vises for å spare spørrings- og portkompleksitet sammenlignet med flere iterasjoner av enkeltvariable forekomster. For dette formål gir vi en serie innledende resultater som viser at, opp til en veldefinert formodning, er de mulige multivariable transformasjonene med M-QSP/M-QSVT så løst begrenset som man kunne forvente.
I tillegg til å demonstrere hvordan en endring av innstilling for QSP/QSVT kan føre til en enormt utvidet familie av kvantealgoritmer, peker dette arbeidet også mot en bred familie av matematiske underfelt og metoder med mulighet for ny relevans for kvanteinformasjon. Dette arbeidet fremmer en ny, nedenfra og opp-tilnærming til å forstå QSP/QSVT-lignende kretser, gjenbruk og utvider kraftige og tilsynelatende urelaterte matematiske teknikker mot ny fysisk intuisjon og beregningsmuligheter.
► BibTeX-data
► Referanser
[1] András Gilyén, Yuan Su, Guang Hao Low og Nathan Wiebe. "Quante singular verditransformasjon og utover: eksponentielle forbedringer for kvantematrisearitmetikk". Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019).
https: / / doi.org/ 10.1145 / 3313276.3316366
[2] Patrick Rall. "Raskere koherente kvantealgoritmer for fase-, energi- og amplitudeestimering". Quantum 5, 566 (2021).
https://doi.org/10.22331/q-2021-10-19-566
[3] John M. Martyn, Yuan Liu, Zachary E. Chin og Isaac L. Chuang. "Effektiv fullt koherent Hamiltonian simulering" (2021). arXiv:2110.11327.
arxiv: 2110.11327
[4] John M. Martyn, Zane M. Rossi, Andrew K. Tan og Isaac L. Chuang. "Stor forening av kvantealgoritmer". PRX Quantum 2, 040203 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[5] Seth Lloyd, Bobak T. Kiani, David RM Arvidsson-Shukur, Samuel Bosch, Giacomo De Palma, William M. Kaminsky, Zi-Wen Liu og Milad Marvian. "Hamiltonsk singular verditransformasjon og invers blokkkoding" (2021). arXiv:2104.01410.
arxiv: 2104.01410
[6] András Gilyén og Alexander Poremba. "Forbedrede kvantealgoritmer for troskapsestimering" (2022). arXiv:2203.15993.
arxiv: 2203.15993
[7] András Gilyén, Seth Lloyd, Iman Marvian, Yihui Quek og Mark M Wilde. "Kvantealgoritme for petz-gjenopprettingskanaler og ganske gode målinger". Physical Review Letters 128, 220502 (2022).
https: / / doi.org/ 10.1103 / PhysRevLett.128.220502
[8] Zane M Rossi og Isaac L Chuang. "Kvantehypotesetesting med gruppestruktur". Physical Review A 104, 012425 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.104.012425
[9] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang og Chunhao Wang. "Sampling-basert sublineær lavrangert matrisearitmetisk rammeverk for avkvantisering av kvantemaskinlæring". I Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Side 387–400. STOC 2020New York, NY, USA (2020). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 3357713.3384314
[10] Alex Lombardi, Fermi Ma og Nicholas Spooner. "Post-quantum null-kunnskap, revisited (eller: How to do quantum rewinding undetectably)" (2021). arXiv:2111.12257.
arxiv: 2111.12257
[11] GH Low, TJ Yoder og IL Chuang. "Metodologi for resonante likekantede sammensatte kvanteporter". Phys. Rev. X 6, 041067 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.041067
[12] GH Low og IL Chuang. "Optimal Hamiltonian simulering ved kvantesignalbehandling". Phys. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
[13] GH Low og IL Chuang. "Hamiltonsk simulering ved kvbitisering". Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[14] Jeongwan Haah. "Produktnedbrytning av periodiske funksjoner i kvantesignalbehandling". Quantum 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190
[15] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang og Mario Szegedy. "Finne vinkler for kvantesignalbehandling med maskinpresisjon" (2020). arXiv:2003.02831.
arxiv: 2003.02831
[16] Yulong Dong, Xiang Meng, K. Birgitta Whaley og Lin Lin. "Effektiv fasefaktorevaluering i kvantesignalbehandling". Phys. Rev. A 103 (2021).
https: / / doi.org/ 10.1103 / physreva.103.042419
[17] Aram W. Harrow, Avinatan Hassidim og Seth Lloyd. "Kvantealgoritme for lineære ligningssystemer". Phys. Rev. Lett. 103 (2009).
https: / / doi.org/ 10.1103 / physrevlett.103.150502
[18] Peter W Shor. "Polynomiske tidsalgoritmer for primfaktorisering og diskrete logaritmer på en kvantedatamaskin". SIAM review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0097539795293172
[19] Richard P Feynman. "Simulere fysikk med datamaskiner". I Feynman og beregning. Side 133–153. CRC Press (2018).
https: / / doi.org/ 10.1007 / BF02650179
[20] Jintai Ding og Bo-Yin Yang. "Multivariat offentlig nøkkelkryptografi". I postkvantekryptografi. Side 193–241. Springer (2009).
https://doi.org/10.1007/978-0-387-36946-4
[21] Scott Aaronson og Paul Christiano. "Kvantepenger fra skjulte underrom". I Proceedings av det førtifjerde årlige ACM-symposiet om databehandlingsteori. Side 41–60. (2012).
https:///doi.org/10.48550/arXiv.1203.4740
[22] Anurag Anshu, Itai Arad og David Gosset. "En områdelov for 2d frustrasjonsfrie spinnsystemer". I Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Side 12–18. (2022).
https: / / doi.org/ 10.1145 / 3519935.3519962
[23] Rahul Sarkar og Theodore J. Yoder. "Tetthetsteoremer med applikasjoner i kvantesignalbehandling" (2022). arXiv:2111.07182.
arxiv: 2111.07182
[24] Jiasu Wang, Yulong Dong og Lin Lin. "Om energilandskapet til symmetrisk kvantesignalbehandling" (2021). arXiv:2110.04993.
arxiv: 2110.04993
[25] Joran Van Apeldoorn, András Gilyén, Sander Gribling og Ronald de Wolf. "Quantum SDP-løsere: Bedre øvre og nedre grenser". Quantum 4, 230 (2020).
https:///doi.org/10.48550/arXiv.1705.01843
[26] Lin Lin og Yu Tong. "Optimal polynombasert kvanteegentilstandsfiltrering med applikasjon for å løse kvantelineære systemer". Quantum 4, 361 (2020).
https://doi.org/10.22331/q-2020-11-11-361
[27] Patrick Rall. "Kvantealgoritmer for å estimere fysiske mengder ved bruk av blokkkodinger". Phys. Rev. A 102, 022408 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
[28] Yu Tong, Dong An, Nathan Wiebe og Lin Lin. "Rask inversjon, forhåndsbetingede kvantelineære systemløsere, rask Green-funksjonsberegning og rask evaluering av matrisefunksjoner". Phys. Rev. A 104, 032422 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.104.032422
[29] J. Geronimo og Hugo Woerdeman. "Positive utvidelser, Fejér-Riesz-faktorisering og autoregressive filtre i to variabler". Ann. Matte. 160, 839–906 (2004).
https: / / doi.org/ 10.4007 / annals.2004.160.839
[30] Murray Marshall. "Positive polynomer og summer av kvadrater". Nummer 146 i matematiske undersøkelser og monografier. Er. Matte. Soc. (2008).
https: / / doi.org/ 10.1090 / Surv / 146
[31] Bogdan Dumitrescu. "Positive trigonometriske polynomer og signalbehandlingsapplikasjoner". Springer. Sveits (2007).
https://doi.org/10.1007/978-3-319-53688-0
[32] Michael Dritschel og Hugo Woerdeman. "Ytre faktoriseringer i en og flere variabler". Trans. Er. Matte. Soc. 357, 4661–4679 (2005).
https:///doi.org/10.48550/arXiv.math/0403099
[33] Jeffrey S Geronimo og Hugo Woerdeman. "To variable ortogonale polynomer på bisirkelen og strukturerte matriser". SIAM-tidsskrift om matriseanalyse og applikasjoner 29, 796–825 (2007).
https: / / doi.org/ 10.1137 / 060662472
[34] Michael A. Dritschel og James Rovnyak. "Operatoren Fejér-Riesz-teoremet". Side 223–254. Springer Basel. Basel (2010).
https://doi.org/10.1007/978-3-0346-0347-8_14
[35] Robin Hartshorne. "Algebraisk geometri". Bind 52. Springer New York, NY. (2013).
https://doi.org/10.1007/978-1-4757-3849-0
[36] William Fulton. "Algebraiske kurver: En introduksjon til algebraisk geometri". Addison-Wesley. (1969). url: dept.math.lsa.umich.edu/wfulton/CurveBook.pdf.
https:///dept.math.lsa.umich.edu/~wfulton/CurveBook.pdf
[37] George Polya og Gabor Szegö. "Problemer og teoremer i analyse II". Springer. Berlin (1998).
https://doi.org/10.1007/978-3-642-61905-2
[38] F. Grenez. "Design av lineære eller minimumsfase FIR-filtre ved begrenset Chebyshev-tilnærming". Signalprosess. 5, 325-332 (1983).
https://doi.org/10.1016/0165-1684(83)90091-9
[39] E. Remez. "Sur le calcul effectif des polynomes dapproximation de Tchebichef". CR Acad. Sci. Paris 199, 337–340 (1934).
[40] J. McClellan, T. Parks og L. Rabiner. "Et dataprogram for å designe optimale FIR lineære fase digitale filtre". IEEE trans. lyd elektroakust. 21, 506-526 (1973).
https:///doi.org/10.1109/TAU.1973.1162525
[41] Jeffrey S Geronimo og Hugo J Woerdeman. "To-variable polynomer: kryssende nuller og stabilitet". IEEE Trans. Kretser Syst. I: Regular Papers 53, 1130–1139 (2006).
https: / / doi.org/ 10.1109 / TCSI.2005.862180
[42] Anatolii Grinshpan, Dmitry S Kaliuzhnyi-Verbovetskyi, Victor Vinnikov og Hugo J Woerdeman. "Stabile og reelle nullpolynomer i to variabler". Multidimens. Syst. Signalprosess. 27, 1–26 (2016).
https://doi.org/10.1007/s11045-014-0286-3
[43] Rudolf Lidl og Ch. Wells. "Chebyshev polynomer i flere variabler." Journal für die reine und angewandte Mathematik 255, 104–111 (1972).
https:///doi.org/10.1515/crll.1972.255.104
[44] Charles F Dunkl og Yuan Xu. "Ortogonale polynomer med flere variabler". Nummer 155 i Encyclopedia of mathematics and its applications. Cambridge University Press. (2014).
https: / / doi.org/ 10.1017 / CBO9781107786134
[45] RJ Beerends. "Chebyshev polynomer i flere variabler og den radielle delen av Laplace-Beltrami-operatøren". Trans. Er. Matte. Soc. 328, 779-814 (1991).
https: / / doi.org/ 10.2307 / 2001804
[46] Zane M Rossi, Jeffery Yu, Isaac L Chuang og Sho Sugiura. "Kvantefordel for støyende kanaldiskriminering". Phys. Rev. A 105, 032401 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.032401
[47] Camille Jordan. "Essai sur la géométrie à $ n $ dimensjoner". Bulletin de la Société mathématique de France 3, 103–174 (1875).
[48] DJ Newman og HS Shapiro. "Jacksons teorem i høyere dimensjoner". I On Approximation Theory/Über Approximationstheorie. Side 208–219. Springer (1964).
https://doi.org/10.1007/978-3-0348-4131-3_20
[49] David L Ragozin. "Polynomisk tilnærming på kompakte manifolder og homogene rom". Trans. Er. Matte. Soc. 150, 41-53 (1970).
https://doi.org/10.1090/S0002-9947-1970-0410210-0
[50] Lloyd Trefethen. "Multivariat polynomtilnærming i hyperkuben". Proc. Er. Matte. Soc. 145, 4837–4844 (2017).
https:///doi.org/10.1090/proc/13623
[51] TW Parks og James McClellan. "Chebyshev-tilnærming for ikke-rekursive digitale filtre med lineær fase". IEEE Transactions on circuit theory 19, 189–194 (1972).
https: / / doi.org/ 10.1109 / TCT.1972.1083419
[52] GA Watson. "En multippel utvekslingsalgoritme for multivariat Chebyshev-tilnærming". SIAM J. Nummer. Anal. 12, 46-52 (1975).
https: / / doi.org/ 10.1137 / 0712004
[53] Hugo J Woerdeman, Jeffrey S Geronimo og Glaysar Castro. "En numerisk algoritme for stabil 2D autoregressiv filterdesign". Signal Processing 83, 1299–1308 (2003).
https://doi.org/10.1016/S0165-1684(03)00057-4
[54] Yvan Hachez og Hugo J Woerdeman. "Tilnærmelsesvis summer av kvadrater med et enkelt kvadrat". Lineær Algebra Appl. 399, 187–201 (2005).
https: / / doi.org/ 10.1016 / j.laa.2004.10.005
[55] Mario Szegedy. "Kvantehastigheten til Markov-kjedebaserte algoritmer". I 45. årlige IEEE-symposium om grunnlaget for informatikk. Side 32–41. IEEE (2004).
https: / / doi.org/ 10.1109 / FOCS.2004.53
[56] Chris Marriott og John Watrous. "Quantum Arthur – Merlin-spill". Comput. Kompleks. 14, 122–152 (2005).
https: / / doi.org/ 10.1007 / s00037-005-0194-x
[57] Daniel Nagaj, Pawel Wocjan og Yong Zhang. "Rask forsterkning av QMA". Kvanteinformasjon. Comput. 9, 1053–1068 (2009).
https: / / doi.org/ 10.26421 / QIC9.11-12-8
Sitert av
[1] Shantanav Chakraborty, Aditya Morolia og Anurudh Peduri, "Quantum Regularized Least Squares", arxiv: 2206.13143.
Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2022-09-21 22:29:06). 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 2022-09-21 22:29:04).
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.
