Lab Home  Phone  Search  


In the System of Linear Equations (SLE) problem, an invertible N x N matrix A, an Ndimensional 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 wellconditioned, sparse and rowcomputable, 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 â€œblockencodableâ€, i.e. M forms the upper left block of a unitary operator UM which can be implemented by a polynomialsize 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 