Quantum random walk search on satisfiability problems
Date
2008
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Swarthmore College. Dept. of Physics & Astronomy
Type
Thesis (B.A.)
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
en_US
Note
Table of Contents
Terms of Use
Full copyright to this work is retained by the student author. It may only be used for non-commercial, research, and educational purposes. All other uses are restricted.
Rights Holder
Access Restrictions
Terms of Use
Tripod URL
Identifier
Abstract
Using numerical simulation, we measured the performance of several potential
quantum algorithms, based on quantum random walks, to solve Boolean
satisfiability (SAT) problems. We develop the fundamentals of quantum computing
and the theory of classical algorithms to indicate how these algorithms
could be implemented. We also discuss the development of quantum random
walks and the principles that go into creating them, presenting existing work
on search algorithms using coined discrete-time quantum random walks. Although
our quantum algorithms do not solve SAT problems faster than may be
done classically, as a step toward that objective, we present the first example
of a quantum walk on a directed graph that has a significant increase in speed
over the analogous classical walk.