1. Quantum search by measurement
Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Andrew J. Landahl
Phys. Rev. A 66, 032314 (2002)
http://arxiv.org/abs/quant-ph/0204013
We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms.
2. A New Protocol and Lower Bounds for Quantum Coin Flipping
Andris Ambainis
Journal of Computer and System Sciences, 68(2): 398-416, 2004.
http://arxiv.org/abs/quant-ph/0204022
We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most $\epsilon$, it must use at least $\Omega(\log \log \frac{1}{\epsilon})$ rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel.)
3. Lower bound for a class of weak quantum coin flipping protocols
Andris Ambainis
http://arxiv.org/abs/quant-ph/0204063
We study the class of protocols for weak quantum coin flipping introduced by Spekkens and Rudolph (quant-ph/0202118). We show that, for any protocol in this class, one party can win the coin flip with probability at least $1/\sqrt{2}$.
4. Random Walk and Diffusion on a Smash Line Algebra
Demosthenes Ellinas, Ioannis Tsohantjis
http://arxiv.org/abs/quant-ph/0204148
Working withing the framework of Hopf algebras, a random walk and the associated diffusion equation are constructed on a space that is algebraically described as the merging of the real line algebra with the anyonic line algebra. Technically this merged structure is a smash algebra, namely an algebra resulting by a braided tensoring of real with anyonic line algebras. The motivation of introducing the smashing results from the necessity of having non commuting increments in the random walk. Based on the observable-state duality provided by the underlying Hopf structure, the construction is cast into two dual forms: one using functionals determined by density probability functions and the other using the associated Markov transition operator. The ensuing diffusion equation is shown to possess triangular matrix realization. The study is completed by the incorporation of Hamiltonian dynamics in the above random walk model, and by the construction of the dynamical equation obeyed by statistical moments of the problem for generic entangled density functions.