Date of Award

Spring 2008

Document Type

Restricted Thesis

Terms of Use

© 2008 Stephan Hoyer. All rights reserved. Access to this work is restricted to users within the Swarthmore College network and may only be used for non-commercial, educational, and research purposes. Sharing with users outside of the Swarthmore College network is expressly prohibited. For all other uses, including reproduction and distribution, please contact the copyright holder.

Degree Name

Bachelor of Arts

Department

Physics & Astronomy Department

First Advisor

David A. Meyer

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.

Download

Share

COinS