Quantum Algorithm for the Boolean Hidden Shift Problem

DOI10.1007/978-3-642-22685-4_14MaRDI QIDQ3087947zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky, Martin Roetteler, Jérémie Roland

Publication date 17 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.3017

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: 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.

Recommendations

• Quantum algorithm for a generalized hidden shift problem
• scientific article; zbMATH DE number 2079375
• Quantum Algorithms for Some Hidden Shift Problems
• A hidden shift quantum algorithm
• Quantum algorithms for shifted subset problems
• Quantum algorithms related to \(HN\)-transforms of Boolean functions
• scientific article; zbMATH DE number 6297720
• Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems
• Quantum algorithms for testing Boolean functions
• Quantum algorithms for testing and learning Boolean functions

Cited in

(6)

• Quantum algorithms for typical hard problems: a perspective of cryptanalysis
• Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum algorithms for shifted subset problems
• Quantum pattern matching fast on average

This page was built for publication: Quantum Algorithm for the Boolean Hidden Shift Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087947)