Department of Mathematics

We show that if a closed, oriented 3-manifold M is secretly homeomorphic to a lens space L(n,k), then we can compute n and k in randomized polynomial time (in the size of the triangulation of M) with a discrete logarithm oracle. Using Shor's algorithm, a quantum computer can thus identify lens spaces in quantum polynomial time. In addition, k can be computed in functional NP. A given value of k can be certified in randomized polynomial time, specifically in coRP. The idea of the algorithm is to calculate Reidemeister torsion over a prime field that has nth roots of unity.