  We study quantum algorithms that learn properties of a matrix using queries
that return its action on an input vector. We show that for various problems,
including computing the trace, determinant, or rank of a matrix or solving a
linear system that it specifies, quantum computers do not provide an asymptotic
speedup over classical computation. On the other hand, we show that for some
problems, such as computing the parities of rows or columns or deciding if
there are two identical rows or columns, quantum computers provide exponential
speedup. We demonstrate this by showing equivalence between models that provide
matrix-vector products, vector-matrix products, and vector-matrix-vector
products, whereas the power of these models can vary significantly for
classical computation.
