Quantum Verification of Matrix Products
Abstract
Description
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.
15 pages, submitted; v2: rewritten, clarified, and fixed some proofs
15 pages, submitted; v2: rewritten, clarified, and fixed some proofs