Quantum Verification of Matrix Products
classification
🪐 quant-ph
keywords
algorithmquantumtimeentriesmatrixbestboundedefficient
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Universal Matrix Multiplication on Quantum Computer
Proposes a QFT-based quantum matrix multiplication framework claiming O(n) adder and O(n²) multiplier gate complexity plus a quantum Strassen variant for potential ML acceleration.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.