Classical and Quantum Resource Analysis for the Quantum Linear Systems Algorithm

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 presentation is to analyze the classical and quantum resources required for implementation. The presentation has two major tasks. We first summarize the field of quantum algorithms. The papers which established this field (e.g., Feynman and Deutsch) to recent works are briefly surveyed. 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. 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. This work can therefore contribute to the design of efficient quantum algorithms.