Could a quantum computer perform linear algebra faster than a classical computer?

Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has anyone created a quantum algorithm for linear algebra, and what is it's running time? In theory, an operation such as matrix-matrix multiplication is highly parallelizable, however in practice it requires a lot of work to implement parallel matrix-matrix multiplication that runs quickly. Would a quantum computer provide any practical advantage?

Here are some pointers:

• By the way, these pointers were among the first few results on Google. – Yuval Filmus Jun 8 '17 at 15:57
• Your answer is based on links, is this correct? – user53451 Jun 8 '17 at 16:00
• Indeed so. I confess that I haven't actually read the papers. – Yuval Filmus Jun 8 '17 at 16:05
• It's okay, at least one answer. – user53451 Jun 8 '17 at 16:11
• I'd also recommend Scott Aaronson's summary of these algorithms: Quantum Machine Learning Algorithms: Read the Fine Print – Craig Gidney Jun 9 '17 at 0:16

Mathematical model with matrix

The HHL algorithm can be found in the already mentioned links, let's implement it on a quantum computer. We want to solve a system of linear equations $A|x> = |b>$ From this $|x> = A^{-1} |b>$

With matrix $A = \begin{bmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{bmatrix}$ and input $b = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

$A^{-1} . |b> = \begin{bmatrix} 0.75 \\ -0.25 \end{bmatrix}$

Quantum circuit design

We use the quantumcircuit in arXiv 1302.1210 with 2 qubits,one qubit with input b. The second qubit is a ancilla bit and a one on the output means output is ready. The circuit uses a PEA circuit (gate R) as input and an inverse PEA circuit at the output. Phase estimation or PEA is used to decompose the quantum state of |b> in a particular basis and the eigenvalues of A are stored in an eigenvalue register. Rotation gate R(y) transforms with an angle depending on the value in the eigenvalue register. Then we run a PEA in reverse to uncompute the eigenvalue and find the answer. In the quantumcomputer, only the possibility of finding a 1 or 0 can be measured.

Gate parameters

R is the matrix of eigenvectors of matrix A and Rdagger is it's transpose. From the Matrix A we find the eigenvalues $\lambda_{1} = 1 \; \lambda_{2} = 2$ The rotation angle of the Y rotation gate is determinded by the ratio of eigenvalues. Rotation angle $\theta = -2arccos \dfrac{\lambda_{1}}{\lambda_{2}} \\$

$\theta = -2arccos(1/2)= -2\dfrac{\pi}{3}$. Implement this circuit in the IBM quantumcomputer with the link to the circuit:

quantumexperience.ng.bluemix.net/qx/editor?codeId=9da9d545772273118671911e1078ac42

• This looks more like a blog post. How does it answer the question? – Yuval Filmus Jun 21 '17 at 15:48
• The first part of the question about the algorithm was already answered by the pointers with the links to HHL algorithm. The second part of the question is about the trade-off between theory and practical implications with matrix multiplications. I did not answer that but at least I showed a possible implementation and therefore something to analyze and find a conclusion. – Bram Jun 21 '17 at 19:29