Τμήμα Επιστήμης Υπολογιστών, Πανεπιστήμιο του Τέξας στο inστιν, inστιν, TX 78712, ΗΠΑ
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Μια κορυφαία πρόταση για την επαλήθευση βραχυπρόθεσμων πειραμάτων κβαντικής υπεροχής σε θορυβώδη τυχαία κβαντικά κυκλώματα είναι η γραμμική συγκριτική αξιολόγηση εγκάρσιας εντροπίας. Για ένα κβαντικό κύκλωμα $ C $ σε $ n $ qubits και ένα δείγμα $ z σε {0,1}^n $, το σημείο αναφοράς περιλαμβάνει τον υπολογισμό $ | langle z | C | 0^n rangle |^2 $, δηλαδή την πιθανότητα μέτρησης $ z $ από την κατανομή εξόδου $ C $ σε όλες τις μηδενικές εισόδους. Υπό μια ισχυρή εικασία σχετικά με την κλασική σκληρότητα της εκτίμησης των πιθανοτήτων εξόδου των κβαντικών κυκλωμάτων, κανένας κλασικός αλγόριθμος πολυωνυμικού χρόνου με $ C $ δεν μπορεί να εξάγει μια συμβολοσειρά $ z $ έτσι ώστε $ | langle z | C | 0^nrangle |^2 $ είναι σημαντικά μεγαλύτερο από $ frac {1} {2^n} $ (Aaronson and Gunn, 2019). Από την άλλη πλευρά, για ένα τυχαίο κβαντικό κύκλωμα $ C $, η δειγματοληψία $ z $ από την κατανομή εξόδου $ C $ επιτυγχάνει $ | langle z | C | 0^nrangle |^2 περίπου frac {2} {2^n} $ κατά μέσο όρο (Arute et al., 2019).
Σε αναλογία με την ανισότητα Tsirelson από κβαντικούς μη τοπικούς συσχετισμούς, ρωτάμε: μπορεί ένας κβαντικός αλγόριθμος πολυωνυμικού χρόνου να κάνει σημαντικά καλύτερα από $ frac {2} {2^n} $; Μελετάμε αυτήν την ερώτηση στο μοντέλο ερωτήματος (ή μαύρου πλαισίου), όπου ο κβαντικός αλγόριθμος έχει πρόσβαση χρησμού σε $ C $. Δείχνουμε ότι, για οποιοδήποτε $ varepsilon ge frac {1} {mathrm {poly} (n)} $, βγάζοντας ένα δείγμα $ z $ έτσι ώστε $ | langle z | C | 0^nrangle |^2 ge frac {2 + varepsilon} {2^n} $ κατά μέσο όρο απαιτεί τουλάχιστον $ Omegaleft (frac {2^{n/4}} {mathrm {poly} (n)} right) $ queries to $ C $, but not more than $ Oleft (2^{n/3} δεξιά) $ ερωτήματα σε $ C $, αν $ C $ είναι είτε Haar-random $ n $ -qubit unitary, είτε κανονικό μαντείο προετοιμασίας κατάστασης για Haar-random $ n $ -qubit κατάσταση. Δείχνουμε επίσης ότι όταν δείγματα $ C $ από τη διανομή Fourier μιας τυχαίας συνάρτησης Boolean, ο αφελής αλγόριθμος που λαμβάνει δείγματα από $ C $ είναι ο βέλτιστος αλγόριθμος 1 ερωτήματος για τη μεγιστοποίηση του $ | langle z | C | 0^nrangle |^2 $ κατά μέσο όρο.
Δημοφιλή περίληψη
Υποστηρίζουμε ότι αυτό το ανώτατο όριο στη δύναμη των κλασικών αλγορίθμων για το Γραμμικό XEB είναι ανάλογο με την ανισότητα Bell σε μη τοπικούς συσχετισμούς: και τα δύο αποτυπώνουν εγγενή όρια στη δύναμη της κλασικής πληροφορίας και στον υπολογισμό που μπορεί να παραβιαστούν στην κβαντική ρύθμιση. Με κίνητρο αυτή τη σύνδεση, ρωτάμε: ποιο είναι το ανάλογο της κβαντικής υπεροχής της ανισότητας Tsirelson; Δηλαδή, ποια είναι η υψηλότερη Γραμμική βαθμολογία XEB που μπορεί να επιτευχθεί με έναν αποτελεσματικό κβαντικό αλγόριθμο; Δίνουμε στοιχεία ότι ο αφελής κβαντικός αλγόριθμος για την υπέρβαση του δείκτη αναφοράς είναι ουσιαστικά ο βέλτιστος από αυτή την άποψη.
► Δεδομένα BibTeX
► Αναφορές
[1] Σκοτ Άρονσον. Δειγματοληψία τυχαίου κυκλώματος: Σκέψεις και ανοιχτά προβλήματα. The Quantum Wave in Computing, 2020. URL https://simons.berkeley.edu/ Talk/tbd-124.
https://simons.berkeley.edu/ talk/tbd-124
[2] Scott Aaronson και Lijie Chen. Πολυπλοκότητα-Θεωρητικά θεμέλια πειραμάτων κβαντικής υπεροχής. In Ryan O'Donnell, editor, 32th Computational Complexity Conference (CCC 2017), τόμος 79 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 22: 1–22: 67, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.22. URL http://drops.dagstuhl.de/ opus/volltexte/2017/7527.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.22
http: / / drop.dagstuhl.de/ opus / volltexte / 2017/7527
[3] Ο Scott Aaronson και ο Sam Gunn. Σχετικά με την κλασική σκληρότητα της παραποίησης της γραμμικής συγκριτικής αξιολόγησης διασταυρούμενης εντροπίας. Theory of Computing, 16 (11): 1–8, 2020. 10.4086/toc.2020.v016a011. URL http://www.theoryofcomputing.org/ articles/v016a011.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
http: / / www.theoryofcomputing.org/ άρθρα / v016a011
[4] Scott Aaronson, Robin Kothari, William Kretschmer και Justin Thaler. Κβαντικά χαμηλότερα όρια για κατά προσέγγιση καταμέτρηση μέσω πολυώνυμων Laurent. In Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020), τόμος 169 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 7: 1–7: 47, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Το ISBN 978-3-95977-156-6. 10.4230/LIPIcs.CCC.2020.7. Διεύθυνση URL https://drops.dagstuhl.de/ opus/volltexte/2020/12559.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2020.7
https://drops.dagstuhl.de/ opus/volltexte/2020/12559
[5] Dorit Aharonov, Alexei Kitaev και Noam Nisan. Κβαντικά κυκλώματα με μικτές καταστάσεις. In Proceedings of the Thirtieth Annual Symposium ACM on Theory of Computing, STOC '98, σελίδα 20–30, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919629. 10.1145/276698.276708. URL https://doi.org/ 10.1145/276698.276708.
https: / / doi.org/ 10.1145 / 276698.276708
[6] Άντρης Αμπαίνης. Κατανόηση κβαντικών αλγορίθμων μέσω πολυπλοκότητας ερωτήματος. Στα Πρακτικά του Διεθνούς Συνεδρίου Μαθηματικών 2018, τόμος 3, σελίδες 3249–3270, 2018. 10.1142/9789813272880_0181.
https: / / doi.org/ 10.1142 / 9789813272880_0181
[7] Andris Ambainis, Loïck Magnin, Martin Roetteler και Jeremie Roland. Αντίπαλοι με τη συμμετρία για την παραγωγή κβαντικής κατάστασης. Στα Πρακτικά του 2011ου Ετήσιου Συνεδρίου 26 IEEE on Computational Complexity, CCC '11, σελίδα 167–177, ΗΠΑ, 2011. IEEE Computer Society. ISBN 9780769544113. 10.1109/CCC.2011.24. URL https://doi.org/ 10.1109/CCC.2011.24.
https: / / doi.org/ 10.1109 / CCC.2011.24
[8] Andris Ambainis, Ansis Rosmanis και Dominique Unruh. Κβαντικές επιθέσεις σε κλασικά συστήματα απόδειξης: Η σκληρότητα της κβαντικής επανατύλιξης. Στα Πρακτικά του 2014ου Ετήσιου Συμποσίου IEEE 55 για τα Θεμέλια της Επιστήμης των Υπολογιστών, FOCS '14, σελίδα 474–483, ΗΠΑ, 2014. IEEE Computer Society. ISBN 9781479965175. 10.1109/FOCS.2014.57. URL https://doi.org/ 10.1109/FOCS.2014.57.
https: / / doi.org/ 10.1109 / FOCS.2014.57
[9] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis και Ronald de Wolf. Συλλέκτης Κβαντικών Κουπονιών. Στο Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), τόμος 158 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 10: 1–10: 17, Dagstuhl, Γερμανία, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230/LIPIcs.TQC.2020.10. Διεύθυνση URL https://drops.dagstuhl.de/ opus/volltexte/2020/12069.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
https://drops.dagstuhl.de/ opus/volltexte/2020/12069
[10] Frank Arute, Kunal Arya, Ryan Babbush, et al. Κβαντική υπεροχή χρησιμοποιώντας προγραμματιζόμενο υπεραγώγιμο επεξεργαστή. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5. URL https://doi.org/ 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[11] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca και Ronald de Wolf. Κβαντικά κατώτερα όρια κατά πολυώνυμα. J. ACM, 48 (4): 778–797, Ιούλιος 2001. ISSN 0004-5411. 10.1145/502090.502097. URL https://doi.org/ 10.1145/502090.502097.
https: / / doi.org/ 10.1145 / 502090.502097
[12] Τζον Μπελ. Για το παράδοξο Einstein-Podolsky-Rosen. Physics, 1: 195–200, Nov 1964. 10.1103/PhysicsPhysiqueFizika.1.195. URL https://link.aps.org/ doi/10.1103/PhysicsPhysiqueFizika.1.195.
https: / / doi.org/ 10.1103 / PhysicsPhysiqueFizika.1.195
[13] Αλεξάντρς Μπέλοβς. Παραλλαγές στον κβαντικό αντίπαλο, 2015.
arXiv: 1504.06943
[14] Αλεξάντρς Μπέλοβς και Άνσις Ροσμάνης. Σφιχτό κβαντικό κατώτερο όριο για κατά προσέγγιση καταμέτρηση με κβαντικές καταστάσεις, 2020.
arXiv: 2002.06879
[15] Fernando GSL Brandão, Aram W. Harrow και Michał Horodecki. Τα τοπικά τυχαία κβαντικά κυκλώματα είναι κατά προσέγγιση πολυωνυμικά σχέδια. Επικοινωνίες στη Μαθηματική Φυσική, 346 (2): 397–434, 2016. 10.1007/s00220-016-2706-8. URL https://doi.org/ 10.1007/s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8
[16] Gilles Brassard, Peter Høyer και Alain Tapp. Κβαντική κρυπτανάλυση των λειτουργιών κατακερματισμού και χωρίς νύχια. SIGACT News, 28 (2): 14–19, Ιούνιος 1997. ISSN 0163-5700. 10.1145/261342.261346. URL https://doi.org/ 10.1145/261342.261346.
https: / / doi.org/ 10.1145 / 261342.261346
[17] Gilles Brassard, Peter Høyer, Michele Mosca και Alain Tapp. Ενίσχυση και εκτίμηση κβαντικού πλάτους. Στο Quantum Computation and Quantum Information, τόμος 305 των Σύγχρονων Μαθηματικών, σελίδες 53–74. American Mathematical Society, 2002. ISBN 9780821821404. 10.1090/conm/305.
https: / / doi.org/ 10.1090 / conm / 305
[18] Mark Bun και Justin Thaler. Διπλά χαμηλότερα όρια για κατά προσέγγιση βαθμό και ανισότητες Markov-Bernstein. Inf Comput., 243 (C): 2–25, Αύγουστος 2015. ISSN 0890-5401. 10.1016/j.ic.2014.12.003. URL https://doi.org/ 10.1016/j.ic.2014.12.003.
https: / / doi.org/ 10.1016 / j.ic.2014.12.003
[19] Boris Cirel'son (Tsirelson). Κβαντικές γενικεύσεις της ανισότητας του Μπελ. Επιστολές στη Μαθηματική Φυσική, 4 (2): 93–100, 1980. 10.1007/BF00417500. Διεύθυνση URL https://doi.org/ 10.1007/BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[20] John F. Clauser, Michael A. Horne, Abner Shimony και Richard A. Holt. Προτεινόμενο πείραμα για τη δοκιμή τοπικών θεωριών κρυφών μεταβλητών. Φυσ. Rev. Lett., 23: 880–884, Οκτ 1969. 10.1103/PhysRevLett.23.880. URL https://link.aps.org/ doi/10.1103/PhysRevLett.23.880.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[21] Richard Cleve, Peter Høyer, Benjamin Toner και John Watrous. Συνέπειες και όρια μη τοπικών στρατηγικών. Στα Πρακτικά του 19ου Ετήσιου Συνεδρίου IEEE για την Υπολογιστική Πολυπλοκότητα, CCC '04, σελίδα 236–249, ΗΠΑ, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/CCC.2004.1313847.
https: / / doi.org/ 10.1109 / CCC.2004.1313847
[22] Aram Harrow και Saeed Mehraban. Κατά προσέγγιση ενιαία t-σχέδια με σύντομα τυχαία κβαντικά κυκλώματα χρησιμοποιώντας πύλες πλησιέστερου γείτονα και μεγάλης εμβέλειας, 2018.
arXiv: 1809.06957
[23] Norman L. Johnson και Samuel Kotz. Μοντέλα Urn και εφαρμογή τους: μια προσέγγιση στη σύγχρονη διακριτή θεωρία πιθανοτήτων. Wiley, 1977. ISBN 9780471446309.
[24] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols και Theodore J. Yoder. Προσομοίωση Hamiltonian με βέλτιστη πολυπλοκότητα δείγματος. npj Quantum Information, 3 (1): 13, 2017. 10.1038/s41534-017-0013-7. URL https://doi.org/ 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7
[25] Γουίλιαμ Κρέτσμερ. Η κβαντική υπεροχή Tsirelson ανισότητα. Στο James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), τόμος 185 των Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 13: 1–13: 13, Dagstuhl, Γερμανία, 2021. Schloss Dagstuhl– Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230/LIPIcs.ITCS.2021.13. Διεύθυνση URL https://drops.dagstuhl.de/ opus/volltexte/2021/13552.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.13
https://drops.dagstuhl.de/ opus/volltexte/2021/13552
[26] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek και Mario Szegedy. Πολυπλοκότητα κβαντικού ερωτήματος μετατροπής κατάστασης. Στα Πρακτικά του 2011ου Ετήσιου Συμποσίου 52 IEEE για τα Θεμέλια της Επιστήμης των Υπολογιστών, FOCS '11, σελίδα 344–353, ΗΠΑ, 2011. IEEE Computer Society. ISBN 9780769545714. 10.1109/FOCS.2011.75. URL https://doi.org/ 10.1109/FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75
[27] Nathan Lindzey και Ansis Rosmanis. Σφιχτά χαμηλότερο όριο για μη συνεκτική διαγραφή δείκτη. Στο Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), τόμος 151 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 59: 1–59: 37, Dagstuhl, Γερμανία, 2020. Schloss Dagstuhl – Leibniz- Zentrum fuer Informatik. ISBN 978-3-95977-134-4. 10.4230/LIPIcs.ITCS.2020.59. Διεύθυνση URL https://drops.dagstuhl.de/ opus/volltexte/2020/11744.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2020.59
https://drops.dagstuhl.de/ opus/volltexte/2020/11744
[28] Frederic Magniez, Ashwin Nayak, Jeremie Roland και Miklos Santha. Αναζήτηση μέσω κβαντικής βόλτας. In Proceedings of the Thirty-Ninth Annual Symposium ACM on Theory of Computing, STOC '07, σελίδα 575–584, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/1250790.1250874. URL https://doi.org/ 10.1145/1250790.1250874.
https: / / doi.org/ 10.1145 / 1250790.1250874
[29] Ράιαν Ο 'Ντόνελ. Ανάλυση των συναρτήσεων Boolean. Cambridge University Press, ΗΠΑ, 2014. ISBN 1107038324. 10.1017/CBO9781139814782.
https: / / doi.org/ 10.1017 / CBO9781139814782
[30] Martin Raab και Angelika Steger. "Μπάλες σε κάδους" - μια απλή και σφιχτή ανάλυση. In Proceedings of the Second International Workshop on Randomization and Approximing Techniques in Computer Science, RANDOM '98, pages 159–170, Berlin, Heidelberg, 1998. Springer-Verlag. ISBN 354065142X. 10.1007/3-540-49543-6_13.
https://doi.org/10.1007/3-540-49543-6_13
[31] Ben W. Reichardt. Αντανακλάσεις για αλγόριθμους κβαντικών ερωτημάτων. In Proceedings of the Twenty-Second Annual Symposium ACM-SIAM on Discrete Algorithms, SODA '11, σελίδα 560–569, ΗΠΑ, 2011. Society for Industrial and Applied Mathematics. 10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[32] Alfréd Rényi. Σχετικά με τη θεωρία της στατιστικής παραγγελίας. Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191–231, 1953. 10.1007/BF02127580. Διεύθυνση URL https://doi.org/ 10.1007/BF02127580.
https: / / doi.org/ 10.1007 / BF02127580
Αναφέρεται από
[1] Daniel Stilck França και Raul Garcia-Patron, «Ένα παιχνίδι κβαντικού πλεονεκτήματος: σύνδεση επαλήθευσης και προσομοίωσης», arXiv: 2011.12173.
[2] Nicholas LaRacuente, "Quantum Oracle Separations from Complex but Easily Specified States", arXiv: 2104.07247.
[3] Scott Aaronson, «Ανοιχτά προβλήματα που σχετίζονται με την πολυπλοκότητα της κβαντικής ερώτησης», arXiv: 2109.06917.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2021-10-07 11:15:15). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
Δεν ήταν δυνατή η λήψη Crossref αναφερόμενα δεδομένα κατά την τελευταία προσπάθεια 2021-10-07 11:15:13: Δεν ήταν δυνατή η λήψη των αναφερόμενων δεδομένων για το 10.22331 / q-2021-10-07-560 από την Crossref. Αυτό είναι φυσιολογικό αν το DOI καταχωρήθηκε πρόσφατα.
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
Πλάτωνας. Επανεκτίμησε το Web3. Ενισχυμένη ευφυΐα δεδομένων.
Κάντε κλικ εδώ για πρόσβαση.
