Abstract:
In recent years quantum random walks have garnered much interest among quantum information researchers. Part of the reason is the prospect
that many hard problems can be solved efficiently by employing algorithms
based on quantum random walks, in the same way that classical random walks
have played a central role in many hugely successful randomized algorithms. In
this paper we introduce a new representation for the quantum random walks
via the classical random walk with internal states. This new representation
allows for a systematic approach to finding closed form expressions for the
n-step distributions for a variety of quantum random walk models, and lends
itself naturally to large deviation analysis. As an example, we show how to use
the new representation to arrive at the same closed form expression for the
Hadamard quantum random walk on a line, previously obtained by others. We
assert the proposed method works in the most general settings.
