Hidden shift problem for complex functions

arXiv (Cornell University)

Abstract

We study quantum algorithms for the hidden shift problem of complex scalar- and vector-valued functions on finite abelian groups. Given oracle access to a shifted function and the Fourier transform of the unshifted function, the goal is to find the hidden shift. We analyze the success probability of our algorithms when using a constant number of queries. For bent functions, they succeed with probability 1, while for arbitrary functions the success probability depends on the `bentness' of the function.

Authors 4

1. Serge Adonsou

   University of Guelph

   Affiliation as printed

   Department of Mathematics and Statistics , University of Guelph , Canada

2. Peter Bruin Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute , Leiden University , Netherlands

3. Māris Ozols

   QuSoft · University of Amsterdam

   Affiliation as printed

   Institute for Logic, Language and Computation , and Korteweg-de Vries Institute for Mathematics , University of Amsterdam , Netherlands

   QuSoft , Amsterdam , Netherlands

4. Joppe Stokvis Aachen Mathematical Institute

   Leiden University · QuSoft

   Affiliation as printed

   Mathematical Institute , Leiden University , Netherlands

   QuSoft , Amsterdam , Netherlands