Recent results by Harrow et. al. and by Ta-Shma, suggest that quantum computers may have an exponential advantage in solving a wealth of linear algebraic problems, over classical algorithms. Building on the quantum intuition of these results, we step back into the classical domain, and explore its usefulness in designing classical algorithms. We achieve an algorithm for solving the major linear-algebraic problems in time $O(n^{ω+ν})$ for any $ν>0$, where $ω$ is the optimal matrix-product constant. Thus our algorithm is optimal w.r.t. matrix multiplication, and comparable to the state-of-the-art algorithm for these problems due to Demmel et. al. Being derived from quantum intuition, our proposed algorithm is completely disjoint from all previous classical algorithms, and builds on a combination of low-discrepancy sequences and perturbation analysis. As such, we hope it motivates further exploration of quantum techniques in this respect, hopefully leading to improvements in our understanding of space complexity and numerical stability of these problems.
Recent results by Harrow et. al. and by Ta-Shma, suggest that quantum computers may have an exponential advantage in solving a wealth of linear algebraic problems, over classical algorithms. Building on the quantum intuition of these results, we step back into the classical domain, and explore its usefulness in designing classical algorithms. We achieve an algorithm for solving the major linear-algebraic problems in time O(nω+ν) for any ν>0, where ω is the optimal matrix-product constant. Thus our algorithm is optimal w.r.t. matrix multiplication, and comparable to the state-of-the-art algorithm for these problems due to Demmel et. al. Being derived from quantum intuition, our proposed algorithm is completely disjoint from all previous classical algorithms, and builds on a combination of low-discrepancy sequences and perturbation analysis. As such, we hope it motivates further exploration of quantum techniques in this respect, hopefully leading to improvements in our understanding of space complexity and numerical stability of these problems.
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.
We prove lower bounds on the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Using a novel way of applying recording query methods we show that for many linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices A, including the discrete Fourier transform (DFT) matrix, we prove that quantum circuits with at most T input queries and S qubits of memory require T=Ω(n2/S) to compute matrix-vector product Ax for x ∈ {0,1}n. We similarly prove that matrix multiplication for n× n binary matrices requires T=Ω(n3 / √S). Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems at any space bound. We also improve the previous quantum time-space tradeoff lower bounds for n× n Boolean (i.e. AND-OR) matrix multiplication from T=Ω(n2.5/S1/2) to T=Ω(n2.5/S1/4) which has optimal exponents for the powerful query algorithms to which it applies. Our method also yields improved lower bounds for classical algorithms.
Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.
Quantum computing offers promising alternatives to classical approaches for solving complex linear algebra problems. This paper presents a comparative study of the performance of quantum algorithms versus classical algorithms in solving systems of linear equations and matrix operations. Through simulation and analysis, we demonstrate that while quantum computing holds advantages in specific problem sets, classical computing remains efficient for general applications. These findings highlight the current limitations and potential of quantum computing.
We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix A∈Rm×n and a vector b∈Rm, we propose classical algorithms that produce a data structure for the solution x∈Rn of the linear system Ax=b with the ability to sample and query its entries. The resulting x satisfies ∥x−A+b∥≤ε∥A+b∥, where ∥⋅∥ is the spectral norm and A+ is the Moore-Penrose inverse of A. Our algorithm has time complexity O(κF4/κε2) in the general case, where κF=∥A∥F∥A+∥ and κ=∥A∥∥A+∥ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When A is s-sparse, our algorithm has complexity O(sκlog(1/ε)), matching the quantum lower bound for solving linear systems in κ and 1/ε up to poly-logarithmic factors [Harrow and Kothari]. When A is s-sparse and symmetric positive-definite, our algorithm has complexity O(sκlog(1/ε)). Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.
Abstract In a sense, gate-based quantum computers are just machines that apply (extremely) large matrices to input states (vectors), and so it is natural to ask whether linear algebra applications can benefit from quantum computing. In the case of solving linear systems, this question has been answered with an emphatic ‘yes’. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd proposed a quantum algorithm to solve linear systems exponentially faster than the best classical counterpart. The quantum linear systems solver is ubiquitously known by the initials of its inventors, ‘HHL’. As well as detailing HHL, this chapter also explores some of the quantum machine learning applications that have been proposed based on HHL along with results showing that these algorithms are often ‘dequantised’ in the problem space of interest – i.e., there exists an efficient classical ‘quantum-inspired’ algorithm.