1. Search via Quantum Walk
Fr��d��ric Magniez, Ashwin Nayak, J��r��mie Roland, Miklos Santha
SIAM Journal on Computing, 40(1):142-164, 2011
http://arxiv.org/abs/quant-ph/0608026
We propose a new method for designing quantum search algorithms for finding a "marked" element in the state space of a classical Markov chain. The algorithm is based on a quantum walk \'a la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
2. Universal Mixing of Quantum Walk on Graphs
W. Carlson, A. Ford, E. Harris, J. Rosen, C. Tamon, K. Wrobel
Quantum Information and Computation 7(8):738-751, 2007
http://arxiv.org/abs/quant-ph/0608044
We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph G is universal mixing if the instantaneous or average probability distribution of the quantum walk on G ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is uniform mixing if it visits the uniform distribution. Our results include the following: (a) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no unweighted complete multipartite graphs are uniform mixing (except for the four-cycle). (b) The weighted claw or star graph is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted claw is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. (c) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. (d) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.
3. The Learnability of Quantum States
Scott Aaronson
http://arxiv.org/abs/quant-ph/0608142
Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible implications for experimental physics, our learning theorem has two applications to quantum computing: first, a new simulation of quantum one-way communication protocols, and second, the use of trusted classical advice to verify untrusted quantum advice.
4. Improved quantum algorithms for the ordered search problem via semidefinite programming
Andrew M. Childs, Andrew J. Landahl, Pablo A. Parrilo
Phys. Rev. A 75, 032335 (2007)
http://arxiv.org/abs/quant-ph/0608161
One of the most basic computational problems is the task of finding a desired item in an ordered list of N items. While the best classical algorithm for this problem uses log_2 N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find new quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using 4 log_{605} N \approx 0.433 log_2 N queries, which improves upon the previously best known exact algorithm.