Βασικές κβαντικές υπορουτίνες: Εύρεση πολλαπλών σημειωμένων στοιχείων και άθροιση αριθμών

Αναδημοσίευση από τον Πλάτωνα

Ακολουθούν: 0

Βασικές κβαντικές υπορουτίνες: εύρεση πολλαπλών επισημασμένων στοιχείων και άθροιση αριθμών PlatoBlockchain Data Intelligence. Κάθετη αναζήτηση. Ολα συμπεριλαμβάνονται.

Joran van Apeldoorn¹, Σάντερ Γκρίμπλινγκ², να Harold Nieuwboer³

¹IViR και QuSoft, Πανεπιστήμιο του Άμστερνταμ, Ολλανδία
²Τμήμα Οικονομετρίας και Επιχειρησιακής Έρευνας, Πανεπιστήμιο Tilburg, Tilburg, Ολλανδία
³Korteweg–de Vries Institute for Mathematics and QuSoft, Πανεπιστήμιο του Άμστερνταμ, Ολλανδία και Σχολή Επιστήμης Υπολογιστών, Πανεπιστήμιο Ruhr Bochum, Γερμανία και Τμήμα Μαθηματικών Επιστημών, Πανεπιστήμιο της Κοπεγχάγης, Δανία

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

Περίληψη

Δείχνουμε πώς να βρείτε όλα τα στοιχεία που έχουν επισημανθεί $k$ σε μια λίστα μεγέθους $N$ χρησιμοποιώντας τον βέλτιστο αριθμό $O(sqrt{N k})$ των κβαντικών ερωτημάτων και μόνο μια πολυλογαριθμική επιβάρυνση στην πολυπλοκότητα της πύλης, στη ρύθμιση όπου κάποιος έχει μικρή κβαντική μνήμη. Οι προηγούμενοι αλγόριθμοι είτε είχαν έναν συντελεστή $k$ στην πολυπλοκότητα της πύλης είτε είχαν έναν επιπλέον παράγοντα $log(k)$ στην πολυπλοκότητα του ερωτήματος.
Στη συνέχεια εξετάζουμε το πρόβλημα της εύρεσης μιας πολλαπλασιαστικής $delta$-προσέγγισης του $s = sum_{i=1}^N v_i$ όπου $v=(v_i) σε [0,1]^N$, δεδομένης πρόσβασης κβαντικού ερωτήματος σε μια δυαδική περιγραφή του $v$. Δίνουμε έναν αλγόριθμο που το κάνει, με πιθανότητα τουλάχιστον $1-rho$, χρησιμοποιώντας κβαντικά ερωτήματα $O(sqrt{N log(1/rho) / delta})$ (κάτω από ήπιες υποθέσεις για $rho$). Αυτό βελτιώνει τετραγωνικά την εξάρτηση από $1/δέλτα$ και $log(1/rho)$ σε σύγκριση με μια απλή εφαρμογή εκτίμησης πλάτους. Για να αποκτήσουμε τη βελτιωμένη εξάρτηση $log(1/rho)$ χρησιμοποιούμε το πρώτο αποτέλεσμα.

► Δεδομένα BibTeX

