Kvantti-Fourier-muunnoksen keskimääräinen tapausvarmennus mahdollistaa pahimman tapauksen vaiheen arvioinnin PlatoBlockchain-tietotiedon. Pystysuuntainen haku. Ai.

Kvantti-Fourier-muunnoksen keskimääräinen tapausvarmennus mahdollistaa pahimman tapauksen vaiheen arvioinnin

Aikaleima: 7. joulukuuta 2022 11

Noah Linden1 ja Ronald de Wolf2

1Matematiikan laitos, Bristolin yliopisto. n.linden@bristol.ac.uk
2QuSoft, CWI ja Amsterdamin yliopisto, Alankomaat. rdewolf@cwi.nl

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Kvantti-Fourier-muunnos (QFT) on kvanttilaskennan avainprimitiivi, jota käytetään tyypillisesti alirutiinina suuremmassa laskennassa, esimerkiksi vaiheestimointiin. Sellaisenaan emme voi hallita QFT:hen syötettyä tilaa. Näin ollen, kun toteutamme hyvää QFT:tä, voimme kuvitella, että sen on toimittava hyvin mielivaltaisissa syöttötiloissa. Tämän QFT-toteutuksen pahimman tapauksen oikean käyttäytymisen $varmentaminen$ olisi eksponentiaalisesti vaikeaa (kubittien määrässä) yleensä, mikä herättää huolen siitä, että tämä todentaminen olisi käytännössä mahdotonta missään hyödyllisen kokoisessa järjestelmässä. Tässä artikkelissa osoitamme, että itse asiassa meillä on oltava vain hyvä QFT:n $keskimääräinen$-$case$ suorituskyky saavuttaaksemme hyvän $huonoin$-$case$ -suorituskyvyn avaintehtävissä – vaiheen estimointi, jaksohaku ja amplitudiestimaatio. . Lisäksi annamme erittäin tehokkaan menettelyn varmistaaksemme tämän QFT:n vaaditun keskimääräisen tapauksen käyttäytymisen.

Suosittu yhteenveto

Kvantti-Fourier-muunnos (QFT) on avainprimitiivi, jota käytetään tyypillisesti alirutiinina suuremmassa kvanttilaskennassa. Sellaisenaan emme voi hallita QFT:hen syötettyä tilaa. Osoitamme, että QFT:n hyvä suorituskyky $average$-tulotilassa (1) on tehokkaasti testattavissa ja (2) riittää hyvän $worst$-$case$ -suorituskyvyn saavuttamiseen QFT-pohjaisissa tehtävissä, kuten vaiheestimointi, jaksohaku ja amplitudiarvio.

► BibTeX-tiedot

► Viitteet

[1] Scott Aaronson ja Patrick Rall. Kvanttilikimääräinen laskenta, yksinkertaistettu. Teoksessa Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), sivut 24–32, 2020. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / +1.9781611976014.5
arXiv: 1908.10846

[2] Charles H.Bennett, Ethan Bernstein, Gilles Brassard ja Umesh Vazirani. Kvanttilaskennan vahvuudet ja heikkoudet. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. quant-ph / 9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: kvant-ph / 9701001

[3] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvanttiamplitudin amplitudi ja arviointi. Julkaisussa Quantum Computation and Quantum Information: A Millennium Volume, Volume 305 of AMS Contemporary Mathematics Series, sivut 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: kvant-ph / 0005055

[4] Chi-Fang Chen ja Fernando GSL Brandão. Keskittyminen Trotter-virheeseen. arXiv:2111.05324, 9.
https://​/​doi.org/​10.48550/​arXiv.2111.05324
arXiv: 2111.05324

[5] Richard Cleve, Artur Ekert, Chiara Macchiavello ja Michele Mosca. Kvanttialgoritmit tarkasteltiin uudelleen. Teoksessa Proceedings of the Royal Society of London, osa A454, sivut 339–354, 1998. quant-ph/​9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: kvant-ph / 9708016

