Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1103.3017 · Lecture notes in computer science

Quantum Algorithm for the Boolean Hidden Shift Problem

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

Published Jan 1, 2011• 14 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-22685-4_14

Related papers

Easy and Hard Functions for the Boolean Hidden Shift Problem

Andrew M. Childs, Robin Kothari, Māris Ozols +1 more

We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.

arXiv:1304.4642•Leibniz international proceedings in informatics•Jan 1, 2013•11 citations

Quantum algorithms

Daowen Qiu

Elsevier eBooks•Aug 29, 2025•0 citations

Quantum algorithms for highly non-linear Boolean functions

Martin Rötteler

Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1

•Jan 1, 2008•24 citations

Quantum Algorithms

The MIT Press eBooks•Mar 19, 2019•0 citations

Quantum Algorithms

Madhusudan Singh Irish Singh, Bharat S. Rawal

Springer eBooks•Jan 1, 2026•0 citations

Quantum algorithms for highly non-linear Boolean functions

Martin Rötteler

Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal is to find exponential separations for computational problems. However, such separations do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalize Shor's factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present new quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms.

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Jan 17, 2010•24 citations
We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.
Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1
Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal is to find exponential separations for computational problems. However, such separations do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalize Shor's factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present new quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms.