 |
Center for Nonlinear Studies |
In the System of Linear Equations (SLE) problem, an invertible N x N matrix A, an N-dimensional vector b and another Hermitian N x N matrix M are given, and the task is to compute x*Mx, where x is the solution vector to the equation Ax = b. A quantum algorithm by Harrow, Hassidim and Lloyd (HHL) generates efficiently, i.e. via a circuit of size polylog(N), the solution as a quantum state x, provided A is well-conditioned, sparse and row-computable, and provided the initial vector as a quantum state b can be generated efficiently. In this work, we show by constructing an explicit quantum algorithm that the expectation value x*Mx can be computed efficiently if M is “block-encodableâ€, i.e. M forms the upper left block of a unitary operator UM which can be implemented by a polynomial-size quantum circuit. Our algorithm has query complexity with quasilinear dependence on inverse error. We further show that this dependence on error is nearly optimal. Our algorithm builds on HHL algorithm to provide complete and efficient solution of SLE for any sparse matrix {M} and beyond, therefore providing verifiable conditions under which a practical application based on SLE is tractable on a quantum computer.
Host: Gopi Muraleedharan