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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
Here are some pointers:
Quantum algorithm for linear systems of equations by Harrow, Hassidim, and Lloyd. This paper shows how to solve sparse systems of linear equations very quickly.
Quantum Algorithms for Linear Algebra and Machine Learning by Anupam Prakash. This PhD thesis proposes a quick algorithm for singular value estimation, and presents several applications.
answered Jun 8, 2017 at 15:56
-
$\begingroup$ By the way, these pointers were among the first few results on Google. $\endgroup$ Commented Jun 8, 2017 at 15:57
-
$\begingroup$ Your answer is based on links, is this correct? $\endgroup$– user53451Commented Jun 8, 2017 at 16:00
-
$\begingroup$ Indeed so. I confess that I haven't actually read the papers. $\endgroup$ Commented Jun 8, 2017 at 16:05
-
$\begingroup$ It's okay, at least one answer. $\endgroup$– user53451Commented Jun 8, 2017 at 16:11
-
1$\begingroup$ I'd also recommend Scott Aaronson's summary of these algorithms: Quantum Machine Learning Algorithms: Read the Fine Print $\endgroup$ Commented Jun 9, 2017 at 0:16
$\begingroup$
$\endgroup$
2
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
-
1$\begingroup$ This looks more like a blog post. How does it answer the question? $\endgroup$ Commented Jun 21, 2017 at 15:48
-
$\begingroup$ 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. $\endgroup$– BramCommented Jun 21, 2017 at 19:29