Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Konstantakis Christos

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/99BC2BD7-FA98-4A35-B5BC-C0FAEC98F44F-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.74831-
Γλώσσαen-
Μέγεθος114 pagesen
ΤίτλοςAlgebraic, geometric and complexity aspects of quantum search algorithmsen
ΤίτλοςΘέματα άλγεβρας, γεωμετρίας και πολυπλοκότητας στους κβαντικούς αλγόριθμους αναζήτησηςel
ΔημιουργόςKonstantakis Christosen
ΔημιουργόςΚωνσταντακης Χρηστοςel
Συντελεστής [Επιβλέπων Καθηγητής]Ellinas Dimosthenisen
Συντελεστής [Επιβλέπων Καθηγητής]Ελληνας Δημοσθενηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Aggelakis Dimitriosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Αγγελακης Δημητριοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Garofalakis Minosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Γαροφαλακης Μινωςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Kolountzakis, Mihalisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Manousakis Antoniosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μανουσακης Αντωνιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Pachos, Jiannis Ken
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Petrakis Minosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Πετρακης Μινωςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Περίληψη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. en
ΤύποςΔιδακτορική Διατριβήel
ΤύποςDoctoral Dissertationen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2018-05-08-
Ημερομηνία Δημοσίευσης2018-
Θεματική ΚατηγορίαQuantum computingen
Βιβλιογραφική ΑναφοράChristos Konstantakis, "Algebraic, geometric and complexity aspects of quantum search algorithms", Doctoral Dissertation, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2018en
Βιβλιογραφική ΑναφοράΧρήστος Κωνσταντάκης, "Θέματα άλγεβρας, γεωμετρίας και πολυπλοκότητας στους κβαντικούς αλγόριθμους αναζήτησης", Διδακτορική Διατριβή, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2018el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά