The Hidden Subgroup Problem for Infinite Groups

Greg Kuperberg (UC Davis) https://simons.berkeley.edu/talks/resolution-brown-susskind-conjecture Quantum and Lattices Joint Reunion Workshop The hidden subgroup problem (HSP) is one of the main frameworks for quantum algorithms for algebraic problems, in particular for problems with a rigorous exponential quantum advantage, at least relative to an oracle or with cryptographic assumptions. The input to HSP is a function f on a group G which is periodic with respect to a subgroup H, and otherwise injective; the problem is to compute H. Although HSP was motivated by Shor's algorithm, which solves the problem when G is the integers, much of the research since then has been in the case when G is a finite group instead. I will talk about HSP for discrete infinite groups for cases other than Shor's algorithm and the Shor-Kitaev algorithm. In particular, the hidden subgroup problem is NP-hard for the group of rationals, so that a superpolynomial quantum advantage is implausible. I will also discuss a polynomial-time quantum algorithm for HSP when G is a multidimensional lattice ℤ^d and the hidden subgroup H has any rank. This algorithm extends the celebrated Shor-Kitaev algorithm, which assumes that H has maximal rank.