1. Analysis of Absorbing Times of Quantum Walks
Tomohiro Yamasaki, Hirotada Kobayashi, Hiroshi Imai
http://arxiv.org/abs/quant-ph/0205045
Quantum walks are expected to provide useful algorithmic tools for quantum computation. This paper introduces absorbing probability and time of quantum walks and gives both numerical simulation results and theoretical analyses on Hadamard walks on the line and symmetric walks on the hypercube from the viewpoint of absorbing probability and time.
2. Quantum Computing and Dynamical Quantum Models
Scott Aaronson
http://arxiv.org/abs/quant-ph/0205059
A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^{1/3} steps (though not fewer).
3. Symmetry of distribution for the one-dimensional Hadamard walk
Norio Konno, Takao Namiki, Takahiro Soshi
Interdisciplinary Information Sciences, Vol.10, No.1, pp.11-22 (2004)
http://arxiv.org/abs/quant-ph/0205065
In this paper we study a one-dimensional quantum random walk with the Hadamard transformation which is often called the Hadamard walk. We construct the Hadamard walk using a transition matrix on probability amplitude and give some results on symmetry of probability distributions for the Hadamard walk.
4. Quantum Random Walks Hit Exponentially Faster
Julia Kempe
Probability Theory and Related Fields, Vol. 133(2), p. 215-235 (2005), conference version in Proc. 7th RANDOM, p. 354-69, 2003
http://arxiv.org/abs/quant-ph/0205083
We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing.
5. On the digraph of a unitary matrix
Simone Severini
SIAM Journal on Matrix Analysis and Applications, Volume 25, Number 1, pp. 295-300, July 2003
http://arxiv.org/abs/math/0205187
Given a matrix M of size n, a digraph D on n vertices is said to be the digraph of M, when M_{ij} is different from 0 if and only if (v_{i},v_{j}) is an arc of D. We give a necessary condition, called strong quadrangularity, for a digraph to be the digraph of a unitary matrix. With the use of such a condition, we show that a line digraph, LD, is the digraph of a unitary matrix if and only if D is Eulerian. It follows that, if D is strongly connected and LD is the digraph of a unitary matrix then LD is Hamiltonian. We conclude with some elementary observations. Among the motivations of this paper are coined quantum random walks, and, more generally, discrete quantum evolution on digraphs.