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.07231

Extending Forrelation: Quantum Algorithms Related to Generalized Fourier-Correlation

Dutta, Suman, Subhamoy Maitra, Pantelimon Stănică

Published Jul 9, 2025• 0 citations
arXivHTMLPDF

Abstract

In this paper, we study different cryptographically significant spectra of Boolean functions, including the Walsh-Hadamard, cross-correlation, and autocorrelation. The $2^k$-variation by Stanica [IEEE-IT 2016] is considered here with the formulation for any $m \in \mathbb{N}$. Given this, we present the most generalized version of the Deutsch-Jozsa algorithm, which extends the standard and previously extended versions, thereby encompassing them as special cases. Additionally, we generalize the Forrelation formulation by introducing the $m$-Forrelation and propose various quantum algorithms towards its estimation. In this regard, we explore different strategies in sampling these newly defined spectra using the proposed $m$-Forrelation algorithms and present a comparison of their corresponding success probabilities. Finally, we address the problem related to affine transformations of generalized bent functions and discuss quantum algorithms in identifying the shifts between two bent (or negabent) functions with certain modifications, and compare these with existing results.

DOI
10.48550/arxiv.2507.07231

Related papers

Efficient Quantum Algorithms related to Autocorrelation Spectrum

Debajyoti Bera, Subhamoy Maitra, Tharrmashastha Sapv

In this paper, we propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First, we present a quantum algorithm that samples from the Walsh spectrum of any derivative of $f()$. Informally, the autocorrelation coefficient of a Boolean function $f()$ at some point $a$ measures the average correlation among the values $f(x)$ and $f(x \oplus a)$. The derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of $f()$. The Walsh spectrum is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem. We extend the idea to "Higher-order Deutsch-Jozsa" quantum algorithm to obtain points corresponding to large absolute values in the Walsh spectrum of a certain derivative of $f()$. Further, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Finally we provide a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares.

arXiv:1808.04448•Aug 10, 2018•2 citations

Forrelation Is Extremally Hard

Uma Girish, Rocco A. Servedio

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tildeΩ\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.

arXiv:2508.02514•Leibniz international proceedings in informatics•Aug 4, 2025•5 citations

THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS

Subhamoy Maitra, PARTHA MUKHOPADHYAY

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.

arXiv:quant-ph/0410042•International Journal of Quantum Information•May 31, 2005•13 citations

Classical algorithms for Forrelation

Sergey B. Bravyi, David Gosset, Daniel Grier +1 more

We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime $O(n2^{n/2})$. This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes $t$ queries to an $n$-bit oracle can be simulated by classical query algorithm making only $O(2^{n(1-1/2t)})$ queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to $poly(n,t))$ factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where $n$ binary variables live at vertices of some fixed graph and the functions $f,g$ are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time $O(n)$ for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and $225$ qubits on a laptop computer.

arXiv:2102.06963•Feb 13, 2021•22 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•28 citations

On the Connection Between Deutsch-Jozsa Algorithm and Bent Functions

Eraldo Pereira Marinho

Abstract It is presently shown that the Deutsch-Jozsa algorithm is connected to the concept of bent function. Particularly, it is noticeable that the quantum circuit used to denote the well-known quantum algorithm is by itself the quantum computer that performs the Walsh transform of a Boolean function. Consequently, the output from the Deutsch-Jozsa algorithm when the hidden function is bent corresponds to a flat spectrum of quantum states.

arXiv:1912.01549•Journal of Physics Conference Series•Jan 1, 2021•0 citations
In this paper, we study different cryptographically significant spectra of Boolean functions, including the Walsh-Hadamard, cross-correlation, and autocorrelation. The 2k2^k2k-variation by Stanica [IEEE-IT 2016] is considered here with the formulation for any m∈Nm \in \mathbb{N}m∈N. Given this, we present the most generalized version of the Deutsch-Jozsa algorithm, which extends the standard and previously extended versions, thereby encompassing them as special cases. Additionally, we generalize the Forrelation formulation by introducing the mmm-Forrelation and propose various quantum algorithms towards its estimation. In this regard, we explore different strategies in sampling these newly defined spectra using the proposed mmm-Forrelation algorithms and present a comparison of their corresponding success probabilities. Finally, we address the problem related to affine transformations of generalized bent functions and discuss quantum algorithms in identifying the shifts between two bent (or negabent) functions with certain modifications, and compare these with existing results.
In this paper, we propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First, we present a quantum algorithm that samples from the Walsh spectrum of any derivative of f()f()f(). Informally, the autocorrelation coefficient of a Boolean function f()f()f() at some point aaa measures the average correlation among the values f(x)f(x)f(x) and f(x⊕a)f(x \oplus a)f(x⊕a). The derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of f()f()f(). The Walsh spectrum is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem. We extend the idea to "Higher-order Deutsch-Jozsa" quantum algorithm to obtain points corresponding to large absolute values in the Walsh spectrum of a certain derivative of f()f()f(). Further, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Finally we provide a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares.
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to nnn-bit Boolean functions fff and ggg, the goal is to estimate the Forrelation function forr(f,g)\mathrm{forr}(f,g)forr(f,g), which measures the correlation between ggg and the Fourier transform of fff. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely (f,g)(f,g)(f,g) with forr(f,g)=1\mathrm{forr}(f,g)=1forr(f,g)=1 and forr(f,g)=−1\mathrm{forr}(f,g)=-1forr(f,g)=−1. We show that this problem can be solved with one quantum query and success probability one, yet requires Ω~(2n/4)\tildeΩ\left(2^{n/4}\right)Ω~(2n/4) classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs f,gf,gf,g are computable by small classical circuits and show classical hardness under cryptographic assumptions.
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.
We study the forrelation problem: given a pair of nnn-bit Boolean functions fff and ggg, estimate the correlation between fff and the Fourier transform of ggg. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime O(n2n/2)O(n2^{n/2})O(n2n/2). This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes ttt queries to an nnn-bit oracle can be simulated by classical query algorithm making only O(2n(1−1/2t))O(2^{n(1-1/2t)})O(2n(1−1/2t)) queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to poly(n,t))poly(n,t))poly(n,t)) factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where nnn binary variables live at vertices of some fixed graph and the functions f,gf,gf,g are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time O(n)O(n)O(n) for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and 225225225 qubits on a laptop computer.
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.