Genomsnittlig fallverifiering av Quantum Fourier-transformen möjliggör värsta fall-fasuppskattning PlatoBlockchain-dataintelligens. Vertikal sökning. Ai.

Genomsnittlig fallverifiering av Quantum Fourier-transformen möjliggör värsta fall-fasuppskattning

Tidsstämpel: 7 december 2022 11:15

Noah Linden1 och Ronald de Wolf2

1School of Mathematics, University of Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI och University of Amsterdam, Nederländerna. rdewolf@cwi.nl

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Kvantfouriertransformen (QFT) är en nyckelprimitiv för kvantberäkning som vanligtvis används som en subrutin inom en större beräkning, till exempel för fasuppskattning. Som sådan kan vi ha liten kontroll över tillståndet som matas in till QFT. När vi implementerar en bra QFT kan vi alltså föreställa oss att den behöver prestera bra på godtyckliga indatatillstånd. $Att verifiera$ detta korrekta beteende i värsta fall av en QFT-implementering skulle vara exponentiellt svårt (i antalet qubits) i allmänhet, vilket ger upphov till oro för att denna verifiering skulle vara omöjlig i praktiken på alla användbara system. I det här dokumentet visar vi att vi i själva verket bara behöver ha bra $average$-$case$ prestanda för QFT för att uppnå bra $worst$-$case$ prestanda för nyckeluppgifter – fasuppskattning, periodfynd och amplituduppskattning. Vidare ger vi en mycket effektiv procedur för att verifiera detta erforderliga genomsnittliga beteende hos QFT.

Populär sammanfattning

Quantum Fourier-transformen (QFT) är en nyckelprimitiv som vanligtvis används som en subrutin inom en större kvantberäkning. Som sådan kan vi ha liten kontroll över tillståndet som matas in till QFT. Vi visar att god prestanda för QFT på ett $average$ ingångstillstånd (1) är effektivt testbart och (2) räcker för att uppnå bra $worst$-$case$ prestanda för QFT-baserade uppgifter som fasuppskattning, periodfynd och amplituduppskattning.

► BibTeX-data

► Referenser

[1] Scott Aaronson och Patrick Rall. Kvant ungefärlig räkning, förenklat. I Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), sidorna 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 och Umesh Vazirani. Styrkor och svagheter i kvantberäkning. 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 och Alain Tapp. Kvantamplitudförstärkning och uppskattning. I kvantberäkning och kvantinformation: A Millennium Volume, volym 305 i AMS Contemporary Mathematics Series, sidorna 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
arXiv: kvant-ph / 0005055

[4] Chi-Fang Chen och Fernando GSL Brandão. Koncentration för travfel. arXiv:2111.05324, 9 november 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.05324
arXiv: 2111.05324

[5] Richard Cleve, Artur Ekert, Chiara Macchiavello och Michele Mosca. Kvantalgoritmer återbesöks. I Proceedings of the Royal Society of London, volym A454, sidorna 339–354, 1998. quant-ph/​9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: kvant-ph / 9708016

[6] Don Coppersmith. En ungefärlig Fouriertransform användbar vid kvantfaktorering. IBM Research Report nr. 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 och David Poulin. Praktisk karakterisering av kvantenheter utan 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 och Elham Kashefi. Kvantcertifiering och 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 och Yi-Kai Liu. Direkt trohetsuppskattning från få Pauli-mätningar. 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 och Nathan Wiebe. Optimering av kvantoptimeringsalgoritmer via snabbare kvantgradientberäkning. I Proceedings of 30th ACM-SIAM SODA, sidorna 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465

[11] Lov K. Grover. En snabb kvantmekanisk algoritm för databassökning. I Proceedings of 28th ACM STOC, sidorna 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 och Nathan Wiebe. Kvantsingular värdetransformation och bortom: exponentiella förbättringar för kvantmatrisaritmetik. I Proceedings of 51st ACM STOC, sidorna 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838

[13] Stephen P. Jordan. Snabb kvantalgoritm för numerisk gradientuppskattning. Physical Review Letters, 95:050501, 2005. quant-ph/​0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: kvant-ph / 0405146

[14] Alexey Yu. Kitaev. Kvantmätningar och det abelska stabilisatorproblemet. quant-ph/​9511026, 12 november 1995.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: kvant-ph / 9511026

[15] Noah Linden och Ronald de Wolf. Lättviktsdetektering av ett litet antal stora fel i en kvantkrets. Quantum, 5(436), 2021. arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv: 2009.08840

[16] Urmila Mahadev. Klassisk verifiering av kvantberäkningar. I Proceedings of 59th IEEE FOCS, sidorna 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 och Isaac L. Chuang. En storslagen förening av kvantalgoritmer. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203

[18] Michael A. Nielsen och Isaac L. Chuang. Kvantberäkning och kvantinformation. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Rall. Snabbare koherenta kvantalgoritmer för fas-, energi- och amplituduppskattning. Quantum, 5(566), 2021. arXiv:2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv: 2103.09717

[20] Peter W. Shor. Polynom-tidsalgoritmer för primtalsfaktorisering och diskreta logaritmer på en kvantdator. SIAM Journal on Computing, 26(5):1484–1509, 1997. Tidigare version i FOCS'94. quant-ph/​9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: kvant-ph / 9508027

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li och Andrew M. Childs. Hamiltonsimulering med slumpmässiga ingångar. arXiv:2111.04773, 8 november 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv: 2111.04773

Citerad av

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

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-12-08 04:24:57). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2022-12-08 04:24:56).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal