1. Quantum search algorithms
Andris Ambainis
SIGACT News, 35 (2):22-35, 2004.
http://arxiv.org/abs/quant-ph/0504012
We review some of quantum algorithms for search problems: Grover's search algorithm, its generalization to amplitude amplification, the applications of amplitude amplification to various problems and the recent quantum algorithms based on quantum walks.
2. Quantum Timing and Synchronization Problems
Diego de Falco, Dario Tamascelli
International Journal of Modern Physics B, vol. 18, Nos, 4-5 (2004) 623-631
http://arxiv.org/abs/quant-ph/0504024
Feynman's model of a quantum computer provides an example of a continuous-time quantum walk. Its clocking mechanism is an excitation of a basically linear chain of spins with occasional controlled jumps which allow for motion on a planar graph. The spreading of the wave packet poses limitations on the probability of ever completing the $s$ elementary steps of a computation: an additional amount of storage space $\delta$ is needed in order to achieve an assigned completion probability. In this note we study the END instruction, viewed as a measurement of the position of the clocking excitation: a $\pi$-pulse indefinitely freezes the contents of the input/output register, with a probability depending only on the ratio $\delta/s$.
3. Entanglement in coined quantum walks on regular graphs
Ivens Carneiro, Meng Loo, Xibai Xu, Mathieu Girerd, Viv Kendon, Peter L. Knight
New J. Phys. 7 (2005) 156
http://arxiv.org/abs/quant-ph/0504042
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC, pp 5968) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.
4. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
Dave Bacon, Andrew M. Childs, Wim van Dam
Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469-478
http://arxiv.org/abs/quant-ph/0504083
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
5. Statistical Properties of a Quantum Cellular Automaton
Norio Inui, Shuichi Inokuchi, Yoshihiro Mizoguchi, Norio Konno
http://arxiv.org/abs/quant-ph/0504104
We study a quantum cellular automaton (QCA) whose time-evolution is defined from global transition function of classical cellular automata (CA). In order to investigate natural transformations from CA to QCA, the present QCA includes CA with Wolfram's rule 150 and 105 as special cases. We firstly compute the time-evolution of the QCA and examine its statistical properties. As a basic statistical value, the probability of finding an active cell averaged over a spatial-temporal space is introduced, and the difference between CA and QCA is considered. In addition, it is shown that statistical properties in QCA are related to the classical trajectory in the configuration space.
6. Quantum walks on directed graphs
Ashley Montanaro
Quantum Information and Computation, vol. 7, no. 1 (2007)
http://arxiv.org/abs/quant-ph/0504116
We consider the definition of quantum walks on directed graphs. Call a directed graph reversible if, for each pair of vertices (i, j), if i is connected to j then there is a path from j to i. We show that reversibility is a necessary and sufficient condition for a directed graph to allow the notion of a discrete-time quantum walk, and discuss some implications of this condition. We present a method for defining a "partially quantum" walk on directed graphs that are not reversible.
7. Quantum random walk of the field in an externally driven cavity
G S Agarwal, P K Pathak
Phys. Rev. A 72, 033815 (2005).
http://arxiv.org/abs/quant-ph/0504135
Using resonant interaction between atoms and the field in a high quality cavity, we show how to realize quantum random walks as proposed by Aharonov et al [Phys. Rev. A {\bf48}, 1687 (1993)]. The atoms are driven strongly by a classical field. Under conditions of strong driving we could realize an effective interaction of the form $ iS^{x}(a-a^{\dag})$ in terms of the spin operator associated with the two level atom and the field operators. This effective interaction generates displacement in the field's wavefunction depending on the state of the two level atom. Measurements of the state of the two level atom would then generate effective state of the field. Using a homodyne technique, the state of the quantum random walker can be monitored.
8. From quantum graphs to quantum random walks
Gregor Tanner
http://arxiv.org/abs/quant-ph/0504224
We give a short overview over recent developments on quantum graphs and outline the connection between general quantum graphs and so-called quantum random walks.
9. Oracles Are Subtle But Not Malicious
Scott Aaronson
http://arxiv.org/abs/cs/0504048
Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low- degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the first nonrelativizing separation of "traditional" complexity classes, as opposed to interactive proof classes such as MIP and MA-EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size n^k for any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size n^k with quantum advice. To our knowledge, this is the first nontrivial lower bound on quantum circuit size. Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P=NP. Thus, classes such as ZPP^||NP inhabit a "twilight zone," where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem.