arXiv:1912.12212 · Physical Review A

Block-encoding-based quantum algorithm for linear systems with displacement structures

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan, Su‐Juan Qin, Fei Gao, Qiaoyan Wen

Published Dec 8, 2021• 39 citations

Abstract

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.

DOI: 10.1103/physreva.104.062414

Related papers

Faster Quantum-inspired Algorithms for Solving Linear Systems

Changpeng Shao, Ashley Montanaro

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $ A{\bf x}= {\bf b} $ , we show that there is a classical algorithm that outputs a data structure for $ {\bf x} $ allowing sampling and querying to the entries, where $ {\bf x} $ is such that $ \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert $ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $ \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) $ , where $ \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert $ and $ \kappa = \Vert A\Vert \Vert A^{+}\Vert $ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity $ \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) $ . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution $ {\bf x} $ in time $ \widetilde{O}(\kappa _F^2) $ , while the best quantum algorithm known returns $ | {\bf x} \rangle $ in time $ \widetilde{O}(\kappa _F) $ when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

arXiv:2103.10309ACM Transactions on Quantum ComputingMar 25, 202219 citations

Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra

Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd

arXiv:2201.11329QuantumDec 13, 202216 citations

Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression

Kun Tang, Jun Lai

quant-pharXiv:2602.09745Feb 11, 20260 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

arXiv:2203.10236SIAM Journal on Matrix Analysis and ApplicationsMar 11, 202478 citations

Toward speedup without quantum coherent access

Nhat A. Nghiem

quant-pharXiv:2602.20781Feb 25, 20260 citations

Row and column iteration methods to solve linear systems on a quantum computer

Changpeng Shao, Hua Xiang

arXiv:1905.11686Physical Review AFeb 19, 202017 citations

arXiv:1912.12212 · Physical Review A

Block-encoding-based quantum algorithm for linear systems with displacement structures

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan, Su‐Juan Qin, Fei Gao, Qiaoyan Wen

Published Dec 8, 2021• 39 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.1103/physreva.104.062414

Related papers

Faster Quantum-inspired Algorithms for Solving Linear Systems

Changpeng Shao, Ashley Montanaro

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $A{\bf x}= {\bf b}$ , we show that there is a classical algorithm that outputs a data structure for ${\bf x}$ allowing sampling and querying to the entries, where ${\bf x}$ is such that $\Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert$ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $\widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2)$ , where $\kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert$ and $\kappa = \Vert A\Vert \Vert A^{+}\Vert$ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity $\widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4)$ . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution ${\bf x}$ in time $\widetilde{O}(\kappa _F^2)$ , while the best quantum algorithm known returns $| {\bf x} \rangle$ in time $\widetilde{O}(\kappa _F)$ when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $ A{\bf x}= {\bf b} $ , we show that there is a classical algorithm that outputs a data structure for $ {\bf x} $ allowing sampling and querying to the entries, where $ {\bf x} $ is such that $ \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert $ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $ \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) $ , where $ \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert $ and $ \kappa = \Vert A\Vert \Vert A^{+}\Vert $ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity $ \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) $ . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution $ {\bf x} $ in time $ \widetilde{O}(\kappa _F^2) $ , while the best quantum algorithm known returns $ | {\bf x} \rangle $ in time $ \widetilde{O}(\kappa _F) $ when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

arXiv:2103.10309ACM Transactions on Quantum ComputingMar 25, 202219 citations

Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra

Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd

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.

arXiv:2201.11329QuantumDec 13, 202216 citations

Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression

Kun Tang, Jun Lai

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.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.

quant-pharXiv:2602.09745Feb 11, 20260 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

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.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.

arXiv:2203.10236SIAM Journal on Matrix Analysis and ApplicationsMar 11, 202478 citations

Toward speedup without quantum coherent access

Nhat A. Nghiem

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.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.

quant-pharXiv:2602.20781Feb 25, 20260 citations

Row and column iteration methods to solve linear systems on a quantum computer

Changpeng Shao, Hua Xiang

We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size $n$ over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size $n$ over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.

arXiv:1905.11686Physical Review AFeb 19, 202017 citations

n\ifmmode\times\else\texttimes\fi{}n

\ensuremath{\epsilon}

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system

A{\bf x}= {\bf b}

, we show that there is a classical algorithm that outputs a data structure for

{\bf x}

allowing sampling and querying to the entries, where

{\bf x}

is such that

\Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert

. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is

\widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2)

, where

\kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert

and

\kappa = \Vert A\Vert \Vert A^{+}\Vert

. This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity

\widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4)

. Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution

{\bf x}

in time

\widetilde{O}(\kappa _F^2)

, while the best quantum algorithm known returns

| {\bf x} \rangle

in time

\widetilde{O}(\kappa _F)

when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

n

over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.