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

Efficient Quantum Algorithms related to Autocorrelation Spectrum

Debajyoti Bera, Subhamoy Maitra, Tharrmashastha Sapv

Published Aug 10, 2018• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1808.04448

Related papers

Extending Forrelation: Quantum Algorithms Related to Generalized Fourier-Correlation

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

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.

arXiv:2507.07231•Jul 9, 2025•0 citations

Quantum filtering of Boolean functions

János A. Bergou, Ulrike Herzog, Mark S. Hillery

We develop an efficient probabilistic quantum algorithm that can distinguish between sets of Boolean functions. The method is based on an exact solution to the quantum state filtering problem and can be considered to be an extension of the original Deutsch-Jozsa algorithm.

•Aug 31, 2002•0 citations

Walsh transforms and efficient quantum algorithms

Takashi Mihara

In this paper, we show structures of efficient quantum algorithms on a quantum Turing machine. First, we denote a relationship between Simon's algorithm and Walsh transforms. Next, we also show that a quantum Turing machine can efficiently solve the Deutsch–Jozsa problem by using interference among configurations instead of observation. Moreover, based on these results, we are led to structures of more general quantum algorithms. Finally, we show a problem that can be efficiently solved by using this type of algorithm and a Walsh transform. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 71–80, 2000

Electronics and Communications in Japan (Part III Fundamental Electronic Science)•Aug 1, 2000•1 citation

Quantum and Randomised Algorithms for Non-linearity Estimation

Debajyoti Bera, Tharrmashastha Sapv

Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Θ (2 n ) queries to an n -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted λ, with query complexities that depend polynomially on λ. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.

arXiv:2103.07934•ACM Transactions on Quantum Computing•Jun 30, 2021•4 citations

Quantum-state filtering applied to the discrimination of Boolean functions

János A. Bergou, Mark S. Hillery

Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the $N$ given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of $N$ nonorthogonal states, ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$, for distinguishing $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.

arXiv:quant-ph/0507092•Physical Review A•Jul 5, 2005•9 citations

Simulation of quantum algorithms using classical probabilistic bits and circuits

Deniz D. Yavuz, Anirudh Yadav

We discuss a new approach to simulate quantum algorithms using classical probabilistic bits and circuits. Each qubit (a two-level quantum system) is initially mapped to a vector in an eight dimensional probability space (equivalently, to a classical random variable with eight probabilistic outcomes). The key idea in this mapping is to store both the amplitude and phase information of the complex coefficients that describe the qubit state in the probabilities. Due to the identical tensor product structure of combining multiple quantum systems as well as multiple probability spaces, $n$ qubits are then mapped to a tensor product of $n$ 8-dimensional probabilistic vectors (i.e., the Hilbert space of dimension $2^n$ is mapped to a probability space of dimension $8^n$). After this initial mapping, we show how to implement the analogs of single-qubit and two-qubit gates in the probability space using correlation-inducing operations on these classical random variables. The key defining feature of both the mapping to the probability space and the transformations in this space (i.e., operations on the random variables) is that they are not linear, but instead affine. Using this architecture, the evolution of the $2^n$ complex coefficients of the quantum system can be tracked in the joint fully-correlated probabilities of the polynomial number of random variables. We then give specific procedures for implementing (1) the Deutsch-Jozsa algorithm, and (2) the Quantum Fourier Transform in the probability space. Identical to the Quantum case, simulating the Quantum Fourier Transform in the probability space requires $O(n)$ probabilistic bits and $O(n^2)$ (i.e., quadratic in the number of quantum bits) operations.

arXiv:2307.14452•Jul 26, 2023•1 citation
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.
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 show structures of efficient quantum algorithms on a quantum Turing machine. First, we denote a relationship between Simon's algorithm and Walsh transforms. Next, we also show that a quantum Turing machine can efficiently solve the Deutsch–Jozsa problem by using interference among configurations instead of observation. Moreover, based on these results, we are led to structures of more general quantum algorithms. Finally, we show a problem that can be efficiently solved by using this type of algorithm and a Walsh transform. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 71–80, 2000
Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Θ (2 n ) queries to an n -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted λ, with query complexities that depend polynomially on λ. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.
Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the NNN given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of NNN nonorthogonal states, ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$, for distinguishing $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.
We discuss a new approach to simulate quantum algorithms using classical probabilistic bits and circuits. Each qubit (a two-level quantum system) is initially mapped to a vector in an eight dimensional probability space (equivalently, to a classical random variable with eight probabilistic outcomes). The key idea in this mapping is to store both the amplitude and phase information of the complex coefficients that describe the qubit state in the probabilities. Due to the identical tensor product structure of combining multiple quantum systems as well as multiple probability spaces, nnn qubits are then mapped to a tensor product of nnn 8-dimensional probabilistic vectors (i.e., the Hilbert space of dimension 2n2^n2n is mapped to a probability space of dimension 8n8^n8n). After this initial mapping, we show how to implement the analogs of single-qubit and two-qubit gates in the probability space using correlation-inducing operations on these classical random variables. The key defining feature of both the mapping to the probability space and the transformations in this space (i.e., operations on the random variables) is that they are not linear, but instead affine. Using this architecture, the evolution of the 2n2^n2n complex coefficients of the quantum system can be tracked in the joint fully-correlated probabilities of the polynomial number of random variables. We then give specific procedures for implementing (1) the Deutsch-Jozsa algorithm, and (2) the Quantum Fourier Transform in the probability space. Identical to the Quantum case, simulating the Quantum Fourier Transform in the probability space requires O(n)O(n)O(n) probabilistic bits and O(n2)O(n^2)O(n2) (i.e., quadratic in the number of quantum bits) operations.