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 , known endomorphisms indexed by a finite set containing , and injective functions satisfying
where the unknown is the shift . In the cyclic case this becomes for known coefficients . Recovering 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
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.