Hidden shift algorithms 2.0

QuICS Special Seminar

Greg Kuperberg (University of California, Davis)
Friday, March 29, 2019 - 11:00am
ATL 3100A
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".