Ten years have passed since Peter Shor's discovery of a polynomial time
quantum algorithm for factoring. Since then, almost all problems for
which we can obtain an exponential quantum speedup have involved
variants of Shor's algorithm.

One of the key ingredients of Shor's algorithm is the quantum Fourier
transform. We consider two problems that have a close connection to the
Fourier transform: the hidden shift problem and the nonabelian hidden
subgroup problem.

We give a quantum algorithm for the hidden shift problem that uses the
Fourier transform in a fundamentally different way to Shor's algorithm.

Finding an algorithm for the nonabelian hidden subgroup problem is the
most important open problem in quantum algorithms. We propose a new
approach to finding an algorithm that uses ideas from hypothesis testing
and semidefinite programming.

We'll also show an unexpected connection between quantum computing and
the Hubble Space Telescope.

No quantum background will be assumed.