Υβριδική προσέγγιση διαίρει και βασίλευε για αλγόριθμους αναζήτησης δέντρων

Υβριδική προσέγγιση διαίρει και βασίλευε για αλγόριθμους αναζήτησης δέντρων

Χρονική σήμανση: 23 Μαρτίου 2023 9:57 π.μ.
Κόμβος πηγής: 2029300

Μάθις Ρενέλα1, Μάρκα Sebastiaan2, Alfons Laarman2, και ο Βεντράν Ντάνικο2

1Laboratoire de Physique de l'Ecole Normale Supérieure, Inria, CNRS, ENS-PSL, Mines-Paristech, Sorbonne Université, PSL Research University, Παρίσι, Γαλλία
2LIACS, Πανεπιστήμιο Leiden, Leiden, Ολλανδία

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

Περίληψη

Μία από τις προκλήσεις των κβαντικών υπολογιστών βραχυπρόθεσμα και μεσοπρόθεσμα είναι ο περιορισμένος αριθμός qubits που μπορούμε να χρησιμοποιήσουμε για υπολογισμούς. Η εύρεση μεθόδων που επιτυγχάνουν χρήσιμες κβαντικές βελτιώσεις υπό περιορισμούς μεγέθους είναι επομένως ένα βασικό ερώτημα στο πεδίο. Σε αυτό το πνεύμα, πρόσφατα αποδείχθηκε ότι μια υβριδική κλασσική-κβαντική μέθοδος μπορεί να βοηθήσει στην παροχή πολυωνυμικών επιταχύνσεων σε κλασικούς αλγόριθμους διαίρει και βασίλευε, ακόμη και όταν παρέχεται πρόσβαση μόνο σε έναν κβαντικό υπολογιστή πολύ μικρότερο από το ίδιο το πρόβλημα. Σε αυτή την εργασία, μελετάμε την υβριδική μέθοδο διαίρει και βασίλευε στο πλαίσιο αλγορίθμων αναζήτησης δέντρων και την επεκτείνουμε συμπεριλαμβάνοντας κβαντική οπισθοδρόμηση, η οποία επιτρέπει καλύτερα αποτελέσματα από τις προηγούμενες μεθόδους που βασίζονται στο Grover. Επιπλέον, παρέχουμε γενικά κριτήρια για πολυωνυμικές επιταχύνσεις στο πλαίσιο αναζήτησης δέντρου και παρέχουμε έναν αριθμό παραδειγμάτων όπου μπορούν να ληφθούν πολυωνυμικές ταχύτητες, χρησιμοποιώντας αυθαίρετα μικρότερους κβαντικούς υπολογιστές. Παρέχουμε συνθήκες για επιταχύνσεις για τον γνωστό αλγόριθμο DPLL και αποδεικνύουμε επιταχύνσεις χωρίς όριο για τον αλγόριθμο PPSZ (τον πυρήνα του ταχύτερου ακριβούς λύτη ικανοποίησης Boolean) για καλές κατηγορίες τύπων. Παρέχουμε επίσης ένα απλό παράδειγμα όπου οι επιταχύνσεις μπορούν να ληφθούν με τρόπο ανεξάρτητο από αλγόριθμο, κάτω από ορισμένες καλά μελετημένες θεωρητικές υποθέσεις πολυπλοκότητας. Τέλος, συζητούμε εν συντομία τους θεμελιώδεις περιορισμούς των υβριδικών μεθόδων στην παροχή επιταχύνσεων για μεγαλύτερα προβλήματα.

Δημοφιλή περίληψη

Βραχυπρόθεσμα και μεσοπρόθεσμα, με τους κβαντικούς υπολογιστές να έχουν περιορισμένο αριθμό qubits, ορισμένες περιπτώσεις προβλημάτων μπορεί να είναι πολύ μεγάλες για να επιλυθούν σε έναν κβαντικό υπολογιστή. Σε αυτή τη ρύθμιση είναι φυσικό να εξετάσουμε τις στρατηγικές διαίρει και βασίλευε: κλασικά χωρίστε το πρόβλημα σε μέρη που είναι αρκετά μικρά για να επιλυθούν στον κβαντικό υπολογιστή και συνδυάστε τα αποτελέσματα στη συνέχεια. Αυτό ονομάζεται κβαντικός-κλασικός υβριδικός αλγόριθμος.

Οι αλγόριθμοι αναζήτησης δέντρων είναι ιδιαίτερα κατάλληλοι για αυτήν την υβριδική προσέγγιση. Όταν ο χώρος αναζήτησης είναι ένα πλήρες δυαδικό δέντρο, είναι εύκολο να χωριστεί το πρόβλημα σε μέρη αρκετά μικρά για έναν δεδομένο κβαντικό υπολογιστή και να παραμείνει με μια (μικρότερη) κβαντική επιτάχυνση στο αρχικό πρόβλημα. Ωστόσο, στους περισσότερους κλασικούς αλγόριθμους αναζήτησης δέντρων κλαδεύονται κλαδιά κατά τη διάρκεια της αναζήτησης και παραμένει ένα πιο αραιό δέντρο. Σε αυτή τη ρύθμιση, γίνεται λιγότερο προφανές εάν μια μικρή πολυωνυμική επιτάχυνση μπορεί ακόμα να ληφθεί από έναν υβριδικό αλγόριθμο.

Σε αυτό το άρθρο, μελετάμε αυτήν την υβριδική μέθοδο διαίρει και βασίλευε στο πλαίσιο αλγορίθμων αναζήτησης δέντρων, όπως οι αλγόριθμοι που αναπτύχθηκαν για την ικανοποίηση Boolean. Η κύρια συνεισφορά μας είναι ότι παρέχουμε επαρκείς συνθήκες για κβαντικές επιταχύνσεις και τις εφαρμόζουμε σε δύο γνωστούς αλγόριθμους ικανοποίησης Boolean.

► Δεδομένα BibTeX

► Αναφορές

[1] Vedran Dunjko, Yimin Ge και J Ignacio Cirac. «Υπολογιστικές επιταχύνσεις με χρήση μικρών κβαντικών συσκευών». Επιστολές φυσικής αναθεώρησης 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[2] Yimin Ge και Vedran Dunjko. «Ένα πλαίσιο υβριδικού αλγορίθμου για μικρούς κβαντικούς υπολογιστές με εφαρμογή στην εύρεση κύκλων Χαμιλτονίου». Journal of Mathematical Physics 61, 012201 (2020).
https: / / doi.org/ 10.1063 / 1.5119235

[3] Άσλεϊ Μοντανάρο. "Επιτάχυνση κβαντικής βάδισης αλγορίθμων οπισθοδρόμησης". Theory of Computing 14, 1–24 (2018).
https: / / doi.org/ 10.4086 / toc.2018.v014a015

[4] Martin Davis, George Logemann και Donald W Loveland. «Ένα πρόγραμμα μηχανής για την απόδειξη θεωρημάτων». Πανεπιστήμιο της Νέας Υόρκης, Ινστιτούτο Μαθηματικών Επιστημών. (1961).
https: / / doi.org/ 10.1145 / 368273.368557

[5] Ramamohan Paturi, Pavel Pudlák, Michael E Saks και Francis Zane. «Ένας βελτιωμένος αλγόριθμος εκθετικού χρόνου για k-SAT». Journal of the ACM (JACM) 52, 337–364 (2005).
https: / / doi.org/ 10.1145 / 1066100.1066101

[6] Earl Campbell, Ankur Khurana και Ashley Montanaro. «Εφαρμογή κβαντικών αλγορίθμων σε προβλήματα ικανοποίησης περιορισμών». Quantum 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

[7] Simon Martiel και Maxime Remaud. «Πρακτική εφαρμογή αλγορίθμου κβαντικής οπισθοδρόμησης». In International Conference on Current Trends in Theory and Practice of Informatics. Σελίδες 597–606. Springer (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

[8] Thomas Dueholm Hansen, Haim Kaplan, Or Zamir και Uri Zwick. «Ταχύτεροι αλγόριθμοι k-sat με χρήση biased-ppsz». In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Σελίδες 578–589. STOC 2019 Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ (2019). ACM.
https: / / doi.org/ 10.1145 / 3313276.3316359

[9] Armin Biere, Marijn Heule και Hans van Maaren. «Εγχειρίδιο ικανοποίησης». Τόμος 185. Τύπος IOS. (2009).

[10] Marc Mezard, Marc Mezard και Andrea Montanari. «Πληροφορίες, φυσική και υπολογισμός». Oxford University Press. (2009).
https: / / doi.org/ 10.1063 / 1.3397047

[11] Martin Davis και Hilary Putnam. «Μια υπολογιστική διαδικασία για τη θεωρία ποσοτικοποίησης». J. ACM 7, 201–215 (1960).
https: / / doi.org/ 10.1145 / 321033.321034

[12] Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda, et al. «Περιγραφές επίλυσης και συγκριτικής αξιολόγησης». In Proceedings of SAT διαγωνισμός 2018. Department of Computer Science, University of Helsinki (2018). url: http://hdl.handle.net/​10138/​237063.
http: // hdl.handle.net/ 10138 / 237063

[13] Robert Nieuwenhuis, Albert Oliveras και Cesare Tinelli. «Αφηρημένες DPLL και αφηρημένες θεωρίες δομοστοιχείων DPLL». Στο Διεθνές Συνέδριο Logic for Programming Artificial Intelligence and Reasoning. Σελίδες 36–50. Springer (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

[14] Jasmin Christian Blanchette, Sascha Böhme και Lawrence C Paulson. "Extending Sledgehammer με SMT solvers". Journal of automated argumenting 51, 109–128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

[15] Ντάνιελ Ρολφ. «Διατυχισμός του PPSZ για το μοναδικό-k-SAT». Στο Διεθνές Συνέδριο Θεωρίας και Εφαρμογών του Έλεγχου Ικανοποίησης. Σελίδες 216–225. Springer (2005).
https: / / doi.org/ 10.1007 / 11499107_16

[16] Dominik Scheder και John P Steinberger. “PPSZ για γενική k-SAT-καθιστώντας την ανάλυση Hertli απλούστερη και 3-SAT ταχύτερη”. Στο 32ο Συνέδριο Υπολογιστικής Πολυπλοκότητας (CCC 2017). Τόμος 79, σελίδες 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.9

[17] Ντάνιελ Ρολφ. "Βελτιωμένο όριο για τον αλγόριθμο PPSZ/​schoning για 3-SAT". Journal on Satisfiability, Boolean Modeling and Computation 1, 111–122 (2006).
https://doi.org/​10.3233/​SAT190005

[18] Τίμον Χέρτλι. «3-SAT ταχύτερα και απλούστερα—ισχύουν τα μοναδικά όρια SAT για το PPSZ γενικά». SIAM Journal on Computing 43, 718–729 (2014).
https: / / doi.org/ 10.1137 / 120868177

[19] Τίμον Χέρτλι. «Σπάζοντας το φράγμα PPSZ για μοναδικά 3-SAT». In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8-11 Ιουλίου 2014, Proceedings, Part I 41. Σελίδες 600–611. Springer (2014).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

[20] Dominik Scheder. "Το PPSZ είναι καλύτερο από όσο νομίζετε". Το 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Σελίδες 205–216. (2022).
https: / / doi.org/ 10.1109 / FOCS52979.2021.00028

[21] Λοβ Κ Γκρόβερ. «Ένας γρήγορος κβαντομηχανικός αλγόριθμος για αναζήτηση βάσεων δεδομένων». Στα Πρακτικά του εικοστού όγδοου ετήσιου συμποσίου ACM για τη Θεωρία των Υπολογιστών. Σελίδες 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[22] Άντρης Αμπαΐνης. «Κβαντικοί αλγόριθμοι αναζήτησης». ACM SIGACT News 35, 22–35 (2004).
https: / / doi.org/ 10.1145 / 992287.992296

[23] Άντρης Αμπαΐνης και Μαρτίνς Κοκαΐνης. «Κβαντικός αλγόριθμος για την εκτίμηση του μεγέθους του δέντρου, με εφαρμογές για backtracking και παιχνίδια 2 παικτών». In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Σελίδες 989–1002. (2017).
https: / / doi.org/ 10.1145 / 3055399.3055444

[24] Μάικλ Τζάρετ και Κιάννα Γουάν. «Βελτιωμένοι αλγόριθμοι κβαντικής οπισθοδρόμησης χρησιμοποιώντας αποτελεσματικές εκτιμήσεις αντίστασης». Φυσική Ανασκόπηση Α 97, 022337 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022337

[25] Dominic J. Moylett, Noah Linden και Ashley Montanaro. «Κβαντική επιτάχυνση του προβλήματος του περιοδεύοντος πωλητή για γραφήματα περιορισμένου βαθμού». Phys. Α' 95, 032323 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032323

[26] Neil D. Jones και William T. Laaser. «Ολοκληρωμένα προβλήματα για ντετερμινιστικό πολυωνυμικό χρόνο». Theoretical Computer Science 3, 105 – 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

[27] Raymond Greenlaw, H James Hoover, Walter L Ruzzo, et al. «Όρια στον παράλληλο υπολογισμό: Θεωρία P-πληρότητας». Oxford University Press on Demand. (1995).

[28] Thomas Lengauer και Robert E Tarjan. «Ασυμπτωτικά στενά όρια στις αντισταθμίσεις χρόνου-χώρου σε ένα παιχνίδι με βότσαλα». Journal of the ACM (JACM) 29, 1087-1130 (1982).
https: / / doi.org/ 10.1145 / 322344.322354

[29] Τσαρλς Χ Μπένετ. «Αντιστοιχίες χρόνου/χώρου για αναστρέψιμο υπολογισμό». SIAM Journal on Computing 18, 766–776 (1989).
https: / / doi.org/ 10.1137 / 0218053

[30] T. Altman και Y. Igarashi. «Χονδρική ταξινόμηση: Διαδοχική και παράλληλη προσέγγιση». J. Inf. Επεξεργάζομαι, διαδικασία. 12, 154-158 (1989). url: http://id.nii.ac.jp/​1001/​00059782/​.
http://​id.nii.ac.jp/​1001/​00059782/​

[31] Hong-Yu Liang και Jing He. «Ικανοποίηση με την εξάρτηση του δείκτη». Journal of Computer Science and Technology 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

[32] Marcello Benedetti, John Realpe-Gómez και Alejandro Perdomo-Ortiz. «Μηχανές Helmholtz που υποβοηθούνται με κβαντικά: Ένα κβαντικό-κλασικό πλαίσιο βαθιάς μάθησης για βιομηχανικά σύνολα δεδομένων σε βραχυπρόθεσμες συσκευές». Quantum Science and Technology 3, 034007 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aabd98

[33] Aram W. Harrow. «Μικροί κβαντικοί υπολογιστές και μεγάλα κλασικά σύνολα δεδομένων» (2020) arXiv:2004.00026.
arXiv: 2004.00026

[34] Michael A Nielsen και Isaac Chuang. «Κβαντικός υπολογισμός και κβαντικές πληροφορίες». Αμερικανική Ένωση Καθηγητών Φυσικής. (2002).
https: / / doi.org/ 10.1017 / CBO9780511976667

[35] Robert B. Griffiths και Chi-Sheng Niu. «Ημικλασικός μετασχηματισμός Fourier για κβαντικό υπολογισμό». Phys. Αναθ. Lett. 76, 3228-3231 (1996).
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

[36] Robert Raussendorf και Hans J. Briegel. «Ένας μονόδρομος κβαντικός υπολογιστής». Phys. Αναθ. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[37] Thomas E O'Brien, Brian Tarasinski και Barbara M Terhal. "Εκτίμηση κβαντικής φάσης πολλαπλών ιδιοτιμών για πειράματα μικρής κλίμακας (θορυβώδους)". New Journal of Physics 21, 023022 (2019).
https: / / doi.org/ 10.1088 / 1367-2630 / aafb8e

[38] Akshay Ajagekar, Travis Humble και Fengqi You. «Στρατηγικές υβριδικών λύσεων που βασίζονται στον κβαντικό υπολογισμό για μεγάλης κλίμακας προβλήματα διακριτής συνεχούς βελτιστοποίησης». Computers & Chemical Engineering 132, 106630 (2020).
https://doi.org/​10.1016/​j.compchemeng.2019.106630

[39] Tianyi Peng, Aram W Harrow, Maris Ozols και Xiaodi Wu. "Προομοίωση μεγάλων κβαντικών κυκλωμάτων σε έναν μικρό κβαντικό υπολογιστή". Επιστολές φυσικής αναθεώρησης 125, 150504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.150504

[40] Sergey Bravyi, Graeme Smith και John A. Smolin. «Εμπόριο κλασσικών και κβαντικών υπολογιστικών πόρων». Φυσική Ανασκόπηση Χ 6 (2016).
https: / / doi.org/ 10.1103 / physrevx.6.021043

[41] Μάρτιν Σουέν. «Επίλυση SAT σε θορυβώδεις κβαντικούς υπολογιστές». https://theses.liacs.nl/​1725 (2019). Πτυχιακή εργασία.
https://theses.liacs.nl/​1725

[42] Theodore J Yoder, Guang Hao Low και Isaac L Chuang. «Κβαντική αναζήτηση σταθερού σημείου με βέλτιστο αριθμό ερωτημάτων». Επιστολές φυσικής αναθεώρησης 113 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501

[43] Alessandro Cosentino, Robin Kothari και Adam Paetznick. “Dequantizing Read-once Quantum Formulas”. Στο 8ο Συνέδριο Θεωρίας Κβαντικού Υπολογισμού, Επικοινωνίας και Κρυπτογραφίας (TQC 2013). Τόμος 22 του Leibniz International Proceedings in Informatics (LIPIcs), σελίδες 80–92. Dagstuhl, Γερμανία (2013). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.80

[44] Ντέιβιντ Α Μπάρινγκτον. "Τα προγράμματα διακλάδωσης πολυωνυμικού μεγέθους περιορισμένου πλάτους αναγνωρίζουν ακριβώς αυτές τις γλώσσες στο NC1". Journal of Computer and System Sciences 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

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

[1] Casper Gyurik, Chris Cade και Vedran Dunjko, «Προς το κβαντικό πλεονέκτημα μέσω ανάλυσης τοπολογικών δεδομένων», arXiv: 2005.02607, (2020).

[2] Kyle EC Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield και Eleanor Rieffel, “Quantum-accelerated constraint programming”, Κβαντικό 5, 550 (2021).

[3] Casper Gyurik, Chris Cade και Vedran Dunjko, «Προς το κβαντικό πλεονέκτημα μέσω ανάλυσης τοπολογικών δεδομένων», Κβαντικό 6, 855 (2022).

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

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2023-03-25 02:01:59).

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

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

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