Quantum matrix multiplication? 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?
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.