1School of Mathematics, Universiteit van Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI en Universiteit van Amsterdam, Nederland. rdewolf@cwi.nl
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
De kwantum Fourier-transformatie (QFT) is een sleutelprimitief voor kwantumcomputing die typisch wordt gebruikt als een subroutine binnen een grotere berekening, bijvoorbeeld voor faseschatting. Als zodanig hebben we mogelijk weinig controle over de status die wordt ingevoerd in de QFT. Bij het implementeren van een goede QFT kunnen we ons dus voorstellen dat deze goed moet presteren op willekeurige invoerstatussen. $Verifiëren$ van dit in het slechtste geval correcte gedrag van een QFT-implementatie zou in het algemeen exponentieel moeilijk zijn (in het aantal qubits), wat de bezorgdheid doet rijzen dat deze verificatie in de praktijk onmogelijk zou zijn op elk systeem van bruikbare omvang. In dit artikel laten we zien dat we in feite alleen goede $gemiddelde$-$case$-prestaties van de QFT nodig hebben om goede $worst$-$case$-prestaties te bereiken voor sleuteltaken – faseschatting, periodebepaling en amplitudeschatting . Verder geven we een zeer efficiënte procedure om dit vereiste gemiddelde gevalgedrag van de QFT te verifiëren.
Populaire samenvatting
► BibTeX-gegevens
► Referenties
[1] Scott Aaronson en Patrick Rall. Kwantum bij benadering tellen, vereenvoudigd. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), pagina's 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 en Umesh Vazirani. Sterke en zwakke punten van kwantumcomputers. 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 en Alain Tapp. Kwantumamplitude versterking en schatting. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 van AMS Contemporary Mathematics Series, pagina's 53-74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
arXiv: quant-ph / 0005055
[4] Chi-Fang Chen en Fernando GSL Brandão. Concentratie voor Trotter-fout. arXiv:2111.05324, 9 november 2021.
https://doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello en Michele Mosca. Kwantumalgoritmen herzien. In Proceedings of the Royal Society of London, volume A454, pagina's 339-354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[6] Don Kopersmid. Een geschatte Fourier-transformatie die nuttig is bij kwantumfactoring. IBM Research Report 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-kardinaal en David Poulin. Praktische karakterisering van kwantumapparaten zonder tomografie. 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 en Elham Kashefi. Kwantumcertificering en 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 en Yi-Kai Liu. Directe getrouwheidsschatting van enkele Pauli-metingen. 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 en Nathan Wiebe. Algoritmen voor kwantumoptimalisatie optimaliseren via snellere berekening van kwantumgradiënten. In Proceedings of 30th ACM-SIAM SODA, pagina's 1425-1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465
[11] Liefs K. Grover. Een snel kwantummechanisch algoritme voor het doorzoeken van databases. In Proceedings of 28th ACM STOC, pagina's 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 en Nathan Wiebe. Quantum singuliere waardetransformatie en verder: exponentiële verbeteringen voor kwantummatrixberekeningen. In Proceedings of 51st ACM STOC, pagina's 193-204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[13] Stephen P Jordan. Snel kwantumalgoritme voor numerieke gradiëntschatting. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: quant-ph / 0405146
[14] Alexei Yu. Kitajev. Kwantummetingen en het Abelse stabilisatorprobleem. quant-ph/9511026, 12 november 1995.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: quant-ph / 9511026
[15] Noah Linden en Ronald de Wolf. Lichtgewicht detectie van een klein aantal grote fouten in een kwantumcircuit. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Urmila Mahadev. Klassieke verificatie van kwantumberekeningen. In Proceedings of 59th IEEE FOCS, pagina's 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 en Isaac L. Chuang. Een grote unificatie van kwantumalgoritmen. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] Michael A. Nielsen en Isaac L. Chuang. Kwantumberekening en kwantuminformatie. Cambridge Universitaire Pers, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[19] Patrick Raall. Snellere coherente kwantumalgoritmen voor fase-, energie- en amplitudeschatting. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Polynoom-tijdalgoritmen voor priemfactorisatie en discrete logaritmen op een kwantumcomputer. SIAM Journal on Computing, 26(5):1484–1509, 1997. Eerdere versie in FOCS'94. quant-ph/9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027
[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li en Andrew M. Childs. Hamiltoniaanse simulatie met willekeurige invoer. arXiv:2111.04773, 8 november 2021.
https://doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Geciteerd door
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén en Giacomo Nannicini, “Quantum tomography using state-preparation unitaries”, arXiv: 2207.08800.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-12-08 04:24:57). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2022-12-08 04:24:56).
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
