30
$\begingroup$

It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat the complexity of the Coppersmith-Winograd algorithm using quantum computers?

$\endgroup$
26
$\begingroup$

In arXiv:quant-ph/0409035v2 Buhrman and Spalek present a quantum algorithm beating the Coppersmith-Winograd algorithm in cases where the output matrix has few nonzero entries.

Update: There is also a slightly improved quantum algorithm by Dörn and Thierauf.

Update: There is an improved quantum algorithm by Le Gall beating Burhman and Spalek in general.

$\endgroup$
  • 1
    $\begingroup$ This was new to me (I know little about quantum results), but glancing at the paper, the result was even more surprising! If, for $A_{nxm}B_{mxn}=C_{nxn}$ matrix multiplications, there are $o(\sqrt{n})$ nonzero entries in the output, the product can be computed in sub-quadratic time, $o(nm)$. $\endgroup$ – Daniel Apon Nov 13 '10 at 13:09
  • 10
    $\begingroup$ There's a slight improvement to this for the special case of Boolean matrix product, min{$n^{1.3}w^{17/30}, n^2 + w^{47/60} n^{13/15}$} when there are $w$ nonzeroes in the output. (It appeared in our FOCS'10 paper ``Subcubic Equivalences Between Path, Matrix, and Triangle Problems''.) $\endgroup$ – virgi Nov 13 '10 at 14:02
  • 3
    $\begingroup$ A recent improvement to $nw^{1/2}$ in the case of Boolean matrix product is arxiv.org/abs/1112.5855, with also matching lower bounds. $\endgroup$ – Abel Molina May 16 '12 at 8:12
14
$\begingroup$

If you are interested in multiplying two matrices and getting back the full classical result, then Martin's response is probably a definitive answer to your question. However, if you want to calculate something like $v^\dagger X Y v$ then you can do this extremely efficiently. Harrow, Hassidim and Lloyd have an algorithm (arXiv:0811.3171) for calculating $v X^{-1} v$ which is only logarithmic in the dimensions of the matrix $X$ for sparse matrices. It seems relatively straight forward to adapt this approach to calculate products rather than inverses.

$\endgroup$
  • 3
    $\begingroup$ In this case, the runtime will still depend on the condition number of the matrices, and the matrices will have to have complex entries. Also, if X and Y are sparse, then so is their product, and $v'XYv$ can be estimated classically with the same kind of exponential speedup using random sampling. $\endgroup$ – Aram Harrow Nov 15 '10 at 9:05
  • $\begingroup$ @Aram: Good point! I know your algorithm works for sparse matrices, but I was under the impression that it could be made to work for certain non-sparse matrices too. Is this correct? $\endgroup$ – Joe Fitzsimons Nov 15 '10 at 10:54
  • $\begingroup$ Yes, it works for non-sparse matrices whenever we know good ways of simulating those Hamiltonians. So maybe something nontrivial is possible here. $\endgroup$ – Aram Harrow Dec 1 '10 at 9:37
  • 1
    $\begingroup$ @Aram: With the encoding you use, don't we also get the Fourier transform of all sparse matrices via the QFT? $\endgroup$ – Joe Fitzsimons May 23 '11 at 14:27
  • $\begingroup$ @Joe: I just noticed this. Yes, those matrices (which you can think of as being sparse in the momentum basis) are also usable. This is nothing unique to our algorithm. Rather it's a statement about the class of Hamiltonians we know how to simulate on a quantum computer. $\endgroup$ – Aram Harrow Jun 15 '11 at 13:24

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.