Jeremy Cuson with Harsh Mathur

Primality Testing with Quantum Computers

To date there has been only one significant number theoretic algorithm developed for a hypothetical quantum computer, Shor’s algorithm, which allows one to factor large primes.  The task of this project would be to ascertain the usefulness of a quantum computer for other number theoretic algorithms in particular primality testing.  Classically, the computational complexity of a factoring algorithm is greater than that of a primality testing algorithm.  The project will explore whether this parallel exists in quantum computation.  Specifically, we would like to develop a feasible quantum algorithm for testing the primality of Mersenne numbers (2^n -1) for which there exists the classical Lucas-Lehmer test.  Given sufficient time, we would like to explore the quantum computation of combinatorial optimization particularly the traveling salesman problem.