Hidden shift algorithms 2.0

Greg Kuperberg - University of California, Davis

Abstract

The dihedral hidden subgroup problem is equivalent to the

hidden shift problem for a cyclic group, while the hidden shift

problem for an arbitrary abelian group is generally similar. In

2003, I found a subexponential time algorithm for this problem, more

precisely stretched exponential time. Later there were two

variations, one due to Regev and the other due to me. These

algorithms became more interesting when Childs, Jao, and Soukharev

showed that they yield a quantum algorithm to find isogenies between

elliptic curves. I will discuss my lesser known second algorithm,

which deserves more attention because it supersedes my original

algorithm as well as Regev's algorithm. The newer algorithm has a

better constant in the exponent, it is expensive only in classical

space and not quantum space, and it is tunable in various ways. The

algorithm also breaks out of the representation theory of finite

groups and instead uses a novel quantum data structure that can be

called a "phase vector".

hidden shift problem for a cyclic group, while the hidden shift

problem for an arbitrary abelian group is generally similar. In

2003, I found a subexponential time algorithm for this problem, more

precisely stretched exponential time. Later there were two

variations, one due to Regev and the other due to me. These

algorithms became more interesting when Childs, Jao, and Soukharev

showed that they yield a quantum algorithm to find isogenies between

elliptic curves. I will discuss my lesser known second algorithm,

which deserves more attention because it supersedes my original

algorithm as well as Regev's algorithm. The newer algorithm has a

better constant in the exponent, it is expensive only in classical

space and not quantum space, and it is tunable in various ways. The

algorithm also breaks out of the representation theory of finite

groups and instead uses a novel quantum data structure that can be

called a "phase vector".

This talk is organized by Andrea F. Svejda