Quantum Algorithms

Welcome to Matthew Hayward's quantum algorithms page. The purpose of this page is simply to present the work I have done and am currently doing in the area of quantum algorithms. In many cases my papers are designed to be accessible to anyone with a technical or engineering background. Hopefully they will serve as a primer or tutorial for those interested in quantum computing, Shor's algorithm, Grover's algorithm, and other quantum algorithms.

I am always glad to hear comments on my work, from the technical to the grammatical, all suggestions are welcome.

• Lower Query Bounds in the Quantum Oracle Model: Masters Thesis in Computer Science at the University of Illinois with Professor Jeff Erickson. I hope to illustrate and improve on upper and lower bounds for various fundamental algorithms on a quantum computer. Available online in: HTML, PostScript, PDF
• Quantum Computing and Shor's Algorithm this was my first foray into the world of quantum computing, a senior thesis done at the University of Illinois with Professor Roy Campbell. It contains a good deal of information on quantum computing in general, both theory and motivation, as well as a discussion of Shor's algorithm. Originally written in Spring 1999, it has since been updated. It is available online in: HTML, PostScript, PDF, LaTeX. There is also a tar of the simulator code.
• Quantum Computing, Shor's Algorithm, and Parallelism A semester project completed for CS 433, Parallel Architecture at the University of Illinois. This is basically a revision of the work done above, with an emphasis on simulating quantum parallelism with a classical parallel computer, essentially linear speedup is attained using POSIX threads on an SGI Origin 2000. Available online in: HTML, PostScript, PDF, LaTeX, tar of figures for the LaTeX document, tar of simulator code.
• Quantum Computing and Grover's Algorithm A paper written for Professor Jeff Erickson at the University of Illinois, a semester project in CS 473, Topics on the Analysis of Algorithms. Intended to be a slightly mathematical introduction to Grover's algorithm, an explanation of the algorithm and a summary of various proofs relating to its correctness. Available online in: HTML, PostScript, PDF, LaTeX, tar of figures for the LaTeX source.