Classical and Quantum Resource Analysis for the Quantum Linear Systems Algorithm

Casey J.R. Riggs

Jon Inouye

The quantum algorithm by Harrow, Hassidim, and Lloyd solves a system of N linear equations and achieves exponential speedup over classical algorithms under certain conditions. The advantage to the algorithm is that log(N) rather than N registers are required. Given an N x N matrix A and vectors x and b, the quantum algorithm seeks to find x such that Ax = b. By representing vector b as a superposition of quantum states |b>, quantum phase estimation is used to find the corresponding eigenvalues of A. Applying the inverse Fourier transform, we solve for |x> such that |x> = A-1|b>. We model the algorithm using a quantum circuit diagram, with data qubits encoded using the Steane code for fault tolerant quantum phase estimation. Fresh ancilla for error correction are provided using an oracular pipelined ancilla architecture. We then analyze the classical and quantum resources needed for implementation. The significance of this case study is to examine how classical and quantum resources interact in implementing this algorithm. The issues raised in this analysis, such as fault tolerant phase estimation using pipelined ancilla, garbage collection, and the preparation of I/O registers to this architecture, will be explored in more detail in future research.

Osama M. Raisuddin, Suvranu De

Adrian Harkness, Kate Saltovets, Mohammadhossein Mohammadisiahroudi +1 more

Systems of linear equations are ubiquitous across science, engineering, machine learning, and even finance. While classical methods can be prohibitively slow for large-scale problems, quantum linear systems algorithms offer the potential for exponential speedup in certain parameter regimes. However, a significant gap persists between this theoretical promise and practical implementation, as the advantages are often obscured by the substantial quantum resources and high sensitivity to noise inherent in current quantum hardware. One way to bridge this gap is through the use of Iterative Refinement, a classical post-processing scheme that can exponentially improve the accuracy to which a linear system of equations can be solved using low-precision arithmetic. In the context of quantum linear systems algorithms, such as the HHL algorithm proposed by Harrow, Hassidim, and Loyd, Iterative Refinement can greatly reduce the quantum resources required to calculate an accurate solution in terms of tomography cost, circuit volume, and fault-tolerant overhead. Here, we compute and benchmark highly precise solutions to linear systems of equations of up to eight variables by running HHL with Iterative Refinement on NISQ quantum computers. We also present our open-source implementation, emphasizing that our circuit is not tailored to specific problem instances, as most available implementations are.

Dhruv Yalamanchi

Jon Inouye

Recently (2009) a quantum algorithm for solving a system of linear equations\nhas been proposed. The algorithm by Harrow, Hassidim, and Lloyd has attracted\nconsiderable attention in the quantum algorithms community, due to the broad\npotential applications of a rapid linear equations solver. The contribution of this\nthesis is to analyze the classical and quantum resources required for implementation.\nThe thesis has two major tasks. We first survey the field of quantum\nalgorithms. The papers which established this field (e.g., Feynman and Deutsch) to\nrecent works are reviewed. Different classes of quantum algorithms are examined,\nincluding those based on the Fourier transform, quantum searching, and quantum\nwalk.\nFor the second task, we focus on the algorithm by Harrow, Hassidim, and\nLloyd. The advantages of the algorithm are an exponential performance gain over\nclassical algorithms (under conditions of sparse operator matrices and few selected\nmeasurements from the solution set), and fewer data registers.\nIn the second part of the thesis, we study the classical resources required for\nimplementation of the algorithm. Since classical resources can determine the ultimate\nefficiency of the quantum algorithm, the optimal use of classical resources is\nmandatory.\nWe demonstrate how a classical computer may handle certain computations\n(e.g., time evolution) and feed these into the quantum circuit implementing the\nalgorithm. Thus, the classical and quantum resources for implementing the algorithm\nare described. Through a detailed analysis of the classical resources, we hope to\nunderstand how these resources may be optimized. This work can therefore\ncontribute to the design of efficient quantum algorithms.