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

Περίληψη

Ο αλγόριθμος κβαντικής αναζήτησης είναι ένας από τους σημαντικότερους κβαντικούς αλγόριθμους και χρησιμοποιείται στην αναζήτηση k το πλήθος μαρκαρισμένων στοιχείων συνόλου (μη δομημένη βάση δεδομένων), πληθικού αριθμού Ν. Ο αλγόριθμος είναι πιθανοθεωρητικός και απαντά επιτυχώς με Order(SQRT(N/k)) δοκιμές, επιτυγχάνοντας έτσι τετραγωνική ελάττωση της πολυπλοκότητας αναζήτησης σε σύγκριση με κάθε αντίστοιχο κλασικό αλγόριθμο πολυπλοκότητας Οrder(N/k). Ο αλγοριθμος εκμεταλλεύεται βασικά χαρακτηριστικά της Κβαντομηχανικής όπως η γραμμική υπέρθεση, ο κβαντικός εναγκαλισμός (quantum entanglement) διανυσμάτων κατάστασης σε τανυστικά γινόμενα χώρων Hilbert, η γιουνίταρι δυναμική, η κβαντική προβολική μέτρηση. Στην παρούσα εργασία διερευνούμε διάφορες αλγεβρικές, γεωμετρικές και υπολογιστικές (από την σκοπιά της πολυπλοκότητας) πτυχές της κβαντικής αναζήτησης και προτείνουμε νέους κβαντικούς αλγόριθμους οι οποίοι ελαττώνουν περαιτέρω τα όρια της πολυπλοκότητας. Πιο συγκεκριμένα, εισάγου ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Quantum search algorithm determines k marked items in an otherwise unstructured set (database), of size N by performing Order(SQRT(N/k)) trials. Hence a quadratic reduction of search complexity is achieved compared to Order(N/k) trials required by any classical algorithm. The quantum algorithm exploits successfully basic ingredients of Quantum Mechanics such as, linear superpositions and quantum entanglement of state vectors in multiple tensorial products of Hilbert spaces, unitary dynamics, projective measurements and the probabilistic interpretation of the outcomes. It stands as a landmark procedure and a computational primitive within the field of Quantum Information Algorithms. This Thesis undertakes research on the original quantum search scheme and proposes novel quantum algorithms that exceed existing search complexity limits. The work is organized along the algebraic, geometrical and complexity aspects characterizing the quantum search field. Initially the so called oracl ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/43606
ND
43606
Εναλλακτικός τίτλος
Albebraic, geometric and complexity aspects of quantum search algorithms
Συγγραφέας
Κωνσταντάκης, Χρήστος του Δημήτριος
Ημερομηνία
2018
Ίδρυμα
Πολυτεχνείο Κρήτης. Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Εξεταστική επιτροπή
Έλληνας Δημοσθένης
Μανουσάκης Αντώνιος
Πετράκης Μίνως
Αγγελάκης Δημήτριος
Γαροφαλάκης Μίνως
Κολουντζάκης Μιχαήλ
Πάχος Ιωάννης
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Λέξεις-κλειδιά
Κβαντική πληροφορία; Κβαντικοί αλγόριθμοι; Κβαντική Αναζήτηση
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
114 σ., σχημ., γραφ.

Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)