Quantum Algorithm for Checking Matrix Identities
- PDF / 213,161 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 12 Downloads / 197 Views
Q
Quantum Algorithm for Checking Matrix Identities
query complexity (n2 ). Buhrman and Spalek [5] gave an O(n5/3 ) quantum query algorithm using [18].
What is the “most natural” definition? And, when is there a quantum speedup over the classical mixing time?
Group Commutativity Testing
Cross References
Suppose one is presented with a black-box group specified by its k generators and is required to determine if the group commutes using as few queries as possible to the group product operation (i. e., queries of the form “What is the product of elements g and h?”). The classical query complexity is (k) group operations. Magniez and ˜ 2/3 ) quantum Nayak [11] gave an (essentially optimal) O(k query algorithm by walking on the product of two graphs whose vertices are (ordered) l-tuples of distinct generators and whose transition probabilities are nonzero only where the l-tuples at two endpoints differ in at most one coordinate. Open Problems Many issues regarding quantization of Markov chains remain unresolved, both for the hitting problem and the closely related mixing problem. Hitting Can the quadratic quantum hitting time speedup be extended from all symmetric Markov chains to all reversible ones? Can the lower bound of [18] on observation probability be extended beyond the class of state-transitive Markov chains with a unique marked state? What other algorithmic applications of quantum hitting time can be found? Mixing Another wide use of Markov chains in classical algorithms is in mixing. In particular, Markov chain Monte Carlo algorithms work by running an ergodic Markov chain with carefully chosen stationary distribution until reaching its mixing time, at which point the current state is guaranteed to be distributed "-close to uniform. Such algorithms form the basis of most randomized algorithms for approximating #P-complete problems. Hence, the problem is: INPUT: Markov chain P on set S, tolerance ">0. OUTPUT: A state "-close to in total variation distance. Notions of quantum mixing time were first proposed and analyzed on the line, the cycle, and the hypercube by Nayak et al. [3,15], Aharonov et al. [1], and Moore and Russell [14]. Recent work of Kendon and Tregenna [10] and Richter [16] has investigated the use of decoherence in improving mixing of quantum walks. Two fundamental questions about the quantum mixing time remain open:
Quantum Algorithm for Element Distinctness Quantum Algorithm for Finding Triangles Recommended Reading 1. Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. STOC (2001) 2. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007). Preliminary version in Proc. FOCS 2004 3. Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proc. STOC (2001) 4. Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. SODA (2005) 5. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proc. SODA (2006) 6. Childs, A., Cleve, R., De
Data Loading...
