Physics – Quantum Physics
Scientific paper
2011-03-15
17th International Computing & Combinatorics Conference (COCOON'11), Lecture Notes in Computer Science 6842 (Springer, 2011),
Physics
Quantum Physics
10 pages, 1 figure
Scientific paper
10.1007/978-3-642-22685-4_14
The hidden shift problem is a natural place to look for new separations between classical and quantum models of computation. One advantage of this problem is its flexibility, since it can be defined for a whole range of functions and a whole range of underlying groups. In a way, this distinguishes it from the hidden subgroup problem where more stringent requirements about the existence of a periodic subgroup have to be made. And yet, the hidden shift problem proves to be rich enough to capture interesting features of problems of algebraic, geometric, and combinatorial flavor. We present a quantum algorithm to identify the hidden shift for any Boolean function. Using Fourier analysis for Boolean functions we relate the time and query complexity of the algorithm to an intrinsic property of the function, namely its minimum influence. We show that for randomly chosen functions the time complexity of the algorithm is polynomial. Based on this we show an average case exponential separation between classical and quantum time complexity. A perhaps interesting aspect of this work is that, while the extremal case of the Boolean hidden shift problem over so-called bent functions can be reduced to a hidden subgroup problem over an abelian group, the more general case studied here does not seem to allow such a reduction.
Gavinsky Dmitry
Roetteler Martin
Roland Jérémie
No associations
LandOfFree
Quantum algorithm for the Boolean hidden shift problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum algorithm for the Boolean hidden shift problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum algorithm for the Boolean hidden shift problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-261519