← All problems

Hidden Shift (problem 6)

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? AimPL: Quantum algorithms for analysis of public-key crypto

Background

Kuperberg’s multiple-shift formulation considers a finite abelian group AA, known endomorphisms ϕj:A→A\phi_j:A\to A indexed by a finite set JJ containing 00, and injective functions fj:A→Xf_j:A\to X satisfying

fj(a)=f0(a+ϕj(s)),ϕ0=0,f_j(a)=f_0(a+\phi_j(s)),\qquad \phi_0=0,

where the unknown is the shift s∈As\in A. In the cyclic case this becomes fj(a)=f0(a+rjs)f_j(a)=f_0(a+r_js) for known coefficients rjr_j. Recovering ss requires a nondegeneracy condition on the maps; Kuperberg notes that the multiple-shift discussion is heuristic and does not fully specify this condition when there are more than two shifts. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

The algorithm’s central mechanism is a collimation sieve: weak Fourier measurements produce states whose phases encode the hidden shift, and partial measurements combine them into states with more aligned phases. Kuperberg’s later algorithm makes some use of multiple shifts, though he reports that the acceleration is not dramatic. This is distinct from the general hidden multiple shift (HMS) problem studied by Ivanyos, Prakash, and Santha, which relates shifts to learning linear functions from a subset. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem On learning linear functions from subset and its applications in quantum computing

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.