7
$\begingroup$

I'm exploring quantum computers for a semester project. I'm mainly interested in making faster matrix calculations than a regular computer.

I was wondering what arithmetic operations (irrespective of how simple or complex they are) are faster on a quantum computer? Also, by what factor does the time complexity improve?

Note - I'm a newbie to quantum computers. So, apologies if this question is too vague than the usual questions here.

Improve this question
$\endgroup$
2
  • $\begingroup$ In such comparisons, does one generally assume the matrix is given classically and one needs to encode it to a quantum state, do some operations and finally measure to get a classical output? If so, the encoding process should also be counted towards the time complexity, correct? $\endgroup$
    – user1936752
    Commented Feb 4, 2021 at 13:11
  • $\begingroup$ Do you mean, like efficient matmul on a quantum computer? You should check out this paper: nature.com/articles/srep24910 $\endgroup$
    – Cuhrazatee
    Commented Feb 4, 2021 at 20:55

1 Answer 1

Reset to default
4
$\begingroup$

ANSWER MADE CW

Arguably the one thing that a quantum computer can do quickly, as long as the matrix is defined in the appropriate manner, is the quantum Fourier transform (QFT). Much as the classical fast Fourier transform (FFT) is the workhouse of many classical matrix algorithms, the QFT is the basis for many such quantum matrix algorithms.

  • For example, a standard answer about quantum algorithms for matrices is the quantum algorithm for linear systems - the HHL algorithm of Harrow, Hassidm, and Lloyd. This algorithm allows one to invert a matrix.

  • Another interesting matrix algorithm is that of Janzing and Wocjan on determining the elements of a power of a matrix.

  • One algorithm that I haven't studied in detail but nonetheless seems interesting is Wang's method of determining the effective resistance between two nodes in a graph - if the network were considered to be an adjacency matrix of resistors.

Without knowing more about the OP's background, at least hearing of the importance of the QFT and its embodiment for quantum phase estimation (QPE) is critical to understand how quantum computers can be useful for matrix algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.