Quantum Verification of Matrix Products
| dc.creator | Buhrman, Harry | |
| dc.creator | Spalek, Robert | |
| dc.date | 2004-09-06 | |
| dc.date | 2005-07-06 | |
| dc.date.accessioned | 2026-07-07T06:10:48Z | |
| dc.date.available | 2026-07-07T06:10:48Z | |
| dc.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. | |
| dc.description | 15 pages, submitted; v2: rewritten, clarified, and fixed some proofs | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0409035 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0409035 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92354 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum Verification of Matrix Products | |
| dc.type | text |