4. Hidden Shift

Problem 4.2.
How much noise is tolerated in hidden shift algorithms? Consider too many solutions vs. too few. 
Problem 4.3.
[Greg Kuperberg] Is there a fast hidden shift algorithm for Heisenberg group over $\mathbb F_p$?
Remark. HSP is known.


Problem 4.4.
[Tanja Lange] What is the cost of hidden shift on $\mathbb Z$ where the shift $s\in [a,b]$, under binary cost of oracle? 
Problem 4.5.
[Greg Kuperberg] Hidden shift on $\mathbb Z^d$ where $f_0$ and $f_1$ are periodic under unary oracle cost. 
Problem 4.6.
[Elena Kirshanova] How does Kuperbergâ€™s algorithm behave under multiple hidden shifts (with known relations between shifts, e.g. arithmetic progression) with Gaussians, using the work of Ivanyos, Prakash, and Santha?,
Cite this as: AimPL: Quantum algorithms for analysis of publickey crypto, available at http://aimpl.org/quantumalg.