← All problems

How much noise is tolerated in hidden shift algorithms?

How much noise is tolerated in hidden shift algorithms? Consider too many solutions vs. too few. The question does not specify a noise model, a class of hidden-shift instances, or a particular algorithm, so it has no more precise general formulation here. AimPL: Quantum algorithms for analysis of public-key crypto

Background

One concrete setting for hidden shift uses Boolean functions f,g:Z2n→Z2f,g:\mathbb{Z}_2^n\to\mathbb{Z}_2 promised to satisfy g(x)=f(x+s)g(x)=f(x+s) for an unknown s∈Z2ns\in\mathbb{Z}_2^n; the task is to recover ss. More generally, hidden shift is closely connected to the dihedral hidden subgroup problem: for injective functions on ZN\mathbb{Z}_N, the usual hidden-shift problem is equivalent to that problem. These settings give context for robustness questions, but do not specify the noise model intended in the question. Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm Quantum algorithm for a generalized hidden shift problem

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.