ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Μεταπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ Διδακτορικής Διατριβής
Χρήστου Κωνσταντάκη
με θέμα
Θέματα Άλγεβρας, Γεωμετρίας και Πολυπλοκότητας στους Κβαντικούς Αλγόριθμους Αναζήτησης
Algebraic, Geometric and Complexity Aspects of Quantum Search Algorithms
Δευτέρα 7 Μαΐου 2018, 12-14 μ.μ.
Αίθουσα: Κτίριο Επιστημών, Αίθουσα Συνεδριάσεων Σχολής ΗΜΜΥ 141Π-36,141Π-37, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Δημοσθένης Έλληνας (επιβλέπων), Πολυτεχνείο Κρήτης
Αναπλ. Καθηγητής Δημήτρης Αγγελάκης, Πολυτεχνείο Κρήτης
Καθηγητής Μίνως Γαροφαλάκης, Πολυτεχνείο Κρήτης
Καθηγητής Μιχάλης Κολουντζάκης, Πανεπιστήμιο Κρήτης
Αναπλ. Καθηγητής Αντώνης Μανουσάκης, Πολυτεχνείο Κρήτης
Professor Jiannis Pachos, University of Leeds
Αναπλ. Καθηγητής Μίνως Πετράκης, Πολυτεχνείο Κρήτης
Abstract
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 oracle matrix algebra is introduced as a special SU(2) isomorphic algebra embedded in SU(N) algebra, determined by the oracle Boolean function that marks the target vectors in the database Hilbert space. Formulating search via oracle algebra reveals that Bloch's vector search trajectories are spherical geodesics, hence the complexity reduction has geometric origin. Within the same algebraic setting a toy model relaxation of the unitarity of the model leading to an open quantum system search algorithm is introduced. Searching is now carried out by a completely positive trace preserving map (CPTP), the investigation of which allows to address questions of complexity vs. accuracy trade off, and to provide answers summarized in the form of a new search strategy.
Utilizing oracle algebra's representation theory a novel scheme of collective quantum search is put forward. Many quantum searche(r)s can be joined in two modes: either by concatenation or by merging their Boolean functions and database Hilbert spaces. While concatenation complexity Tconc, leads to no improvements, merging quantum searches, say n of them, leads to complexity: Tconc=Order(SQRT(n)) Tmerg. Hence collective search speeds up finding items by a factor quadratic in the number of searches participating. Between the all n merging to all n concatenating joining schemes all other possible interpolating joining schemes are investigated. They provide all intermediate values of complexity reductions, as is shown analytically by means of the theory of partitions, Young tableaux, and majorization theory.
Relying on unitary dilation theory of CP maps, it is next shown that the parametric quantum search algorithm introduced before admits a unitarization (unitary dilation) a la quantum walk (QW), at the expense of introducing auxiliary quantum coin-qubit spaces. QW, a proverbial model of quantum random walk with quadratic enhancement of the diffusion range in comparison to that of classical random walk, hence of similar to search quadratic complexity reduction, is shown to enable quantum search simulation. QW dynamics is generated by a Hamiltonian representing multi-particle long-range interacting qubits. The QW-Quantum Search construct is finally shown to give rise to a double lane quantum search algorithm.
Finally the Thesis addresses the fast counting problem: Counting the size of a set requires as many counts as set's cardinality, say N. Employing single item search algorithm of N dimensional database and the entanglement developed between any two parts of database space during search leads to fast counting. Demonstrating the periodic projectivity of reduced density matrix ensuing by de-coupling fraction of qubits from database state and monitoring entanglement measures, being periodically vanishing with period Order(SQRT(N)), leads to quadratic speed up of counting. By rigging marked item initial probability a hyper-quadratic acceleration of counting is achieved.
Περίληψη
Ο αλγόριθμος κβαντικής αναζήτησης είναι ένας από τους σημαντικότερους κβαντικούς αλγόριθμους και χρησιμοποιείται στην αναζήτηση k το πλήθος μαρκαρισμένων στοιχείων συνόλου (μη δομημένη βάση δεδομένων), πληθικού αριθμού Ν. Ο αλγόριθμος είναι πιθανοθεωρητικός και απαντά επιτυχώς με Order(SQRT(N/k)) δοκιμές, επιτυγχάνοντας έτσι τετραγωνική ελάττωση της πολυπλοκότητας αναζήτησης σε σύγκριση με κάθε αντίστοιχο κλασικό αλγόριθμο πολυπλοκότητας Οrder(N/k). Ο αλγοριθμος εκμεταλλεύεται βασικά χαρακτηριστικά της Κβαντομηχανικής όπως η γραμμική υπέρθεση, ο κβαντικός εναγκαλισμός (quantum entanglement) διανυσμάτων κατάστασης σε τανυστικά γινόμενα χώρων Hilbert, η γιουνίταρι δυναμική, η κβαντική προβολική μέτρηση.
Στην παρούσα εργασία διερευνούμε διάφορες αλγεβρικές, γεωμετρικές και υπολογιστικές (από την σκοπιά της πολυπλοκότητας) πτυχές της κβαντικής αναζήτησης και προτείνουμε νέους κβαντικούς αλγόριθμους οι οποίοι ελαττώνουν περαιτέρω τα όρια της πολυπλοκότητας.
Πιο συγκεκριμένα, εισάγουμε πρώτα την έννοια της άλγεβρας του μαντείου η οποία καθορίζεται από τις Boolean συναρτήσεις χαρακτηρισμού των ζητούμενων στοιχείων, ως μια ισομορφική άλγεβρα της SU(2) εμφυτευμένης στην άλγεβρα SU(N) και επαναδιατυπώνουμε αλγεβρικά τον αλγόριθμο. Δυνάμει της αλγεβρικής επαναδιατύπωση αποδεικνύεται ότι το διάνυσμα αναζήτησης Bloch ακολουθεί σφαιρική γεωδαισιακή τροχιά, αιτιολογώντας έτσι γεωμετρικά την τετραγωνική ελάττωση της πολυπλοκότητας αναζήτησης. Έχοντας επαναδιατυπώσει αλγεβρικά τον αλγόριθμο, εισάγουμε την χαλάρωση του γιουνίταρι χαρακτήρα του τελεστή αναζήτησης, ο οποίος αντικαθίσταται από μία μονοπαραμετρική πλήρως θετική ιχνοδιατηρητική απεικόνιση. Η μελέτη της απεικόνισης αναζήτησης οδηγεί στην διερεύνηση της σχέσης πολυπλοκότητας-ακρίβειας στην εύρεση στοιχείων και οδηγεί στην διατύπωση μίας νέας στρατηγικής αναζήτησης.
Η χρήση της θεωρίας αναπραστάσεων της άλγεβρας μαντείου μας επιτρέπει να εισάγουμε δυο νέους τρόπους συλλογικής κβαντικής αναζήτησης : την συγχώνευση (merging) και την αλύσωση (concatenation) , που αντιστοιχούν σε δύο τρόπους συνένωσης των συναρτήσεων Boole και των χώρων Hilbert των επιμέρους (έστω n τον αριθμό), κβαντικών αλγορίθμων. Αποδεικνύουμε ότι για τις αντίστοιχες πολυπλοκότητες αλύσωσης Tconc και συγχώνευσης Tmerg, ισχύει ότι αφενός η αλύσωση δεν προσφέρει επιπλέον επιτάχυνση αλλά και ότι Tconc=Order(SQRT(n)) Tmerg. Επομένως η συλλογική αναζήτηση μέσω συγχώνευσης αλγορίθμων παρέχει επιτάχυνση χρόνου αναζήτησης κατά SQRT παράγοντα του αριθμού εμπλεκομένων αλγορίθμων. Χρησιμοποιώντας την θεωρία διαμερίσεων ακεραίων, διαγραμμάτων Young και την θεωρία της κατίσχυσης (majoirization), εξετάζουμε τις ενδιάμεσες τιμές πολυπλοκότητας για όλα τα παρεμβαλλόμενα σχήματα συνένωσης ανάμεσα στα ακραία σχήματα “όλες οι n αναζητήσεις συγχωνευμένες ” και στο “όλες οι n αναζητήσεις αλυσωμένες ”.
Χρησιμοποιώντας την θεωρία της γιουνίταρι επέκτασης των θετικών ιχνοδιατηρητικών απεικονίσεων, αποδεικνύουμε ότι η παραπάνω παραμετρική αναζήτηση είναι ισοδύναμη με έναν κβαντικό περίπατο υπό το κόστος της εισαγωγής (βοηθητικών) χώρων κβαντικού “νομίσματος”. Ακριβέστερα, αποδεικνύουμε ότι ο αριθμός των επαναλήψεων από τη σκοπιά της κβαντικής αναζήτησης είναι ίσος με τον αριθμό των κβαντικών “νομισμάτων” (από τη σκοπιά του κβαντικού περιπάτου) και ότι η τετραγωνική επιτάχυνση της κβαντικής αναζήτησης εκφράζεται ως η τετραγωνική αύξηση της διάχυσης στον κβαντικό περίπατο. Επίσης, αποδεικνύεται ότι με το (επιπλέον) κόστος των δυο ερωτήσεων στο μαντείο, τα άρτιας τάξης βήματα του κβαντικού τυχαίου περιπάτου ισοδυναμούν με τον “διπλασιασμό” της κβαντικής αναζήτησης.
Τέλος, χρησιμοποιούμε τον αλγόριθμο κβαντικής αναζήτησης ενός στοιχείου ως εργαλείο για την λύση ενός εντελώς διαφορετικού προβλήματος: της καταμέτρησης των στοιχείων (έστω Ν), ενός πεπερασμένου συνόλου το οποίο ταυτοποιούμε ως σύνολο βάσης δεδομένων. Προς τούτο αποδεικνύουμε την την περιοδικότητα του συναρτησιακού μέτρου του κβαντικού εναγκαλισμού μεταξύ δυο οποιονδήποτε μερών διαμέρισης του χώρου βάσης δεδομένων. Αποδεικνύουμε ότι αρκεί να προσδιορίσουμε δύο διαδοχικούς μηδενισμούς αυτού του εναγκαλισμού που συμβαίνουν με περιοδικότητα Order(SQRT(N)), προκειμένου να μετρηθεί ο πληθάριθμος Ν με τετραγωνική επιτάχυνση της καταμέτρησης, σε σχέση με την κλασική καταμέτρηση κόστους Ν. Η επιτάχυνση καταμέτρησης βελτιώνεται υπερ-τετραγωνικά ενισχύοντας , εξ αιτίας εικασίας ή a priori πληροφορίας, την αρχική πιθανότητα επιλογής του στοιχείου αναζήτησης.
