We transform the problem of solving linear system of equations $A\mathbf{x}=\mathbf{b}$ to a problem of finding the right singular vector with singular value zero of an augmented matrix $C$, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left( sκ\log \left( 1/ε\right) \right) $ for a $s$-sparse matrix $C$, where $κ$ is the condition number of the matrix $A$, and $ε$ is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[sκ+ \log\left( 1/ε\right)/\log \log \left( 1/ε\right) \right] $. Both algorithms meet the optimal query complexity in $κ$, and are simpler than previous algorithms.
We transform the problem of solving linear system of equations Ax=b to a problem of finding the right singular vector with singular value zero of an augmented matrix C, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of O(sκlog(1/ε)) for a s-sparse matrix C, where κ is the condition number of the matrix A, and ε is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as O[sκ+log(1/ε)/loglog(1/ε)]. Both algorithms meet the optimal query complexity in κ, and are simpler than previous algorithms.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.
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.
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 O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and 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.
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 O(sn∥M∥maxκ2/ϵ2), where κ is the condition number of the matrix of eigenvectors.
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal O(dκlog(1/ϵ)) query complexity for a d-sparse matrix, where κ is the condition number, and ϵ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.
Given a matrix A of dimension M×N and a vector b, the quantum linear system (QLS) problem asks for the preparation of a quantum state ∣y⟩ proportional to the solution of Ay=b. Existing QLS algorithms have runtimes that scale linearly with the condition number κ(A), the sparsity of A, and logarithmically with inverse precision, but often overlook structural properties of b, whose alignment with A's eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector b. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix H=[A,−b], the inverse precision, the ℓ2 norm of the solution y=A+b, and a new instance-dependent parameter ET=∑i=1Mpi2⋅di, where p=(AA⊤)+b, and di denotes the squared ℓ2 norm of the i-th row of H. We also introduce a structure-aware rescaling technique tailored to the solution y=A+b. Unlike left preconditioning methods, which transform the linear system to DAy=Db, our approach applies a right rescaling matrix, reformulating the linear system as ADz=b. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.