Quantum verification of matrix products

Abstract

We present a quantum algorithm that verifies a product of two n × n matrices over any integral domain with bounded error in worst-case time O(n5/3) and expected time O(n5/3/ min(w, √n)1/3), where ω is the number of wrong entries. This improves the previous best algorithm [3] that runs in time O(n7/4). We also present a quantum matrix multiplication algorithm that is efficient when the result has few nonzero entries.