To date there has been only one significant number theoretic algorithm developed for a hypothetical quantum computer, Shor\u2019s algorithm, which allows one to factor large primes.\u00a0 The task of this project would be to ascertain the usefulness of a quantum computer for other number theoretic algorithms in particular primality testing.\u00a0 Classically, the computational complexity of a factoring algorithm is greater than that of a primality testing algorithm.\u00a0 The project will explore whether this parallel exists in quantum computation.\u00a0 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.\u00a0 Given sufficient time, we would like to explore the quantum computation of combinatorial optimization particularly the traveling salesman problem.<\/p>\n","protected":false},"excerpt":{"rendered":"
Jeremy Cuson with Harsh MathurPrimality Testing with Quantum Computers<\/p>\n
To date there has been only one significant number theoretic algorithm developed for a hypothetical quantum computer, Shor\u2019s algorithm, which allows one to factor large primes.\u00a0 The task of this project would be to ascertain the usefulness of a quantum computer for other number theoretic algorithms in particular primality testing.\u00a0 Classically, the computational complexity of a factoring algorithm is greater than that of a primality testing algorithm.\u00a0 The project will explore whether this parallel exists in quantum computation.\u00a0 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.\u00a0<\/p>\n