Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function k(x,x′) , have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast multipole method performs matrix multiplication on kernel matrices of dimension N in time almost linear in N by using the linear algebraic framework of hierarchical matrices. In light of this success, we propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. When applied to many physical kernel matrices, our method can improve the runtime of solving quantum linear systems of dimension N to O(κpolylog(Nε)) , where κ and ε are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of N , exponentially improves over prior quantum linear systems algorithms in the case of dense and full-rank kernel matrices. We discuss possible applications of our methodology in solving integral equations and accelerating computations in N-body problems.
Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function k(x,x′) , have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast multipole method performs matrix multiplication on kernel matrices of dimension N in time almost linear in N by using the linear algebraic framework of hierarchical matrices. In light of this success, we propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. When applied to many physical kernel matrices, our method can improve the runtime of solving quantum linear systems of dimension N to O(κpolylog(Nε)) , where κ and ε are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of N , exponentially improves over prior quantum linear systems algorithms in the case of dense and full-rank kernel matrices. We discuss possible applications of our methodology in solving integral equations and accelerating computations in N-body problems.
While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix A and a vector b the task is to find the vector x such that Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional A with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of A, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of A is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of A and the vector of Euclidean norms of the rows of A.
Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing $n\ifmmode\times\else\texttimes\fi{}n$ dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct $\ensuremath{\epsilon}$-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency ω multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a O(poly(n)) gate complexity, where n is the number of qubits, in the worst-case scenario used for banded matrices, and O(n) when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.