← All problems

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 Fp\mathbb F_p?” 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 HpH_p of triples over Fp\mathbb F_p, with multiplication

(x,y,z)(x′,y′,z′)=(x+x′, y+y′+xz′, z+z′).(x,y,z)(x',y',z')=(x+x',\,y+y'+xz',\,z+z').

For odd primes pp, the subgroups central to the algorithm are Ai,j=⟨(1,j,i)⟩A_{i,j}=\langle(1,j,i)\rangle, for i,j∈Fpi,j\in\mathbb F_p. Their elements are

Ai,j={(l,12l(l−1)i+lj,li):l∈Fp}.A_{i,j}=\{(l,\tfrac12 l(l-1)i+lj,li):l\in\mathbb F_p\}.

The inverse of 22 in this formula is why this description and the cited construction are stated here only for odd pp. Bacon (2008), §6

Conjugation sends a generator (1,j,i)(1,j,i) to (1,j+xi−z,i)(1,j+xi-z,i) for suitable x,z∈Fpx,z\in\mathbb F_p. Consequently, for fixed ii, the subgroups Ai,jA_{i,j} are conjugate as jj varies. The associated hidden subgroup conjugacy problem asks for the conjugacy class, and hence for ii, rather than for the individual parameter jj. This is an intermediate HSP task, not a definition of the hidden-shift question. Bacon (2008), §6

References

Progress summary

Never refreshed

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.