HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearclassicalthancouldfasterperformcomputeralgebraquantum

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#76525, answer score: 3

Revisions (0)

No revisions yet.