Quantum verification of matrix products
From MaRDI portal
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.
Cited in
(36)- A note on the search for k elements via quantum walk
- Quantum algorithm design: techniques and applications
- Quantum walks: a comprehensive review
- Quantum walks with memory on cycles
- Quantum search with variable times
- Efficient quantum circuits for Szegedy quantum walks
- Efficiently correcting matrix products
- On the hitting times of quantum versus random walks
- Quantum walks can find a marked element on any graph
- Szegedy quantum walks with memory on regular graphs
- Search on vertex-transitive graphs by lackadaisical quantum walk
- Three-state quantum walk on the Cayley graph of the dihedral group
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- Efficiently correcting matrix products
- Quantum complexity of Boolean matrix multiplication and related problems
- Quantum Walk Based Search Algorithms
- Probability distributions for Markov chain based quantum walks
- The quantum walk search algorithm: factors affecting efficiency
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- Quantum Random Walks – New Method for Designing Quantum Algorithms
- Quantum Walks with Multiple or Moving Marked Locations
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- Quantum walks on two-dimensional grids with multiple marked locations
- Improvement of quantum walks search algorithm in single-marked vertex graph
- Quantum algorithm for lexicographically minimal string rotation
- On the relationship between continuous- and discrete-time quantum walk
- Theoretical computer science: computational complexity
- Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
- A direct reduction from the polynomial to the adversary method
- Unbounded quantum-classical separation in sample complexity for sphere center finding
- Scaling in the dynamics of directed lackadaisical quantum walks
- A unified framework of quantum walk search
- Quantum algorithms for Hopcroft's problem
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- Quantum algorithms for matching problems
- The quantum query complexity of the determinant
This page was built for publication: Quantum verification of matrix products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581597)
