Preverjanje povprečnega primera kvantne Fourierjeve transformacije omogoča oceno faze v najslabšem primeru PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

Preverjanje povprečnega primera kvantne Fourierjeve transformacije omogoča oceno faze v najslabšem primeru

Časovni žig: 7. december 2022 11:15

Noah Linden1 in Ronald de Wolf2

1Fakulteta za matematiko Univerze v Bristolu. n.linden@bristol.ac.uk
2QuSoft, CWI in Univerza v Amsterdamu, Nizozemska. rdewolf@cwi.nl

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Kvantna Fourierjeva transformacija (QFT) je ključni primitiv za kvantno računalništvo, ki se običajno uporablja kot podprogram znotraj večjega računanja, na primer za fazno oceno. Kot taki imamo morda malo nadzora nad stanjem, ki je vneseno v QFT. Tako si lahko pri izvajanju dobrega QFT predstavljamo, da mora dobro delovati na poljubnih vhodnih stanjih. $Preverjanje$ tega najslabšega primera pravilnega vedenja implementacije QFT bi bilo na splošno eksponentno težko (glede na število kubitov), ​​kar vzbuja skrb, da bi bilo to preverjanje v praksi nemogoče na katerem koli sistemu uporabne velikosti. V tem prispevku pokažemo, da pravzaprav potrebujemo samo dobro $povprečno$-$primerno$ delovanje QFT, da dosežemo dobro $najslabše$-$primerno$ delovanje za ključne naloge – ocena faze, iskanje period in ocena amplitude . Nadalje nudimo zelo učinkovit postopek za preverjanje tega zahtevanega obnašanja QFT v povprečnem primeru.

Priljubljen povzetek

Kvantna Fourierjeva transformacija (QFT) je ključni primitiv, ki se običajno uporablja kot podprogram v večjem kvantnem izračunu. Kot taki imamo morda malo nadzora nad stanjem, ki je vneseno v QFT. Pokazali smo, da je dobro delovanje QFT na $povprečnem$ vhodnem stanju (1) mogoče učinkovito preizkusiti in (2) zadostuje za doseganje dobrega delovanja v $najslabšem$-$primeru$ za naloge, ki temeljijo na QFT, kot je ocena faze, iskanje obdobja in ocena amplitude.

► BibTeX podatki

► Reference

[1] Scott Aaronson in Patrick Rall. Kvantno približno štetje, poenostavljeno. V zborniku 3. simpozija o preprostosti v algoritmih (SOSA), strani 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 in Umesh Vazirani. Prednosti in slabosti kvantnega računalništva. 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 in Alain Tapp. Ojačanje in ocena kvantne amplitude. V Quantum Computation and Quantum Information: A Millennium Volume, zvezek 305 AMS Contemporary Mathematics Series, strani 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: kvant-ph / 0005055

[4] Chi-Fang Chen in Fernando GSL Brandão. Koncentracija za Trotterjevo napako. arXiv:2111.05324, 9. november 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.05324
arXiv: 2111.05324

[5] Richard Cleve, Artur Ekert, Chiara Macchiavello in Michele Mosca. Ponovni pregled kvantnih algoritmov. V Proceedings of the Royal Society of London, zvezek A454, strani 339–354, 1998. quant-ph/​9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: kvant-ph / 9708016

[6] Don Coppersmith. Približna Fourierjeva transformacija, uporabna pri kvantnem faktoriziranju. IBM-ovo raziskovalno poročilo št. 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 in David Poulin. Praktična karakterizacija kvantnih naprav brez tomografije. 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 in Elham Kashefi. Kvantno certificiranje in primerjalna analiza. 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 in Yi-Kai Liu. Neposredna ocena natančnosti iz nekaj Paulijevih meritev. 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 in Nathan Wiebe. Optimiziranje algoritmov kvantne optimizacije s hitrejšim kvantnim gradientnim izračunom. V zborniku 30. ACM-SIAM SODA, strani 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465

[11] Lov K. Grover. Hiter kvantno mehanski algoritem za iskanje po bazi podatkov. V zborniku 28. ACM STOC, strani 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 in Nathan Wiebe. Kvantna transformacija singularne vrednosti in več: eksponentne izboljšave za kvantno matrično aritmetiko. V zborniku 51. ACM STOC, strani 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838

[13] Stephen P. Jordan. Hiter kvantni algoritem za numerično oceno gradienta. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: kvant-ph / 0405146

[14] Aleksej Ju. Kitaev. Kvantne meritve in problem Abelovega stabilizatorja. quant-ph/​9511026, 12. november 1995.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: kvant-ph / 9511026

[15] Noah Linden in Ronald de Wolf. Lahka detekcija majhnega števila velikih napak v kvantnem vezju. Quantum, 5(436), 2021. arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv: 2009.08840

[16] Urmila Mahadev. Klasična verifikacija kvantnih izračunov. V zborniku 59. IEEE FOCS, strani 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 in Isaac L. Chuang. Velika združitev kvantnih algoritmov. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203

[18] Michael A. Nielsen in Isaac L. Chuang. Kvantno računanje in kvantne informacije. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Rall. Hitrejši koherentni kvantni algoritmi za oceno faze, energije in amplitude. Quantum, 5 (566), 2021. arXiv: 2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv: 2103.09717

[20] Peter W. Šor. Polinomski časovni algoritmi za prafaktorizacijo in diskretne logaritme na kvantnem računalniku. SIAM Journal on Computing, 26(5):1484–1509, 1997. Prejšnja različica v FOCS'94. kvant-ph/​9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: kvant-ph / 9508027

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li in Andrew M. Childs. Hamiltonova simulacija z naključnimi vhodi. arXiv:2111.04773, 8. november 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv: 2111.04773

Navedel

[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén in Giacomo Nannicini, “Quantum tomography using state-preparation unitaries”, arXiv: 2207.08800.

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-12-08 04:24:57). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2022-12-08 04:24:56).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal