1Fakultät für Mathematik, Universität Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI und Universität Amsterdam, Niederlande. rdewolf@cwi.nl
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Die Quanten-Fourier-Transformation (QFT) ist ein Schlüsselprimitiv für Quantencomputer, das typischerweise als Unterprogramm innerhalb einer größeren Berechnung verwendet wird, beispielsweise zur Phasenschätzung. Daher haben wir möglicherweise wenig Kontrolle über den Zustand, der in die QFT eingegeben wird. Daher können wir uns bei der Implementierung einer guten QFT vorstellen, dass sie bei beliebigen Eingabezuständen eine gute Leistung erbringen muss. $Die Überprüfung dieses korrekten Verhaltens einer QFT-Implementierung im schlimmsten Fall wäre im Allgemeinen exponentiell schwierig (in Bezug auf die Anzahl der Qubits), was die Sorge aufkommen lässt, dass diese Überprüfung in der Praxis auf jedem System nützlicher Größe unmöglich wäre. In diesem Artikel zeigen wir, dass wir tatsächlich nur über eine gute Durchschnittsleistung der QFT verfügen müssen, um eine gute Leistung im schlechtesten Fall für Schlüsselaufgaben zu erreichen – Phasenschätzung, Periodenfindung und Amplitudenschätzung . Darüber hinaus geben wir ein sehr effizientes Verfahren zur Überprüfung dieses erforderlichen Durchschnittsverhaltens der QFT an.
Populäre Zusammenfassung
► BibTeX-Daten
► Referenzen
[1] Scott Aaronson und Patrick Rall. Quantennäherungszählen, vereinfacht. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), Seiten 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 und Umesh Vazirani. Stärken und Schwächen des Quantencomputers. 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 und Alain Tapp. Quantenamplitudenverstärkung und -schätzung. In Quantenberechnung und Quanteninformation: Ein Millennium-Band, Band 305 der AMS Contemporary Mathematics Series, Seiten 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[4] Chi-Fang Chen und Fernando GSL Brandão. Konzentration auf Trotter-Fehler. arXiv:2111.05324, 9. November 2021.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello und Michele Mosca. Quantenalgorithmen neu interpretiert. In Proceedings of the Royal Society of London, Band A454, Seiten 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[6] Don Coppersmith. Eine ungefähre Fourier-Transformation, die bei der Quantenfaktorisierung nützlich ist. 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-Cardinal und David Poulin. Praktische Charakterisierung von Quantengeräten ohne Tomographie. 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 und Elham Kashefi. Quantenzertifizierung und 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 und Yi-Kai Liu. Direkte Genauigkeitsschätzung aus wenigen Pauli-Messungen. 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 und Nathan Wiebe. Optimierung von Quantenoptimierungsalgorithmen durch schnellere Quantengradientenberechnung. In Proceedings of 30th ACM-SIAM SODA, Seiten 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465
[11] Liebe K. Grover. Ein schneller quantenmechanischer Algorithmus für die Datenbanksuche. In Proceedings of 28th ACM STOC, Seiten 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 und Nathan Wiebe. Quantensingulärwerttransformation und darüber hinaus: exponentielle Verbesserungen für die Quantenmatrixarithmetik. In Proceedings of 51st ACM STOC, Seiten 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[13] Stephen P. Jordan. Schneller Quantenalgorithmus zur numerischen Gradientenschätzung. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https://doi.org/ 10.1103/PhysRevLett.95.050501
arXiv: quant-ph / 0405146
[14] Alexey Yu. Kitajew. Quantenmessungen und das Abelsche Stabilisatorproblem. quant-ph/9511026, 12. November 1995.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: quant-ph / 9511026
[15] Noah Linden und Ronald de Wolf. Leichte Erkennung einer kleinen Anzahl großer Fehler in einer Quantenschaltung. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Urmila Mahadev. Klassische Verifizierung von Quantenberechnungen. In Proceedings of 59th IEEE FOCS, Seiten 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 und Isaac L. Chuang. Eine große Vereinheitlichung der Quantenalgorithmen. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] Michael A. Nielsen und Isaac L. Chuang. Quantencomputation und Quanteninformation. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[19] Patrick Rall. Schnellere kohärente Quantenalgorithmen zur Phasen-, Energie- und Amplitudenschätzung. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Polynomzeitalgorithmen zur Primfaktorzerlegung und diskreten Logarithmen auf einem Quantencomputer. SIAM Journal on Computing, 26(5):1484–1509, 1997. Frühere Version 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 und Andrew M. Childs. Hamilton-Simulation mit zufälligen Eingaben. arXiv:2111.04773, 8. November 2021.
https:///doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Zitiert von
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén und Giacomo Nannicini, „Quantum tomography using state-preparation unitaries“, arXiv: 2207.08800.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2022, 12:08:04 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2022-12-08 04:24:56).
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
