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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
-
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$ Nov 13, 2010 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$– virgiNov 13, 2010 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$ May 16, 2012 at 8:12
$\begingroup$
$\endgroup$
6
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.
-
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$ Nov 15, 2010 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$ Nov 15, 2010 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$ Dec 1, 2010 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$ May 23, 2011 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$ Jun 15, 2011 at 13:24