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:2507.19440

Hidden shift problem for complex functions

Serge Adonsou, Peter Bruin, Māris Ozols, Joppe Stokvis

Published Jul 25, 2025• 1 citation
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2507.19440

Related papers

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•28 citations

Quantum algorithms for highly non-linear Boolean functions

Martin Roetteler

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.

arXiv:0811.3208•Nov 19, 2008•13 citations

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

The non-injective hidden shift problem

Mirmojtaba Gharibi

In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.

•Jan 19, 2012•2 citations

Quantum algorithms and the fourier transform

Lawrence Ip, Umesh V. Vazirani

The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.

•Jan 1, 2004•0 citations

The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem

Lisa Hales

The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.

arXiv:quant-ph/0212002•Nov 30, 2002•28 citations
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.
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.
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.
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.
In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.