Abstract
We present a quantum algorithm that verifies a product of two n*n matrices over any field with bounded error in worst-case time n^\{5/3\} and expected time n^\{5/3\} / min(w,sqrt(n))^\{1/3\}, where w is the number of wrong entries. This improves the previous best algorithm that runs in time n^\{7/4\}. We also present a quantum matrix multiplication algorithm that is efficient when the result has few nonzero entries.