Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frederic Magniez
We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).
View original:
http://arxiv.org/abs/1302.7316
No comments:
Post a Comment