UC Merced

Recently (2009) a quantum algorithm for solving a system of linear equations has been proposed. The algorithm by Harrow, Hassidim, and Lloyd has attracted considerable attention in the quantum algorithms community, due to the broad potential applications of a rapid linear equations solver. The contribution of this thesis is to analyze the classical and quantum resources required for implementation. The thesis has two major tasks. We first survey the field of quantum algorithms. The papers which established this field (e.g., Feynman and Deutsch) to recent works are reviewed. Different classes of quantum algorithms are examined, including those based on the Fourier transform, quantum searching, and quantum walk. For the second task, we focus on the algorithm by Harrow, Hassidim, and Lloyd. The advantages of the algorithm are an exponential performance gain over classical algorithms (under conditions of sparse operator matrices and few selected measurements from the solution set), and fewer data registers. In the second part of the thesis, we study the classical resources required for implementation of the algorithm. Since classical resources can determine the ultimate efficiency of the quantum algorithm, the optimal use of classical resources is mandatory. We demonstrate how a classical computer may handle certain computations (e.g., time evolution) and feed these into the quantum circuit implementing the algorithm. Thus, the classical and quantum resources for implementing the algorithm are described. Through a detailed analysis of the classical resources, we hope to understand how these resources may be optimized. This work can therefore contribute to the design of efficient quantum algorithms.