[6] Don Coppersmith. Likimääräinen Fourier-muunnos, joka on hyödyllinen kvanttifaktorituksessa. IBM:n tutkimusraportti nro RC19642, quant-ph/​0201067, 1994.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0201067
arXiv: kvant-ph / 0201067

[7] Marcus da Silva, Oliver Landon-Cardinal ja David Poulin. Kvanttilaitteiden käytännön karakterisointi ilman tomografiaa. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
arXiv: 1104.3835

[8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud ja Elham Kashefi. Kvanttisertifiointi ja benchmarking. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https:/​/​doi.org/​10.1038/​s42254-020-0186-4
arXiv: 1910.06343

[9] Steven T. Flammia ja Yi-Kai Liu. Suora tarkkuusestimaatti muutamasta Paulin mittauksesta. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695

[10] András Gilyén, Srinivasan Arunachalam ja Nathan Wiebe. Kvanttioptimointialgoritmien optimointi nopeamman kvanttigradienttilaskennan avulla. Teoksessa Proceedings of 30th ACM-SIAM SODA, sivut 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / +1.9781611975482.87
arXiv: 1711.00465

[11] Lov K. Grover. Nopea kvanttimekaaninen algoritmi tietokantahakuun. Teoksessa Proceedings of 28th ACM STOC, sivut 212–219, 1996. quant-ph/​9605043.
https: / / doi.org/ 10.1145 / +237814.237866
arXiv: kvant-ph / 9605043

[12] András Gilyén, Yuan Su, Guang Hao Low ja Nathan Wiebe. Kvanttiyksikköarvon muunnos ja sen jälkeen: eksponentiaalisia parannuksia kvanttimatriisiaritmetiikkaan. Julkaisussa Proceedings of 51st ACM STOC, sivut 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / +3313276.3316366
arXiv: 1806.01838

[13] Stephen P. Jordan. Nopea kvanttialgoritmi numeerisen gradientin estimointiin. Physical Review Letters, 95:050501, 2005. quant-ph/​0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: kvant-ph / 0405146

[14] Aleksei Yu. Kitaev. Kvanttimittaukset ja Abelin stabilaattoriongelma. quant-ph/​9511026, 12. marraskuuta 1995.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: kvant-ph / 9511026

[15] Noah Linden ja Ronald de Wolf. Kevyt havaitseminen pienestä määrästä suuria virheitä kvanttipiirissä. Quantum, 5(436), 2021. arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv: 2009.08840

[16] Urmila Mahadev. Kvanttilaskunnan klassinen verifiointi. Teoksessa Proceedings of 59th IEEE FOCS, sivut 259–267, 2018. arXiv:1804.01082.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
arXiv: 1804.01082

[17] John M. Martyn, Zane M. Rossi, Andrew K. Tan ja Isaac L. Chuang. Suuri kvanttialgoritmien yhdistäminen. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203

[18] Michael A. Nielsen ja Isaac L. Chuang. Kvanttilaskenta ja kvanttitieto. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Rall. Nopeammat koherentit kvanttialgoritmit vaihe-, energia- ja amplitudiarviointiin. Quantum, 5(566), 2021. arXiv:2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv: 2103.09717

[20] Peter W. Shor. Polynomiaikaiset algoritmit alkutekijöiden jakoa ja diskreettejä logaritmeja varten kvanttitietokoneella. SIAM Journal on Computing, 26(5):1484–1509, 1997. Aikaisempi versio FOCS'94:ssä. quant-ph/​9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: kvant-ph / 9508027

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li ja Andrew M. Childs. Hamiltonin simulointi satunnaisilla tuloilla. arXiv:2111.04773, 8.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv: 2111.04773

Viitattu

[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén ja Giacomo Nannicini, "Quantum tomography using state-preparation unitary" arXiv: 2207.08800.

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-12-08 04:24:57). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2022-12-08 04:24:56).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal