<p>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 (<a href="http://arxiv.org/abs/0811.3171">arXiv:0811.3171</a>) 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.</p>

CC BY-SA 2.5
2010-11-15T09:05:21.457Z
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.
Aram Harrow
CC BY-SA 2.5
2010-11-15T10:54:20.720Z
@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?
Joe Fitzsimons
CC BY-SA 2.5
2010-12-01T09:37:36.440Z
Yes, it works for non-sparse matrices whenever we know good ways of simulating those Hamiltonians.  So maybe something nontrivial is possible here.
Aram Harrow
CC BY-SA 3.0
2011-05-23T14:27:04.563Z
@Aram: With the encoding you use, don't we also get the Fourier transform of all sparse matrices via the QFT?
Joe Fitzsimons
CC BY-SA 3.0
2011-06-15T13:24:01.310Z
@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.
Aram Harrow
CC BY-SA 3.0
2011-06-18T21:41:01.710Z
@Aram: Yes, I know, but I think the Fourier domain is probably particularly useful as it plays such a massive role in signal processing, etc.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-13T15:21:41.807Z
2010-11-13T15:51:51.160Z
2010-11-13T15:51:51.160Z
Joe Fitzsimons
<p>In <a href="http://arxiv.org/abs/quant-ph/0409035v2">arXiv:quant-ph/0409035v2</a> Buhrman and Spalek present a quantum algorithm beating the Coppersmith-Winograd algorithm in cases where the output matrix has few nonzero entries.</p>

<p><strong>Update:</strong> There is also a slightly improved quantum algorithm by <a href="http://theorie.informatik.uni-ulm.de/Personen/Thierauf/Papers/quant-walk.pdf">Dörn and Thierauf</a>.</p>

<p><strong>Update:</strong> There is an improved quantum algorithm by <a href="http://francoislegall.com/LeGallSODA12-p.pdf">Le Gall</a> beating Burhman and Spalek in general.</p>

CC BY-SA 3.0
2012-05-16T08:12:34.693Z
A recent improvement to $nw^{1/2}$ in the case of Boolean matrix product is http://arxiv.org/abs/1112.5855, with also matching lower bounds.
Abel Molina
CC BY-SA 2.5
2010-11-13T13:09:38.837Z
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)$.
Daniel Apon
CC BY-SA 2.5
2010-11-13T14:02:43.840Z
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''.)
virgi
CC BY-SA 3.0
2010-11-13T09:35:31.470Z
2011-11-25T15:50:56.610Z
2011-11-25T15:50:56.610Z
Martin Schwarz
<p>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?</p>

<reference-request><quantum-computing><matrix-product>
Quantum matrix multiplication?
Henry Yuen
# Quantum matrix multiplication?

(Asked by: username_0 on 2010-11-13)

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?

**Tags:** reference-request, quantum-computing, matrix-product


---

## 2 answers

### Answer by username_3 on 2010-11-13. Score: 28 | Accepted answer

In [arXiv:quant-ph/0409035v2](http://arxiv.org/abs/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](http://theorie.informatik.uni-ulm.de/Personen/Thierauf/Papers/quant-walk.pdf).

**Update:** There is an improved quantum algorithm by [Le Gall](http://francoislegall.com/LeGallSODA12-p.pdf) beating Burhman and Spalek in general.

> **Comments:**
> **username_5**: 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)$.  
> **username_6**: 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''.)  
> **username_4**: A recent improvement to $nw^{1/2}$ in the case of Boolean matrix product is http://arxiv.org/abs/1112.5855, with also matching lower bounds.  

---

### Answer by username_1 on 2010-11-13. Score: 15

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](http://arxiv.org/abs/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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @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?  
> **username_2**: Yes, it works for non-sparse matrices whenever we know good ways of simulating those Hamiltonians.  So maybe something nontrivial is possible here.  
> **username_1**: @Aram: With the encoding you use, don't we also get the Fourier transform of all sparse matrices via the QFT?  
> **username_2**: @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.  
> **username_1**: @Aram: Yes, I know, but I think the Fourier domain is probably particularly useful as it plays such a massive role in signal processing, etc.  

---

