Quantum Search Algorithm
Abstract
In this thesis we tried to take an overall look at quantum computation and specifically at the quantum search algorithm, an algorithm for unstructured search that finds with high probability the solution. This algorithm provides a quadratic speed up compared to the best possible version of a classical unstructured search algorithm.
The first chapter develops, in deduction from the postulates of quantum computation, a brief description of the elements of quantum circuits, namely bits, registers, gates, channels and the final measurement operation. We also describe a peculiar property of quantum computation: entanglement.
The second chapter begins with a description of what the quantum search algorithm is and how it works. Grover's algorithm can be seen both from an algebraic and a geometric point of view, both of them are explained; then the peculiar element of the algorithm is described: the subroutine.
We continue with a demonstration of the correctness of the algorithm and after that some concrete examples are presented. The problem of the impact of the number of solutions on the performance of the quantum search algorithm, and some possible solutions, are then described.
In conclusion we focused on the performance of the algorithm, on its optimality and on the possible consequences that this could have in terms of the hierarchy of quantum complexity classes. After that there is a brief mention of the consequences that a large-scale application of the algorithm could have on classical cryptography.