Is there a fast hidden shift algorithm for Heisenberg group over … ?
The question as posed is: “Is there a fast hidden shift algorithm for Heisenberg group over ?” It does not specify the hidden-shift promise, the oracle or input model, what the algorithm must recover, or what complexity measure “fast” means. Thus it does not define a precise algorithmic problem whose answer can be stated as a theorem. The nearby Heisenberg hidden subgroup problem is a distinct, more specifically formulated task. AimPL, Problem 4.3
Background
A precise neighboring problem is the hidden subgroup problem (HSP): given oracle access to a function on a finite group that is constant and distinct on left cosets of an unknown subgroup, determine that subgroup. The convention used for the Heisenberg HSP is the group of triples over , with multiplication
For odd primes , the subgroups central to the algorithm are , for . Their elements are
The inverse of in this formula is why this description and the cited construction are stated here only for odd . Bacon (2008), §6
Conjugation sends a generator to for suitable . Consequently, for fixed , the subgroups are conjugate as varies. The associated hidden subgroup conjugacy problem asks for the conjugacy class, and hence for , rather than for the individual parameter . This is an intermediate HSP task, not a definition of the hidden-shift question. Bacon (2008), §6
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.