Implementing and Evaluating the Efficiency of a Quantum Linear Systems Algorithm

We demonstrate the advantage quantum computers bring to solving computationally intensive tasks by presenting the results of determining the solutions to large systems of linear equations using both a quantum algorithm and a classical, deterministic algorithm. In the quantum approach, we implement the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems using a quantum programming language called Qiskit. HHL fundamentally operates using a method called eigenvalue inversion. For the classical algorithm, we implement a Python algorithm that computes the exact solution to the input system of equations using Gaussian elimination with partial pivoting, one of the most efficient classical algorithms. We then feed randomly generated square matrix equations representing $n$ by $n$ linear systems into these two algorithms and record how internal properties such as matrix condition number and sparsity impact metrics such as runtime and solution fidelity. Scaling $n$ enables us to experimentally determine the respective time complexities of the algorithms and compare their efficiencies. We show that, unlike Gaussian elimination, HHL has a strong dependence on condition number and sparsity and scales logarithmically in $n$, providing a noticeable speedup for sufficiently large systems.