arXiv:1807.07820

Quantum Arnoldi and conjugate gradient iteration algorithm

Changpeng Shao

Published Jul 20, 2018• 1 citation

Abstract

Arnoldi method and conjugate gradient method are important classical iteration methods in solving linear systems and estimating eigenvalues. Their efficiency often affected by the high dimension of the space, where quantum computer can play a role in. In this work, we establish their corresponding quantum algorithms. To achieve high efficiency, a new method about linear combination of quantum states will be proposed. The final complexity of quantum Arnoldi iteration method is $O(m^{3+\log (m/ε)}(\log n)^2 /ε^4)$ and the final complexity of quantum conjugate gradient iteration method is $O(m^{1+\log m/ε} (\log n)^2 κ/ε)$, where $ε$ is precision parameter, $m$ is the iteration steps, $n$ is the dimension of space and $κ$ is the condition number of the coefficient matrix of the linear system the conjugate gradient method works on. Compared with the classical methods, whose complexity are $O(mn^2+m^2n)$ and $O(mn^2)$ respectively, these two quantum algorithms provide us more efficient methods to solve linear systems and to compute eigenvalues and eigenvectors of general matrices. Different from the work \cite{rebentros}, the complexity here is almost polynomial in the iteration steps. Also this work is more general than the iteration method considered in \cite{kerenidis}.

DOI: 10.48550/arxiv.1807.07820

Related papers

Computing eigenvalues of matrices in a quantum computer

Changpeng Shao

Dec 17, 20194 citations

Computing eigenvalues of diagonalizable matrices in a quantum computer

Changpeng Shao

arXiv:1912.08015Dec 17, 20195 citations

New Quantum Algorithm For Solving Linear System of Equations

Nhat A. Nghiem

arXiv:2502.13630Feb 19, 20250 citations

Quantum conjugate gradient method using the positive-side quantum eigenvalue transformation

Toyoizumi, Kiichiro, Kaito Wada, Naoki Yamamoto +1 more

arXiv:2404.02713Apr 3, 20240 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

From linear combination of quantum states to Grover's searching algorithm

Changpeng Shao

arXiv:1807.09693Jul 22, 20186 citations

arXiv:1807.07820

Quantum Arnoldi and conjugate gradient iteration algorithm

Changpeng Shao

Published Jul 20, 2018• 1 citation

arXiv HTML PDF

Abstract

O(m^{3+\log (m/ε)}(\log n)^2 /ε^4)

and the final complexity of quantum conjugate gradient iteration method is

O(m^{1+\log m/ε} (\log n)^2 κ/ε)

, where

ε

is precision parameter,

m

is the iteration steps,

n

is the dimension of space and

κ

is the condition number of the coefficient matrix of the linear system the conjugate gradient method works on. Compared with the classical methods, whose complexity are

O(mn^2+m^2n)

and

O(mn^2)

respectively, these two quantum algorithms provide us more efficient methods to solve linear systems and to compute eigenvalues and eigenvectors of general matrices. Different from the work \cite{rebentros}, the complexity here is almost polynomial in the iteration steps. Also this work is more general than the iteration method considered in \cite{kerenidis}.

DOI: 10.48550/arxiv.1807.07820

Related papers

Computing eigenvalues of matrices in a quantum computer

Changpeng Shao

Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size $n$ of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If $M$ is $s$ sparse, then the complexity is $\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)$ , where $\kappa$ is the condition number of the matrix of eigenvectors.Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size $n$ of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If $M$ is $s$ sparse, then the complexity is $\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)$, where $\kappa$ is the condition number of the matrix of eigenvectors.

Dec 17, 20194 citations

Computing eigenvalues of diagonalizable matrices in a quantum computer

Changpeng Shao

Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix $M$ is $s$ -sparse, the complexity is $\widetilde{O}(sρ^2 κ^2/ε^2)$ for diagonalizable matrices that only have real eigenvalues, and $\widetilde{O}(sρ\|M\|_{\max} /ε^2)$ for normal matrices. Here $ρ$ is an upper bound of the eigenvalues, $κ$ is the conditioning of the eigenvalue problem, and $ε$ is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix $M$ is $s$-sparse, the complexity is $\widetilde{O}(sρ^2 κ^2/ε^2)$ for diagonalizable matrices that only have real eigenvalues, and $\widetilde{O}(sρ\|M\|_{\max} /ε^2)$ for normal matrices. Here $ρ$ is an upper bound of the eigenvalues, $κ$ is the conditioning of the eigenvalue problem, and $ε$ is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.

arXiv:1912.08015Dec 17, 20195 citations

New Quantum Algorithm For Solving Linear System of Equations

Nhat A. Nghiem

Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.

arXiv:2502.13630Feb 19, 20250 citations

Quantum conjugate gradient method using the positive-side quantum eigenvalue transformation

Toyoizumi, Kiichiro, Kaito Wada, Naoki Yamamoto +1 more

