Quantum Verification of Matrix Products

Details Quantum Verification of Matrix Products Quantum Verification of Matrix Products

2004-09-06

arxiv.org/abs/quant-ph/0409035v2

Physics

Quantum Physics

15 pages, submitted; v2: rewritten, clarified, and fixed some proofs

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Verification of Matrix Products does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Verification of Matrix Products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Verification of Matrix Products will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375251