@article{vanApeldoorn2024basicquantum, doi = {10.22331/q-2024-03-14-1284}, url = {https://doi.org/10.22331/q-2024-03-14-1284}, τίτλος = {Βασικές κβαντικές υπορουτίνες: εύρεση πολλαπλών σημειωμένων στοιχείων και άθροιση αριθμών}, συγγραφέας = {van Apeldoorn, Joran and Gribling, Sander and Nieuwboer, Harold}, journal = {{Quantum}}, issn = {2521-327X}, εκδότης = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, όγκος = {8}, σελίδες = {1284}, μήνας = Μαρ, έτος = {2024} }

► Αναφορές

[1] Srinivasan Arunachalam και Ronald de Wolf. Βελτιστοποίηση του αριθμού των πυλών στην κβαντική αναζήτηση. Quantum Info. Comput., 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell και P. Jodrá. Ακριβής Kolmogorov και συνολικές αποστάσεις διακύμανσης μεταξύ κάποιων γνωστών διακριτών κατανομών. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/JIA/2006/64307.
https://doi.org/10.1155/JIA/2006/64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter και Ronald de Wolf. Κβαντικοί αλγόριθμοι για κλιμάκωση μήτρας και εξισορρόπηση πινάκων. In Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), τόμος 198, σελίδες 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/LIPics.ICS.ICS.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] Σκοτ Άαρονσον και Πάτρικ Ραλ. Κβαντική κατά προσέγγιση μέτρηση, απλοποιημένη. Στο Symposium on Simplicity in Algorithms, σελίδες 24–32, 2020. doi:10.1137/1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer και Alain Tapp. Σφιχτά όρια στην κβαντική αναζήτηση. Fortschritte der Physik, 46(4–5):493–505, 1998. Προγενέστερη έκδοση στο Physcomp'96. arXiv:quant-ph/9605034.
arXiv: quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf και Christof Zalka. Όρια για κβαντικούς αλγόριθμους μικρού και μηδενικού σφάλματος. Στο 40th Annual Symposium on Foundations of Computer Science (FOCS'99), σελίδες 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca και Alain Tapp. Ενίσχυση και εκτίμηση κβαντικού πλάτους. Στο Quantum Computation and Quantum Information: A Millennium Volume, τόμος 305 του Contemporary Mathematics, σελίδες 53–74. American Mathematical Society, 2002. doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P

[8] Richard Brent και Paul Zimmermann. Modern Computer Arithmetic, τόμος 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even και Oded Goldreich. Κατώτερα όρια για αλγόριθμους δειγματοληψίας για την εκτίμηση του μέσου όρου. Information Processing Letters, 53(1):17–25, Ιανουάριος 1995. doi:10.1016/0020-0190(94)00171-T.
https://doi.org/10.1016/0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini και Leonard Wossnig. Κβαντική μηχανική μάθηση: μια κλασική προοπτική. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, Ιαν 2018. doi:10.1098/rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest και Clifford Stein. Εισαγωγή στους Αλγόριθμους. MIT Press, 4η έκδοση, 2022.

[12] P. Diaconis and D. Freedman. Πεπερασμένες ανταλλάξιμες ακολουθίες. The Annals of Probability, 8(4):745–764, 1980. URL: https://www.jstor.org/stable/2242823.
https: / / www.jstor.org/ stable / 2242823

[13] Christoph Dürr και Peter Høyer. Ένας κβαντικός αλγόριθμος για την εύρεση του ελάχιστου, 1996. doi:10.48550/arXiv.quant-ph/9607014.
https://doi.org/10.48550/arXiv.quant-ph/9607014
arXiv: quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer και Mehdi Mhalla. Κβαντική πολυπλοκότητα ερωτημάτων ορισμένων προβλημάτων γραφήματος. SIAM Journal on Computing, 35(6):1310–1328, Ιανουάριος 2006. doi:10.1137/050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby και Sheldon Ross. Ένας βέλτιστος αλγόριθμος για την εκτίμηση του Μόντε Κάρλο. SIAM Journal on Computing, 29(5):1484–1496, Ιανουάριος 2000. doi:10.1137/S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd και Lorenzo Maccone. Κβαντική μνήμη τυχαίας προσπέλασης. Physical Review Letters, 100(16), Απρίλιος 2008. doi:10.1103/physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling και Harold Nieuwboer. Βελτιωμένα κβαντικά κάτω και άνω όρια για κλιμάκωση πίνακα. In Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), τόμος 219, σελίδες 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/LIPIcs.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] Mart de Graaf και Ronald de Wolf. Σχετικά με τις κβαντικές εκδόσεις της αρχής του Γιάο. Στο 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), τόμος 2285 του Lecture Notes in Computer Science, σελίδες 347–358, Βερολίνο, Χαϊδελβέργη, 2002. Springer. doi: 10.1007/3-540-45841-7_28.
https://doi.org/10.1007/3-540-45841-7_28

[19] Λοβ Κ. Γκρόβερ. Ένας γρήγορος κβαντομηχανικός αλγόριθμος για αναζήτηση βάσεων δεδομένων. In Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), σελίδες 212–219, 1996. arXiv:quant-ph/9605043, doi:10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] Λοβ Κ. Γκρόβερ. Quantum telecomputation, 1997. Bell Labs Technical Memorandum ITD97-31630F. doi:10.48550/arXiv.quant-ph/9704012.
https://doi.org/10.48550/arXiv.quant-ph/9704012
arXiv: quant-ph / 9704012

[21] Λοβ Κ. Γκρόβερ. Ένα πλαίσιο για γρήγορους κβαντομηχανικούς αλγόριθμους. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC'98), σελίδες 53–62, 1998. arXiv:quant-ph/9711043, doi:10.1145/276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] Γιασίν Χαμούδη. Quantum Sub-Gaussian Mean Estimator. Στο 29th Annual European Symposium on Algorithms (ESA 2021), τόμος 204 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 50:1–50:17, 2021. doi:10.4230/LIPIcs.ESA.2021.50.
https://doi.org/10.4230/LIPIcs.ESA.2021.50

[23] Σβάντε Γιάνσον. Όρια ουράς για αθροίσματα γεωμετρικών και εκθετικών μεταβλητών. Statistics & Probability Letters, 135:1–6, 2018. doi:10.1016/j.spl.2017.11.017.
https://doi.org/10.1016/j.spl.2017.11.017

[24] Ντόναλντ Έρβιν Κνουθ. The Art of Computer Programming, τόμος III. Addison-Wesley, 2nd edition, 1998. URL: https://www.worldcat.org/oclc/312994415.
https://www.worldcat.org/oclc/312994415

[25] Robin Kothari και Ryan O'Donnell. Μέση εκτίμηση όταν έχετε τον πηγαίο κώδικα. ή, κβαντικές μέθοδοι Monte Carlo. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), σελίδες 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen και Isaac L. Chuang. Κβαντικός υπολογισμός και κβαντικές πληροφορίες. Cambridge University Press, 2002.

[27] Ashwin Nayak και Felix Wu. Η πολυπλοκότητα του κβαντικού ερωτήματος της προσέγγισης της διάμεσης και των σχετικών στατιστικών. In Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), σελίδες 384–393, 1999. arXiv:quant-ph/9804066, doi:10.1145/301250.301349
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] B. Roos. Διωνυμική προσέγγιση στη διωνυμική κατανομή Poisson: Η επέκταση Krawtchouk. Theory of Probability & Its Applications, 45(2):258–272, 2001. doi:10.1137/S0040585X9797821X.
https://doi.org/10.1137/S0040585X9797821X

[29] Robert M. Young. 75.9 Η σταθερά του Euler. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/3620251.
https: / / doi.org/ 10.2307 / 3620251

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

Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους