Gjennomsnittlig saksbekreftelse av Quantum Fourier-transformasjonen muliggjør Worst-Case faseestimering PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Gjennomsnittlig saksbekreftelse av kvantefouriertransformasjonen muliggjør verstefallsfaseestimering

Tidsstempel: 7. desember 2022 11:15

Noah Linden1 og Ronald de Wolf2

1School of Mathematics, University of Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI og University of Amsterdam, Nederland. rdewolf@cwi.nl

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Kvante-Fourier-transformasjonen (QFT) er en nøkkelprimitiv for kvanteberegning som vanligvis brukes som en subrutine i en større beregning, for eksempel for faseestimering. Som sådan kan vi ha liten kontroll over staten som er input til QFT. Når vi implementerer en god QFT, kan vi derfor forestille oss at den må prestere godt på vilkårlige input-tilstander. $At verifisere$ denne verste tilfelle korrekte oppførselen til en QFT-implementering ville være eksponentielt vanskelig (i antall qubits) generelt, noe som vekker bekymring for at denne verifiseringen ville være umulig i praksis på et hvilket som helst system av nyttig størrelse. I denne artikkelen viser vi at vi faktisk bare trenger å ha god $average$-$case$ ytelse av QFT for å oppnå god $worst$-$case$ ytelse for nøkkeloppgaver – faseestimering, periodefunn og amplitudeestimering . Videre gir vi en veldig effektiv prosedyre for å verifisere denne nødvendige gjennomsnittlige oppførselen til QFT.

Populært sammendrag

Kvante-Fourier-transformasjonen (QFT) er en nøkkelprimitiv som vanligvis brukes som en subrutine i en større kvanteberegning. Som sådan kan vi ha liten kontroll over staten som er input til QFT. Vi viser at god ytelse av QFT på en $average$ input-tilstand (1) er effektivt testbar, og (2) er tilstrekkelig for å oppnå god $worst$-$case$ ytelse for QFT-baserte oppgaver som faseestimering, periodefunn og amplitudeestimering.

► BibTeX-data

► Referanser

[1] Scott Aaronson og Patrick Rall. Kvante omtrentlig telling, 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 svakheter 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. Kvantamplitude amplifikasjon og estimering. I Quantum Computation and Quantum Information: A Millennium Volume, bind 305 i 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. Konsentrasjon for travfeil. 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 revidert. 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-transform som 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 av kvanteenheter uten 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. Kvantesertifisering 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 troskapsestimat 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. Optimalisering av kvanteoptimaliseringsalgoritmer via raskere 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] Kjærlighet K. Grover. En rask kvantemekanisk algoritme for databasesøk. 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 verditransformasjon og utover: eksponentielle forbedringer for kvantematrisearitmetikk. 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. Rask kvantealgoritme for 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 stabilisatorproblemet. 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. Lettvektsdeteksjon av et lite antall store feil i en kvantekrets. Quantum, 5(436), 2021. arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arxiv: 2009.08840

[16] Urmila Mahadev. Klassisk verifisering av 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ått forening av 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 kvanteinformasjon. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Rall. Raskere koherente kvantealgoritmer for 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. Polynom-tidsalgoritmer for primfaktorisering og diskrete logaritmer på en kvantedatamaskin. SIAM Journal on Computing, 26(5):1484–1509, 1997. Tidligere versjon 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 tilfeldige innganger. arXiv:2111.04773, 8. november 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arxiv: 2111.04773

Sitert av

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

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2022-12-08 04:24:57). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2022-12-08 04:24:56).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal