Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Algebraic, geometric and complexity aspects of quantum search algorithms

Konstantakis Christos

Full record

---

Summary

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.

Available Files

Services