1Σχολή Μαθηματικών, Πανεπιστήμιο του Μπρίστολ. n.linden@bristol.ac.uk
2QuSoft, CWI και Πανεπιστήμιο του Άμστερνταμ, Ολλανδία. rdewolf@cwi.nl
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Ο κβαντικός μετασχηματισμός Fourier (QFT) είναι ένα βασικό πρωτόγονο για τον κβαντικό υπολογισμό που χρησιμοποιείται συνήθως ως υπορουτίνα σε έναν μεγαλύτερο υπολογισμό, για παράδειγμα για την εκτίμηση φάσης. Ως εκ τούτου, ενδέχεται να έχουμε ελάχιστο έλεγχο στην κατάσταση που εισάγεται στο QFT. Έτσι, κατά την εφαρμογή ενός καλού QFT, μπορούμε να φανταστούμε ότι πρέπει να έχει καλή απόδοση σε αυθαίρετες καταστάσεις εισαγωγής. $Επαλήθευση$ αυτή η σωστή συμπεριφορά στη χειρότερη περίπτωση μιας εφαρμογής QFT θα ήταν εκθετικά δύσκολη (στον αριθμό των qubits) γενικά, εγείροντας την ανησυχία ότι αυτή η επαλήθευση θα ήταν αδύνατη στην πράξη σε οποιοδήποτε σύστημα χρήσιμου μεγέθους. Σε αυτό το άρθρο δείχνουμε ότι, στην πραγματικότητα, χρειάζεται μόνο να έχουμε καλή απόδοση $μέση$-$case$ του QFT για να επιτύχουμε καλή απόδοση $worst$-$case$ για βασικές εργασίες – εκτίμηση φάσης, εύρεση περιόδου και εκτίμηση πλάτους . Επιπλέον, δίνουμε μια πολύ αποτελεσματική διαδικασία για την επαλήθευση αυτής της απαιτούμενης συμπεριφοράς μέσης περίπτωσης του QFT.
Δημοφιλή περίληψη
► Δεδομένα BibTeX
► Αναφορές
[1] Σκοτ Άαρονσον και Πάτρικ Ραλ. Κβαντική κατά προσέγγιση μέτρηση, απλοποιημένη. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), σελίδες 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 και Umesh Vazirani. Πλεονεκτήματα και αδυναμίες της κβαντικής πληροφορικής. 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 και Alain Tapp. Ενίσχυση και εκτίμηση κβαντικού πλάτους. Στο Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, σελίδες 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[4] Chi-Fang Chen και Fernando GSL Brandão. Συγκέντρωση για σφάλμα Trotter. arXiv:2111.05324, 9 Νοεμβρίου 2021.
https://doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[5] Richard Cleve, Artur Ekert, Chiara Macchiavello και Michele Mosca. Οι κβαντικοί αλγόριθμοι επανεξετάστηκαν. In Proceedings of the Royal Society of London, τόμος A454, σελίδες 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[6] Don Coppersmith. Ένας κατά προσέγγιση μετασχηματισμός Fourier χρήσιμος στην κβαντική παραγοντοποίηση. 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 και David Poulin. Πρακτικός χαρακτηρισμός κβαντικών συσκευών χωρίς τομογραφία. 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 και Elham Kashefi. Κβαντική πιστοποίηση και συγκριτική αξιολόγηση. 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 και Yi-Kai Liu. Άμεση εκτίμηση πιστότητας από λίγες μετρήσεις Pauli. 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 και Nathan Wiebe. Βελτιστοποίηση αλγορίθμων κβαντικής βελτιστοποίησης μέσω ταχύτερου υπολογισμού κβαντικής κλίσης. In Proceedings of 30th ACM-SIAM SODA, σελίδες 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465
[11] Λοβ Κ. Γκρόβερ. Ένας γρήγορος κβαντομηχανικός αλγόριθμος για αναζήτηση βάσεων δεδομένων. In Proceedings of 28th ACM STOC, pages 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 και Nathan Wiebe. Κβαντικός μετασχηματισμός μοναδικής τιμής και πέρα: εκθετικές βελτιώσεις για την αριθμητική κβαντικών πινάκων. In Proceedings of 51st ACM STOC, pages 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[13] Stephen P. Jordan. Γρήγορος κβαντικός αλγόριθμος για αριθμητική εκτίμηση κλίσης. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: quant-ph / 0405146
[14] Alexey Yu. Κιτάεφ. Κβαντικές μετρήσεις και το πρόβλημα του σταθεροποιητή Abelian. quant-ph/9511026, 12 Νοεμβρίου 1995.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: quant-ph / 9511026
[15] Noah Linden και Ronald de Wolf. Ελαφρύς εντοπισμός μικρού αριθμού μεγάλων σφαλμάτων σε ένα κβαντικό κύκλωμα. Quantum, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[16] Ουρμίλα Μαχάντεφ. Κλασική επαλήθευση κβαντικών υπολογισμών. In Proceedings of 59th IEEE FOCS, pages 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 και Isaac L. Chuang. Μια μεγάλη ενοποίηση κβαντικών αλγορίθμων. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] Michael A. Nielsen και Isaac L. Chuang. Κβαντικός Υπολογισμός και Κβαντικές Πληροφορίες. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[19] Πάτρικ Ραλ. Ταχύτεροι συνεκτικοί κβαντικοί αλγόριθμοι για εκτίμηση φάσης, ενέργειας και πλάτους. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
arXiv: 2103.09717
[20] Peter W. Shor. Αλγόριθμοι πολυωνυμικού χρόνου για παραγοντοποίηση πρώτων και διακριτοί λογάριθμοι σε κβαντικό υπολογιστή. SIAM Journal on Computing, 26(5):1484–1509, 1997. Προγενέστερη έκδοση στο 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 και Andrew M. Childs. Χαμιλτονιανή προσομοίωση με τυχαίες εισόδους. arXiv:2111.04773, 8 Νοεμβρίου 2021.
https://doi.org/10.48550/arXiv.2111.04773
arXiv: 2111.04773
Αναφέρεται από
[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén και Giacomo Nannicini, «Κβαντική τομογραφία χρησιμοποιώντας μονάδες προετοιμασίας κράτους». arXiv: 2207.08800.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2022-12-08 04:24:57). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2022-12-08 04:24:56).
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
