One of the newer and rapidly developing approaches in quantum computing is based
on "quantum walks," which are quantum processes on discrete space that evolve in either
discrete or continuous time and are characterized by mixing of components at each step.
The idea emerged in analogy with the classical random walks and stochastic techniques,
but these unitary processes are very different even as they have intriguing similarities.
This thesis is concerned with study of discrete-time quantum walks.
The original motivation from classical Markov chains required for discrete-time quantum
walks that one adds an auxiliary Hilbert space, unrelated to the one in which the
system evolves, in order to be able to mix components in that space and then take the
evolution steps accordingly (based on the state in that space). This additional, "coin,"
space is very often an internal degree of freedom like spin.
We have introduced a general framework for construction of discrete-time quantum
walks in a close analogy with the classical random walks with memory that is rather
different from the standard "coin" approach. In this method there is no need to bring in
a different degree of freedom, while the full state of the system is still described in the
direct product of spaces (of states). The state can be thought of as an arrow pointing
from the previous to the current site in the evolution, representing the one-step memory.
The next step is then controlled by a single local operator assigned to each site in the
space, acting quite like a scattering operator.
This allows us to probe and solve some problems of interest that have not had successful
approaches with "coined" walks. We construct and solve a walk on the binary
tree, a structure of great interest but until our result without an explicit discrete time
quantum walk, due to difficulties in managing coin spaces necessary in the standard approach.
Beyond algorithmic interests, the model based on memory allows one to explore
effects of history on the quantum evolution and the subtle emergence of classical features
as "memory" is explicitly kept for additional steps. We construct and solve a walk with
an additional correlation step, finding interesting new features.
On the other hand, the fact that the evolution is driven entirely by a local operator,
not involving additional spaces, enables us to choose the Fourier transform as an operator
completely controlling the evolution. This in turn allows us to combine the quantum walk
approach with Fourier transform based techniques, something decidedly not possible in
classical computational physics. We are developing a formalism for building networks
manageable by walks constructed with this framework, based on the surprising efficiency
of our framework in discovering internals of a simple network that we so far solved.
Finally, in line with our expectation that the field of quantum walks can take cues
from the rich history of development of the classical stochastic techniques, we establish
starting points for the work on non-Abelian quantum walks, with a particular quantum walk
analog of the classical "card shuffling," the walk on the permutation group.
In summary, this thesis presents a new framework for construction of discrete time
quantum walks, employing and exploring memoried nature of unitary evolution. It is
applied to fully solving the problems of: A walk on the binary tree and exploration of the
quantum-to-classical transition with increased correlation length (history). It is then
used for simple network discovery, and to lay the groundwork for analysis of complex
networks, based on combined power of efficient exploration of the Hilbert space (as a
walk mixing components) and Fourier transformation (since we can choose this for the
evolution operator). We hope to establish this as a general technique as its power would
be unmatched by any approaches available in the classical computing. We also looked
at the promising and challenging prospect of walks on non-Abelian structures by setting
up the problem of "quantum card shuffling," a quantum walk on the permutation group.
Relation to other work is thoroughly discussed throughout, along with examination
of the context of our work and overviews of our current and future work. / Graduation date: 2012
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/30037 |
| Date | 14 June 2012 |
| Creators | Dimcovic, Zlatko |
| Contributors | Kovchegov, Yevgeniy |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0022 seconds