Quantum Algorithms

Welcome to Matthew Hayward's quantum algorithms page. These 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.

• 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 introductory 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, tar of simulator code, GitHub Respository
• Lower Query Bounds in the Quantum Oracle Model My Masters Thesis in Computer Science at the University of Illinois with Professor Jeff Erickson. This paper applies a result of Andris Ambainis to produce lower bounds in the Quantum Oracle Model in a bounded error setting for several functions and classes of functions. Available online in: HTML, PostScript, PDF, GitHub Respository
• 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 complete 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, GitHub Respository
• 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, tar of simulator code, GitHub Respository