QIP2021 | The Hidden Subgroup Problem for Infinite Groups (Greg Kuperberg)

Speaker: Greg Kuperberg, Professor of Mathematics and Computer Science, UC Davis, USA

Abstract
We consider the hidden subgroup problem (HSP) for infinite groups, beyond the celebrated original cases established by Shor and Kitaev. We prove that HSP is NP-hard in the rational numbers ℚ under addition, as well as for normal subgroups of a non-abelian free group F_k. We can show that HSP in the lattice ℤ^k is uSVP-hard with unary encoding of vectors. On the other hand, HSP in ℤ^k with standard binary encoding of vectors can be solved in BQP, uniformly in the dimension, generalizing the Shor-Kitaev algorithm to infinite-index hidden subgroups. HSP in any fixed, finitely generated, virtually abelian subgroup can also be solved in subexponential time using established quantum algorithms for the abelian hidden shift problem.

Get entangled with us!