Citation: Harrow, Aram W., Avinatan Hassidim, and Seth Lloyd. "Quantum algorithm for linear systems of equations." Physical review letters 103.15 (2009): 150502.
Web: https://arxiv.org/abs/0811.3171
Tags: Computer-scientific, Quantum-advantage
This paper gives a quantum advantage for a liner algebra problem. It is stated as follows. Let A,B be operators, and let b be a vector. This algorithm approximately computes the expectation value (x^T)Bx, where x is a solution to the equation Ax=b. Here, all operators act on an N dimensional space (where N is exponentially large), and are sparse in the sense that only polylog many of their entries are non-zero.
The way this algorithm works is by giving a procedure to compute the approximate solution x to Ax=b whenever A is Hermitian and b is a unit vector, given as quantum states. From the quantum state x it is impossible to recover the vector x, because this would require a number of rounds of measurement of order N. However, the expectation value of x under any operator can be readily measured. Hence, the conclusion. There are various tricks used to reduce the general case to the case that A is Hermitian and b is a unit vector.
One could imagine that any classical algorithm would need to compute x before it can compute the expectation value of x under any operator. This vector takes O(N) space to write down, so it must be exponential time to compute. The authors prove several results which seem strongly to imply that their algorithm is optimal, and that it is super-polynomial better than any classical algorithm.
Their algorithm is extremely elegant. It works as follows. First, the vector b is expressed as a quantum state |b>. This state can be expressed in the A-eigenbasis as a sum, \sum_{i=1}^Nc_i |u_i>, where |u_i> are eigenvectors of A. Letting |lambda_i> denote the eigenvalue of A, the authors show that one can construct the state \sum_{i=1}^Nc_i |u_i>|\lambda_i>. This is done by combing efficient algorithms for the simulation of Hamiltonian evolution, and quantum phase estimation. The next step is to act by the operator |\lambda_i> -> \lambda_i^{-1}|\lambda_i>. This operator is non-unitary so has a chance of failing, which is included in the runtime estimate. The last step is to then uncompute the |\lambda_i>, yielding the state \sum_{i=1}^N\lambda_i^{-1} c_i |u_i>. This state is exactly a solution to the equation A |x>=|b>, so the construction is complete!
It is not on a fundamental level surprising that quantum computers yield advantage in numerical linear algebra. In a sense that is the only advantage they offer - they are good for multiplying big sparse matrices. This is just a striking and concrete instance of this phenomenon, which firmly establishes a super-polynomial quantum advantage on real numerical linear algebra problems.