1Bristoli ülikooli matemaatikakool. n.linden@bristol.ac.uk
2QuSoft, CWI ja Amsterdami Ülikool, Holland. rdewolf@cwi.nl
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
Kvant-Fourieri teisendus (QFT) on kvantarvutuse võtmeprimitiiv, mida kasutatakse tavaliselt alamprogrammina suuremas arvutuses, näiteks faaside hindamiseks. Seetõttu võib meil olla vähe kontrolli QFT-sse sisestatava oleku üle. Seega võime hea QFT rakendamisel ette kujutada, et see peab suvaliste sisendolekute korral hästi toimima. Selle QFT-rakenduse halvimal juhul korrektse käitumise $kontrollimine$ oleks üldiselt eksponentsiaalselt raske (kubittide arvu poolest), tekitades muret, et see kontrollimine oleks praktikas võimatu mis tahes kasuliku suurusega süsteemis. Selles artiklis näitame, et tegelikult on meil vaja ainult head $keskmiselt$-$case$ jõudlust, et saavutada head $halvim$-$case$ jõudlust võtmeülesannete puhul – faasi hindamine, perioodi leidmine ja amplituudi hindamine. . Lisaks anname väga tõhusa protseduuri selle QFT nõutava keskmise juhtumi käitumise kontrollimiseks.
Populaarne kokkuvõte
► BibTeX-i andmed
► Viited
[1] Scott Aaronson ja Patrick Rall. Kvantligikaudne loendamine, lihtsustatud. Teoses Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), lk 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. Kvantarvutite tugevad ja nõrgad küljed. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
https:///doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001
[3] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvantamplituudi võimendamine ja hindamine. Teoses Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series, köide 305, lk 53–74. 2002. quant-ph/0005055.
https:///doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055
[4] Chi-Fang Chen ja Fernando GSL Brandão. Kontsentratsioon Trotteri vea jaoks. arXiv:2111.05324, 9. november 2021.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello ja Michele Mosca. Vaadati uuesti läbi kvantalgoritmid. Väljaandes Proceedings of the Royal Society of London, köide A454, lk 339–354, 1998. quant-ph/9708016.
https:///doi.org/10.1098/rspa.1998.0164
arXiv:quant-ph/9708016
[6] Don Coppersmith. Ligikaudne Fourier' teisendus, mis on kasulik kvantfaktoringus. IBM-i uurimisaruanne nr RC19642, quant-ph/0201067, 1994.
https:///doi.org/10.48550/arXiv.quant-ph/0201067
arXiv:quant-ph/0201067
[7] Marcus da Silva, Oliver Landon-Cardinal ja David Poulin. Kvantseadmete praktiline iseloomustus ilma tomograafiata. 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. Kvantsertifitseerimine ja võrdlusuuringud. 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. Otsene täpsuse hinnang mõne Pauli mõõtmise põhjal. 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. Kvantoptimeerimisalgoritmide optimeerimine kiirema kvantgradiendi arvutamise kaudu. Proceedings of 30th ACM-SIAM SODA, lk 1425–1444, 2019. arXiv:1711.00465.
https:///doi.org/10.1137/1.9781611975482.87
arXiv: 1711.00465
[11] Lov K. Grover. Kiire kvantmehaaniline algoritm andmebaasi otsimiseks. Teoses Proceedings of 28th ACM STOC, lk 212–219, 1996. quant-ph/9605043.
https:///doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043
[12] András Gilyén, Yuan Su, Guang Hao Low ja Nathan Wiebe. Kvant-ainsuse väärtuse teisendus ja kaugemalegi: kvantmaatriksi aritmeetika eksponentsiaalsed täiustused. Teoses Proceedings of 51st ACM STOC, lk 193–204, 2019. arXiv:1806.01838.
https:///doi.org/10.1145/3313276.3316366
arXiv: 1806.01838
[13] Stephen P. Jordan. Kiire kvantalgoritm numbrilise gradiendi hindamiseks. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https:///doi.org/10.1103/PhysRevLett.95.050501
arXiv:quant-ph/0405146
[14] Aleksei Yu. Kitaev. Kvantmõõtmised ja Abeli stabilisaatori probleem. quant-ph/9511026, 12. november 1995.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026
[15] Noah Linden ja Ronald de Wolf. Väikese arvu suurte vigade kerge tuvastamine kvantahelas. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Urmila Mahadev. Kvantarvutuste klassikaline kontrollimine. Väljaandes Proceedings of 59th IEEE FOCS, lk 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. Suur kvantalgoritmide ühendamine. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https:///doi.org/10.1103/PRXQuantum.2.040203
[18] Michael A. Nielsen ja Isaac L. Chuang. Kvantarvutus ja kvantteave. Cambridge University Press, 2000.
https:///doi.org/10.1017/CBO9780511976667
[19] Patrick Rall. Kiiremad koherentsed kvantalgoritmid faasi, energia ja amplituudi hindamiseks. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Polünoomaja algoritmid algfaktoriseerimiseks ja diskreetsete logaritmide jaoks kvantarvutis. SIAM Journal on Computing, 26(5):1484–1509, 1997. Varasem versioon FOCS'94-st. quant-ph/9508027.
https:///doi.org/10.1137/S0097539795293172
arXiv:quant-ph/9508027
[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li ja Andrew M. Childs. Hamiltoni simulatsioon juhuslike sisenditega. arXiv:2111.04773, 8. november 2021.
https:///doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Viidatud
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén ja Giacomo Nannicini, "Kvanttomograafia oleku ettevalmistamise ühikutega" arXiv: 2207.08800.
Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-12-08 04:24:57). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.
On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2022-12-08 04:24:56).
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
