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.

  • $\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 Feb 4 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 Feb 4 at 20:55


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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