1School of Mathematics, University of Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI og University of Amsterdam, Holland. rdewolf@cwi.nl
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Kvante Fourier-transformationen (QFT) er en nøgleprimitiv for kvanteberegning, der typisk bruges som en subrutine inden for en større beregning, for eksempel til faseestimering. Som sådan kan vi have ringe kontrol over den tilstand, der er input til QFT. Ved implementering af en god QFT kan vi således forestille os, at den skal fungere godt på vilkårlige inputtilstande. $At verificere$ denne worst-case korrekte opførsel af en QFT-implementering ville være eksponentielt svært (i antallet af qubits) generelt, hvilket giver anledning til bekymring for, at denne verifikation ville være umulig i praksis på et hvilket som helst system af brugbar størrelse. I dette papir viser vi, at vi faktisk kun behøver at have en god $average$-$case$ ydeevne af QFT for at opnå en god $worst$-$case$ ydeevne for nøgleopgaver - faseestimering, periodefunding og amplitudeestimering . Yderligere giver vi en meget effektiv procedure til at verificere denne krævede gennemsnits-case opførsel af QFT.
Populært resumé
► BibTeX-data
► Referencer
[1] Scott Aaronson og Patrick Rall. Kvante omtrentlig optælling, forenklet. I Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), side 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 og Umesh Vazirani. Styrker og svagheder ved kvanteberegning. 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 og Alain Tapp. Kvanteamplitudeforstærkning og estimering. In Quantum Computation and Quantum Information: A Millennium Volume, bind 305 af AMS Contemporary Mathematics Series, side 53-74. 2002. quant-ph/0005055.
https:///doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055
[4] Chi-Fang Chen og Fernando GSL Brandão. Koncentration for travfejl. arXiv:2111.05324, 9. november 2021.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello og Michele Mosca. Kvantealgoritmer revideret. I Proceedings of the Royal Society of London, bind A454, side 339-354, 1998. quant-ph/9708016.
https:///doi.org/10.1098/rspa.1998.0164
arXiv:quant-ph/9708016
[6] Don Coppersmith. En omtrentlig Fourier-transformation, der er nyttig i kvantefaktorering. IBM Research Report No. 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 og David Poulin. Praktisk karakterisering af kvanteudstyr uden tomografi. 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 og Elham Kashefi. Kvantecertificering og 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 og Yi-Kai Liu. Direkte troskabsestimat fra få Pauli-målinger. 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 og Nathan Wiebe. Optimering af kvanteoptimeringsalgoritmer via hurtigere kvantegradientberegning. I Proceedings of 30th ACM-SIAM SODA, side 1425-1444, 2019. arXiv:1711.00465.
https:///doi.org/10.1137/1.9781611975482.87
arXiv: 1711.00465
[11] Kærlighed K. Grover. En hurtig kvantemekanisk algoritme til databasesøgning. I Proceedings of 28th ACM STOC, side 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 og Nathan Wiebe. Kvantesingular værditransformation og videre: eksponentielle forbedringer for kvantematrix-aritmetik. I Proceedings of 51st ACM STOC, side 193-204, 2019. arXiv:1806.01838.
https:///doi.org/10.1145/3313276.3316366
arXiv: 1806.01838
[13] Stephen P. Jordan. Hurtig kvantealgoritme til numerisk gradientestimering. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https:///doi.org/10.1103/PhysRevLett.95.050501
arXiv:quant-ph/0405146
[14] Alexey Yu. Kitaev. Kvantemålinger og det abelske stabilisatorproblem. quant-ph/9511026, 12. november 1995.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026
[15] Noah Linden og Ronald de Wolf. Letvægtsdetektering af et lille antal store fejl i et kvantekredsløb. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Urmila Mahadev. Klassisk verifikation af kvanteberegninger. I Proceedings of 59th IEEE FOCS, side 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 og Isaac L. Chuang. En storslået forening af kvantealgoritmer. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https:///doi.org/10.1103/PRXQuantum.2.040203
[18] Michael A. Nielsen og Isaac L. Chuang. Kvanteberegning og kvanteinformation. Cambridge University Press, 2000.
https:///doi.org/10.1017/CBO9780511976667
[19] Patrick Rall. Hurtigere sammenhængende kvantealgoritmer til fase-, energi- og amplitudeestimering. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Polynomial-tidsalgoritmer til primfaktorisering og diskrete logaritmer på en kvantecomputer. SIAM Journal on Computing, 26(5):1484–1509, 1997. Tidligere version i 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 og Andrew M. Childs. Hamiltonsimulering med tilfældige input. arXiv:2111.04773, 8. november 2021.
https:///doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Citeret af
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén og Giacomo Nannicini, "Quantum tomography using state-preparation unitaries", arXiv: 2207.08800.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-12-08 04:24:57). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2022-12-08 04:24:56).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