Quantum algorithms are still challenging to solve linear systems of equations on real devices. This challenge arises from the need for deep circuits and numerous ancilla qubits. We introduce the quantum conjugate gradient (QCG) method using the quantum eigenvalue transformation (QET). The circuit depth of this algorithm depends on the square root of the coefficient matrix's condition number $κ$ , representing a square root improvement compared to the previous quantum algorithms, while the total query complexity worsens. The number of ancilla qubits is constant, similar to other QET-based algorithms. Additionally, to implement the QCG method efficiently, we devise a QET-based technique that uses only the positive side of the polynomial (denoted by $P(x)$ for $x\in[0,1]$ ). We conduct numerical experiments by applying our algorithm to the one-dimensional Poisson equation and successfully solve it. Based on the numerical results, our algorithm significantly improves circuit depth, outperforming another QET-based algorithm by three to four orders of magnitude.Quantum algorithms are still challenging to solve linear systems of equations on real devices. This challenge arises from the need for deep circuits and numerous ancilla qubits. We introduce the quantum conjugate gradient (QCG) method using the quantum eigenvalue transformation (QET). The circuit depth of this algorithm depends on the square root of the coefficient matrix's condition number $κ$, representing a square root improvement compared to the previous quantum algorithms, while the total query complexity worsens. The number of ancilla qubits is constant, similar to other QET-based algorithms. Additionally, to implement the QCG method efficiently, we devise a QET-based technique that uses only the positive side of the polynomial (denoted by $P(x)$ for $x\in[0,1]$). We conduct numerical experiments by applying our algorithm to the one-dimensional Poisson equation and successfully solve it. Based on the numerical results, our algorithm significantly improves circuit depth, outperforming another QET-based algorithm by three to four orders of magnitude.

arXiv:2404.02713Apr 3, 20240 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

From linear combination of quantum states to Grover's searching algorithm

Changpeng Shao

Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three different forms to achieve LCU. Different from previous algorithms [Childs-linear-system,Clader,Long11], the complexity now only depends on the number of the unitaries and the precision. So it will play more important role in the design of quantum algorithms when the number of unitaries is small, such as quantum iteration algorithms. %Since in iteration algorithms, $m$ often refers to the iteration steps, which is small if the iteration algorithms are efficient. Moreover, as an application of the new LCU, three new quantum algorithms to the searching problem will be proposed, which will provide us new insights into Grover's searching algorithm. We also show that the problem of LCU is closely related to the problem of if we can efficiently implement $U^t$ for $0Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three different forms to achieve LCU. Different from previous algorithms [Childs-linear-system,Clader,Long11], the complexity now only depends on the number of the unitaries and the precision. So it will play more important role in the design of quantum algorithms when the number of unitaries is small, such as quantum iteration algorithms. %Since in iteration algorithms, $m$ often refers to the iteration steps, which is small if the iteration algorithms are efficient. Moreover, as an application of the new LCU, three new quantum algorithms to the searching problem will be proposed, which will provide us new insights into Grover's searching algorithm. We also show that the problem of LCU is closely related to the problem of if we can efficiently implement $U^t$ for $0

arXiv:1807.09693Jul 22, 20186 citations

O(m^{3+\log (m/ε)}(\log n)^2 /ε^4)

and the final complexity of quantum conjugate gradient iteration method is

O(m^{1+\log m/ε} (\log n)^2 κ/ε)

, where

ε

is precision parameter,

m

is the iteration steps,

n

is the dimension of space and

κ

is the condition number of the coefficient matrix of the linear system the conjugate gradient method works on. Compared with the classical methods, whose complexity are

O(mn^2+m^2n)

and

O(mn^2)

n

of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If

M

s

sparse, then the complexity is

\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)

, where

\kappa

is the condition number of the matrix of eigenvectors.

M

s

-sparse, the complexity is

\widetilde{O}(sρ^2 κ^2/ε^2)

for diagonalizable matrices that only have real eigenvalues, and

\widetilde{O}(sρ\|M\|_{\max} /ε^2)

for normal matrices. Here

ρ

is an upper bound of the eigenvalues,

κ

is the conditioning of the eigenvalue problem, and

ε

is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.

κ

, representing a square root improvement compared to the previous quantum algorithms, while the total query complexity worsens. The number of ancilla qubits is constant, similar to other QET-based algorithms. Additionally, to implement the QCG method efficiently, we devise a QET-based technique that uses only the positive side of the polynomial (denoted by

P(x)

for

x\in[0,1]

). We conduct numerical experiments by applying our algorithm to the one-dimensional Poisson equation and successfully solve it. Based on the numerical results, our algorithm significantly improves circuit depth, outperforming another QET-based algorithm by three to four orders of magnitude.

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.

m

often refers to the iteration steps, which is small if the iteration algorithms are efficient. Moreover, as an application of the new LCU, three new quantum algorithms to the searching problem will be proposed, which will provide us new insights into Grover's searching algorithm. We also show that the problem of LCU is closely related to the problem of if we can efficiently implement

U^t

for $0