Quantum verification of matrix products
Harry Buhrman, Robert Špalek · Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 · 2006
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.