Solving mathematical problems using quantum mechanics

Abstract

This prime purpose of this thesis is to appreciate the use of quantum search algo- rithms. The thesis discusses Grover’s search algorithm[Grover96]. The algorithm can √ search for a single match in a database with N records in O( N ) steps assuming that the item must exist in the database with quadratic speed-up over the best known classical algorithm. Later, the focus shifts to application of this algorithm in finding a common element of two sets[Tulsi2012]. We discuss a variant of Grover’s algorithm which proves to be an optimal algorithm for the required problem. Further, we present an algorithm for finding the real roots of a polynomial[Weigert2003b]. Here, we see the problem as an inverse case of finding the characteristic polynomial of a hermitian matrix[Feidler90][Schmeisser93] and then diagonalize the hermitian matrix in a quan- tum way[Weigert2001] using concept of generalised Stern-Gerlach apparatus[Swift77]. Then, we discuss a algorithm analogous to Grover’s search algorithm. This algorithm can be implemented using any Hamiltonian with a discrete energy spectrum through excitation of resonances between an initial and the searched state[Romanelli2005]. The use of quantum resonances in the algorithm clearly shows Grover’s assertion that his algorithm is a quantum phenomenon[Grover2001]. Having being acquainted with these concepts we are now focussed on spatial search. A different physical interpreta- tion of spatial search, using periodic potential barriers with impurity in one of them, is being tried.