1. Quantum Identification of Boolean Oracles
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita
http://arxiv.org/abs/quant-ph/0403056
The oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean oracles out of $2^{N}$ ones, to determine which oracle in $S$ is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to $S$. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper and lower bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it any} $S$ if $|S| = N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S| = N$) such as random oracles and balanced oracles, the query complexity is $\Theta(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.
2. Quantum walks on graphs and quantum scattering theory
Edgar Feldman, Mark Hillery
Coding Theory and Quantum Computing, edited by D. Evans, J. Holt, C. Jones, K. Klintworth, B. Parshall, O. Pfister, and H. Ward, Contemporary Mathematics, 381, 71 (2005).
http://arxiv.org/abs/quant-ph/0403066
We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.
3. Quantum Walks and Reversible Cellular Automata
Norio Konno, Kenichi Mitsuda, Takahiro Soshi, Hyun Jae Yoo
http://arxiv.org/abs/quant-ph/0403107
We investigate a connection between a property of the distribution and a conserved quantity for the reversible cellular automaton derived from a discrete-time quantum walk in one dimension. As a corollary, we give a detailed information of the quantum walk.
4. Quantum walks and their algorithmic applications
Andris Ambainis
International Journal of Quantum Information, 1:507-518, 2003.
http://arxiv.org/abs/quant-ph/0403120
Quantum walks are quantum counterparts of Markov chains. In this article, we give a brief overview of quantum walks, with emphasis on their algorithmic applications.
5. Quantum Algorithms and Covering Spaces
Tobias J. Osborne, Simone Severini
http://arxiv.org/abs/quant-ph/0403127
In this paper we isolate the combinatorial property responsible (at least in part) for the computational speedups recently observed in some quantum walk algorithms. We find that continuous-time quantum walks can exploit the covering space property of certain graphs. We demonstrate that a quantum walk on a graph Y which covers a smaller graph X can be equivalent to a quantum walk on the smaller graph X. This equivalence occurs only when the walk begins on certain initial states, fibre-constant states, which respect the graph covering space structure. We illustrate these observations with walks on Cayley graphs; we show that walks on fibre-constant initial states for Cayley graphs are equivalent to walks on the induced Schreier graph. We also consider the problem of constructing efficient gate sequences simulating the time evolution of a continuous-time quantum walk. For the case of the walk on the m-torus graph T^m on 2^n vertices we construct a gate sequence which uses O(\poly(n)) gates which is independent of the time t the walk is simulated for (and so the sequence can simulate the walk for exponential times). We argue that there exists a wide class of nontrivial operators based on quantum walks on graphs which can be measured efficiently. We introduce a new general class of computational problems, HiddenCover, which includes a variant of the general hidden subgroup problem as a subclass. We argue that quantum computers ought to be able to utilise covering space structures to efficiently solve HiddenCover problems.
6. Localization of Multi-State Quantum Walk in One Dimension
Norio Inui, Norio Konno
http://arxiv.org/abs/quant-ph/0403153
We show analytically that particle trapping appears in a quantum process called "quantum walk", in which the particle moves macroscopically correlating to the inner states. It has been well known that a particle in the ``Hadamard walk" with two inner states spreads away quickly on a line. In contrast, we find one-dimensional quantum walk with multi-state in which a particle stays at the starting point entirely with high positive probability. This striking difference is explained from difference between degeneration of eigenvalues of the time-evolution matrices.
7. Examples of nonuniform limiting distributions for the quantum walk on even cycles
Malgorzata Bednarska, Andrzej Grudka, Pawel Kurzynski, Tomasz Luczak, Antoni Wojcik
http://arxiv.org/abs/quant-ph/0403154
In the note we show how the choice of the initial states can influence the evolution of time-averaged probability distribution of the quantum walk on even cycles.
8. Decoherence in the quantum walk on the line
A. Romanelli, R. Siri, G. Abal, A. Auyuanet, R. Donangelo
Phys. A, vol 347C, pp. 137-152 (2005)
http://arxiv.org/abs/quant-ph/0403192
We investigate the quantum walk on the line when decoherences are introduced either through simultaneous measurements of the chirality and particle position, or as a result of broken links. Both mechanisms drive the system to a classical diffusive behavior. In the case of measurements, we show that the diffusion coefficient is proportional to the variance of the initially localized quantum random walker just before the first measurement. When links between neighboring sites are randomly broken with probability $p$ per unit time, the evolution becomes decoherent after a characteristic time that scales as $1/p$. The fact that the quadratic increase of the variance is eventually lost even for very small frequencies of disrupting events, suggests that the implementation of a quantum walk on a real physical system may be severely limited by thermal noise and lattice imperfections.
9. Quantum correlations from Brownian diffusion of chaotic level-spacings
S.N. Evangelou, D.E. Katsanos
http://arxiv.org/abs/quant-ph/0403206
Quantum chaos is linked to Brownian diffusion of the underlying quantum energy level-spacing sequences. The level-spacings viewed as functions of their order execute random walks which imply uncorrelated random increments of the level-spacings while the integrability to chaos transition becomes a change from Poisson to Gauss statistics for the level-spacing increments. This universal nature of quantum chaotic spectral correlations is numerically demonstrated for eigenvalues from random tight binding lattices and for zeros of the Riemann zeta function.
10. The Random Walk in Generalized Quantum Theory
Xavier Martin, Denjoe O’Connor, R.D. Sorkin
Phys.Rev. D71 (2005) 024029
http://arxiv.org/abs/gr-qc/0403085
One can view quantum mechanics as a generalization of classical probability theory that provides for pairwise interference among alternatives. Adopting this perspective, we ``quantize'' the classical random walk by finding, subject to a certain condition of ``strong positivity'', the most general Markovian, translationally invariant ``decoherence functional'' with nearest neighbor transitions.