Επιτάχυνση κβαντικών αλγορίθμων με προυπολογισμό

Επιτάχυνση κβαντικών αλγορίθμων με προυπολογισμό

Επιτάχυνση κβαντικών αλγορίθμων με προυπολογισμό PlatoBlockchain Data Intelligence. Κάθετη αναζήτηση. Ολα συμπεριλαμβάνονται.

William J. Huggins και Jarrod R. McClean

Google Quantum AI, Βενετία, Καλιφόρνια, ΗΠΑ

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Οι εφαρμογές υπολογιστών στον πραγματικό κόσμο μπορεί να είναι εξαιρετικά ευαίσθητες στο χρόνο. Θα ήταν πολύτιμο εάν μπορούσαμε να επιταχύνουμε τέτοιες εργασίες εκτελώντας ορισμένες από τις εργασίες εκ των προτέρων. Με κίνητρο αυτό, προτείνουμε ένα μοντέλο κόστους για κβαντικούς αλγόριθμους που επιτρέπει τον κβαντικό προυπολογισμό. δηλ. για ένα πολυωνυμικό ποσό «ελεύθερου» υπολογισμού προτού καθοριστεί πλήρως η είσοδος σε έναν αλγόριθμο και μέθοδοι για την αξιοποίησή του. Αναλύουμε δύο οικογένειες μονάδων που είναι ασυμπτωτικά πιο αποτελεσματικές στην εφαρμογή σε αυτό το μοντέλο κόστους από ό,τι στο τυπικό. Το πρώτο παράδειγμα κβαντικού προυπολογισμού, με βάση την εκθετική μήτρα πυκνότητας, θα μπορούσε να προσφέρει ένα εκθετικό πλεονέκτημα υπό ορισμένες συνθήκες. Το δεύτερο παράδειγμα χρησιμοποιεί μια παραλλαγή της τηλεμεταφοράς πύλης για να επιτύχει ένα τετραγωνικό πλεονέκτημα σε σύγκριση με την απευθείας εφαρμογή των ενιαίων. Αυτά τα παραδείγματα υποδεικνύουν ότι ο κβαντικός προυπολογισμός μπορεί να προσφέρει μια νέα αρένα για την αναζήτηση κβαντικού πλεονεκτήματος.

► Δεδομένα BibTeX

► Αναφορές

[1] S Aaronson. Περιορισμοί κβαντικών συμβουλών και μονόδρομης επικοινωνίας. Σε Πρακτικά. 19th IEEE Annual Conference on Computational Complexity, 2004, σελίδες 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/​ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson και Andris Ambainis. Σχέση. In Proceedings of the σαράντα έβδομο ετήσιο συμπόσιο ACM on Theory of Computing, STOC '15, σελίδες 307–316, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 14 Ιουνίου 2015. ACM. ISBN 9781450335362. 10.1145/​2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson και Guy N Rothblum. Απαλή μέτρηση κβαντικών καταστάσεων και διαφορική ιδιωτικότητα. 18 Απριλίου 2019. URL http://arxiv.org/​abs/​1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo και Hartmut Neven. Εστίαση πέρα ​​από τις τετραγωνικές επιταχύνσεις για κβαντικό πλεονέκτημα διορθωμένο με σφάλματα. PRX quantum, 2 (1): 010103, 29 Μαρτίου 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein και Tanja Lange. Ανομοιόμορφες ρωγμές στο σκυρόδεμα: Η δύναμη του ελεύθερου προυπολογισμού. Στο Advances in Cryptology – ASIACRYPT 2013, Lecture notes in computer science, σελίδες 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/​978-3-642-42045-0_17.
https:/​/​doi.org/​10.1007/​978-3-642-42045-0_17

[6] Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean και Ryan Babbush. Qubitization αυθαίρετης βάσης κβαντικής χημείας με μόχλευση της αραιότητας και της παραγοντοποίησης χαμηλής κατάταξης. 6 Φεβρουαρίου 2019. URL https:/​/​doi.org/​10.22331/​q-2019-12-02-208.
https:/​/​doi.org/​10.22331/​q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe και Seth Lloyd. Κβαντική μηχανική μάθηση. Nature, 549 (7671): 195–202, Σεπτέμβριος 2017. ISSN 0028-0836,1476-4687. 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi και Alexei Kitaev. Καθολικός κβαντικός υπολογισμός με ιδανικές πύλες cliford και θορυβώδεις αγκυλώσεις. Phys. Αναθ. Α, 71 (2): 022316, 22 Φεβρουαρίου 2005. ISSN 1050-2947,1094-1622. 10.1103/​physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergey Bravyi και Dmitri Maslov. Τα κυκλώματα χωρίς Hadamard εκθέτουν τη δομή της ομάδας Clifford. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, Ιούλιος 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell και Joe O'Gorman. Μια αποτελεσματική προσέγγιση μαγικής κατάστασης σε περιστροφές μικρής γωνίας. 14 Μαρτίου 2016. URL https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007.
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang και Jerry Li. Εκθετικοί διαχωρισμοί μεταξύ μάθησης με και χωρίς κβαντική μνήμη. Το 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Φεβρουάριος 2022. 10.1109/​focs52979.2021.00063.
https://doi.org/​10.1109/​focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari και Rolando D Somma. Κβαντικός αλγόριθμος για συστήματα γραμμικών εξισώσεων με εκθετικά βελτιωμένη εξάρτηση από την ακρίβεια. SIAM J. Comput., 46 (6): 1920–1950, 1 Ιανουαρίου 2017. ISSN 0097-5397. 10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik και Yoshihisa Yamamoto. Ταχύτερη προσομοίωση κβαντικής χημείας σε κβαντικούς υπολογιστές με ανοχή σε σφάλματα. New J. Phys., 14 (11): 115023, 27 Νοεμβρίου 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​11/​115023.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023

[14] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush και Dominic W Berry. Επιλύτης κβαντικών γραμμικών συστημάτων βέλτιστης κλίμακας μέσω διακριτού αδιαβατικού θεωρήματος. PRX quantum, 3 (4): 040303, 7 Οκτωβρίου 2022. ISSN 2691-3399. 10.1103/​prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang και Jarrod R McClean. Επανεξέταση της αποκβαντικοποίησης και του κβαντικού πλεονεκτήματος στις μαθησιακές εργασίες. 1 Δεκεμβρίου 2021. URL http://arxiv.org/​abs/​2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman και Anirudh Krishna. Διαγώνιες πύλες στην ιεραρχία του cliford. Phys. Αναθ. Α, 95 (1), 26 Ιανουαρίου 2017. ISSN 2469-9926,2469-9934. 10.1103/​physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone και Sam Gutmann. Ένας κβαντικός αλγόριθμος βελτιστοποίησης κατά προσέγγιση. 14 Νοεμβρίου 2014. URL http://arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Βέλτιστος χρονικά κβαντικός υπολογισμός. 17 Οκτωβρίου 2012. URL http://arxiv.org/​abs/​1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian και François Le Gall. Αποκβαντοποίηση του μετασχηματισμού κβαντικής μοναδικής τιμής: σκληρότητα και εφαρμογές στην κβαντική χημεία και την εικασία του κβαντικού PCP. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, σελίδες 19–32, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 9 Ιουνίου 2022. ACM. ISBN 9781450392648. 10.1145/​3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney και Martin Ekerå. Πώς να συνυπολογίσετε ακέραιους αριθμούς RSA 2048 bit σε 8 ώρες χρησιμοποιώντας 20 εκατομμύρια θορυβώδη qubits. Quantum, 5 (433): 433, 15 Απριλίου 2021. ISSN 2521-327X. 10.22331/​q-2021-04-15-433.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

[21] Craig Gidney και Austin G Fowler. Ευέλικτη διάταξη υπολογισμών επιφανειακού κώδικα χρησιμοποιώντας καταστάσεις AutoCCZ. 21 Μαΐου 2019. URL http://arxiv.org/​abs/​1905.08916.
arXiv: 1905.08916

[22] András Gilyén και Alexander Poremba. Βελτιωμένοι κβαντικοί αλγόριθμοι για την εκτίμηση πιστότητας. 29 Μαρτίου 2022. URL http://arxiv.org/​abs/​2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman και Isaac L Chuang. Η κβαντική τηλεμεταφορά είναι ένα παγκόσμιο υπολογιστικό πρωτόγονο. 2 Αυγούστου 1999. URL https://​/​doi.org/​10.1038/​46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady και Ali Kemal Sinop. Γρήγορη κατά προσέγγιση τυχαία τμηματοποίηση περιπατητή χρησιμοποιώντας προυπολογισμό ιδιοδιανύσματος. Το 2008 IEEE Conference on Computer Vision and Pattern Recognition, σελίδες 1–8. IEEE, Ιούνιος 2008. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Λοβ Κ Γκρόβερ. Ένας γρήγορος κβαντομηχανικός αλγόριθμος για αναζήτηση βάσεων δεδομένων. Στα Πρακτικά του εικοστού όγδοου ετήσιου συμποσίου ACM on Theory of computing – STOC '96, STOC '96, σελίδες 212–219, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 1996. ACM Press. ISBN 9780897917858. 10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Οι Aram W Harrow, Avinatan Hassidim και Seth Lloyd. Κβαντικός αλγόριθμος για γραμμικά συστήματα εξισώσεων. Phys. Rev. Lett., 103 (15): 150502, 9 Οκτωβρίου 2009. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill και Jarrod R McClean. Κβαντικό πλεονέκτημα στη μάθηση από πειράματα. Science, 376 (6598): 1182–1186, 10 Ιουνίου 2022. ISSN 0036-8075,1095-9203. 10.1126/​science.abn7293.
https://doi.org/​10.1126/​science.abn7293

[28] Κόντι Τζόουνς. Πρωτόκολλα απόσταξης για καταστάσεις Fourier στον κβαντικό υπολογισμό. 12 Μαρτίου 2013. URL http://arxiv.org/​abs/​1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Ένα κβαντικό πλεονέκτημα για ένα φυσικό πρόβλημα ροής. Το 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), σελίδες 897–908. IEEE, Φεβρουάριος 2022. 10.1109/​focs52979.2021.00091.
https://doi.org/​10.1109/​focs52979.2021.00091

[30] Richard M Karp και Richard J Lipton. Μερικές συνδέσεις μεταξύ ανομοιόμορφων και ομοιόμορφων κλάσεων πολυπλοκότητας. In Proceedings of the 80th ετήσιο ACM Symposium on Theory of computing – STOC '80, STOC '302, σελίδες 309–28, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 1980 Απριλίου 9780897910170. ACM Press. ISBN 10.1145. 800141.804678/​XNUMX.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols και Theodore J Yoder. Χαμιλτονιανή προσομοίωση με βέλτιστη πολυπλοκότητα δείγματος. Npj Quantum Inf., 3 (1): 1–7, 30 Μαρτίου 2017. ISSN 2056-6387,2056-6387. 10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[32] Φρανσουά Λε Γκαλ. Εκθετικός διαχωρισμός κβαντικής και κλασικής διαδικτυακής πολυπλοκότητας χώρου. In Proceedings of the δέκατο όγδοο ετήσιο συμπόσιο ACM για τον Παραλληλισμό σε αλγόριθμους και αρχιτεκτονικές, SPAA '06, σελίδες 67–73, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 30 Ιουλίου 2006. ACM. ISBN 9781595934529. 10.1145/​1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin και Yu Tong. Βέλτιστο πολυωνυμικό φιλτράρισμα κβαντικής ιδιοκατάστασης με εφαρμογή στην επίλυση κβαντικών γραμμικών συστημάτων. Quantum, 4 (361): 361, 11 Νοεμβρίου 2020. ISSN 2521-327X. 10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[34] Ντάνιελ Λιτίνσκι. Απόσταξη μαγικής κατάστασης: Όχι τόσο δαπανηρή όσο νομίζετε. Quantum, 3 (205): 205, 2 Δεκεμβρίου 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[35] Ντάνιελ Λιτίνσκι. Ένα παιχνίδι επιφανειακών κωδίκων: Κβαντικοί υπολογιστές μεγάλης κλίμακας με χειρουργική πλέγματος. Quantum, 3 (128): 128, 5 Μαρτίου 2019β. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni και Patrick Rebentrost. Ανάλυση κβαντικής κύριας συνιστώσας. Nat. Phys., 10 (9): 631–633, 27 Σεπτεμβρίου 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

[37] John M Martyn, Zane M Rossi, Andrew K Tan και Isaac L Chuang. Μεγάλη ενοποίηση κβαντικών αλγορίθμων. PRX quantum, 2 (4): 040203, 3 Δεκεμβρίου 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian και Seth Lloyd. Καθολικός κβαντικός εξομοιωτής. 8 Ιουνίου 2016. URL http://arxiv.org/​abs/​1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher και FK Wilhelm. Γραμμικές και λογαριθμικές συνθέσεις χρόνου κβαντικών τελεστών πολλών σωμάτων. Phys. Rev. Lett., 119 (16): 160503, 20 Οκτωβρίου 2017. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Οπτικός κβαντικός υπολογισμός με χρήση καταστάσεων συστάδων. Phys. Rev. Lett., 93 (4): 040503, 23 Ιουλίου 2004. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Bryan O'Gorman, William J Huggins, Eleanor G Rieffel και K Birgitta Whaley. Γενικευμένα δίκτυα ανταλλαγής για βραχυπρόθεσμο κβαντικό υπολογισμό. 13 Μαΐου 2019. URL http://arxiv.org/​abs/​1905.05118.
arXiv: 1905.05118

[42] Paul Pham και Krysta M Svore. Μια δισδιάστατη κβαντική αρχιτεκτονική πλησιέστερου γείτονα για παραγοντοποίηση σε πολυλογαριθμικό βάθος. 2 Ιουλίου 27. URL http://arxiv.org/​abs/​2012.
arXiv: 1207.6655

[43] R Raussendorf και HJ Briegel. Ένας μονόδρομος κβαντικός υπολογιστής. Phys. Rev. Lett., 86 (22): 5188–5191, 28 Μαΐου 2001. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven και Ryan Babbush. Σύνταξη κβαντικών ευρετικών ανοχής σε σφάλματα για συνδυαστική βελτιστοποίηση. PRX quantum, 1 (2): 020312, 9 Νοεμβρίου 2020. ISSN 2691-3399. 10.1103/​prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd και Michael J Bremner. Χρονικά μη δομημένος κβαντικός υπολογισμός. Proc. Μαθηματικά. Phys. Eng. Sci., 465 (2105): 1413–1439, 8 Μαΐου 2009. ISSN 1364-5021,1471-2946. 10.1098/​rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz και John Snyder. Προυπολογισμένη μεταφορά ακτινοβολίας για απόδοση σε πραγματικό χρόνο σε δυναμικά περιβάλλοντα φωτισμού χαμηλής συχνότητας. Στα Πρακτικά του 29ου ετήσιου συνεδρίου για τα γραφικά υπολογιστών και τις διαδραστικές τεχνικές, SIGGRAPH '02, σελίδες 527–536, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 1 Ιουλίου 2002. ACM. ISBN 9781581135213. 10.1145/​566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] Τζέιμς Ε Σμιθ. Μια μελέτη των στρατηγικών πρόβλεψης κλάδου. Στα 25 χρόνια των διεθνών συμποσίων για την αρχιτεκτονική υπολογιστών (επιλεγμένες εργασίες), ISCA '98, σελίδες 202–215, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 1 Αυγούστου 1998. ACM. ISBN 9781581130584. 10.1145/​285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma και Yiğit Subaşı. Πολυπλοκότητα επαλήθευσης κβαντικής κατάστασης στο πρόβλημα των κβαντικών γραμμικών συστημάτων. PRX quantum, 2 (1): 010315, 27 Ιανουαρίου 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Διόρθωση κβαντικού λάθους για κβαντικές μνήμες. Rev. Mod. Phys., 87 (2): 307–346, 7 Απριλίου 2015. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung και Isaac L Chuang. Μεθοδολογία κατασκευής κβαντικής λογικής πύλης. Phys. Αναθ. Α, 62 (5), 18 Οκτωβρίου 2000. ISSN 1050-2947,1094-1622. 10.1103/​physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Αναφέρεται από

[1] Dar Gilboa και Jarrod R. McClean, “Exponential Quantum Communication Advantage in Distributed Learning”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost και Mikel Sanz, «Κβαντική εκθέτηση μήτρας πυκνότητας υποβοηθούμενη από κβαντική κατά προσέγγιση προσέγγιση». arXiv: 2311.11751, (2023).

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2024-02-22 13:13:08). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

Δεν ήταν δυνατή η λήψη Crossref αναφερόμενα δεδομένα κατά την τελευταία προσπάθεια 2024-02-22 13:13:06: Δεν ήταν δυνατή η λήψη των αναφερόμενων δεδομένων για το 10.22331 / q-2024-02-22-1264 από την Crossref. Αυτό είναι φυσιολογικό αν το DOI καταχωρήθηκε πρόσφατα.

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal