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

Lecture notes in computer science

Efficient Quantum Algorithms Related to Autocorrelation Spectrum

Debajyoti Bera, Subhamoy Maitra, Tharrmashastha Sapv

Published Jan 1, 2019• 5 citations
Publisher
DOI
10.1007/978-3-030-35423-7_21

Related papers

Simon’s Algorithm and Autocorrelation Spectrum

Tharrmashastha Sapv, Debajyoti Bera, Arpita Maitra +1 more

SpringerBriefs in computer science•Jan 1, 2021•2 citations

Quantum algorithms for quantum dynamics

Alexander Miessen, Pauline J. Ollitrault, Francesco Tacchino +1 more

Nature Computational Science•Dec 30, 2022•93 citations

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

Quantum algorithms for the generalized eigenvalue problem

Jin‐Min Liang, Shu‐Qian Shen, Ming Li +1 more

arXiv:2112.02554•Quantum Information Processing•Dec 28, 2021•17 citations

Progress in Quantum Algorithms

Peter W. Shor

Quantum Information Processing•Oct 1, 2004•62 citations

Empirical relations between static and dynamic exponents for Ising model cluster algorithms

Paul Coddington, CLIVE F. BAILLIE

We have measured the autocorrelations for the Swendsen-Wang and the Wolff cluster update algorithms for the Ising model in two, three, and four dimensions. The data for the Wolff algorithm suggest that the autocorrelations are linearly related to the specific heat, in which case the dynamic critical exponent is ${\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}$${\mathit{E}}^{\mathrm{W}}$=\ensuremath{\alpha}/\ensuremath{\nu}. For the Swendsen-Wang algorithm, scaling the autocorrelations by the average maximum cluster size gives either a constant or a logarithm, which implies that ${\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}$${\mathit{E}}^{\mathrm{SW}}$=\ensuremath{\beta}/\ensuremath{\nu} for the Ising model.

Physical Review Letters•Feb 17, 1992•46 citations
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.
We have measured the autocorrelations for the Swendsen-Wang and the Wolff cluster update algorithms for the Ising model in two, three, and four dimensions. The data for the Wolff algorithm suggest that the autocorrelations are linearly related to the specific heat, in which case the dynamic critical exponent is zint,{\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}zint,​EW{\mathit{E}}^{\mathrm{W}}EW=\ensuremath{\alpha}/\ensuremath{\nu}. For the Swendsen-Wang algorithm, scaling the autocorrelations by the average maximum cluster size gives either a constant or a logarithm, which implies that zint,{\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}zint,​ESW{\mathit{E}}^{\mathrm{SW}}ESW=\ensuremath{\beta}/\ensuremath{\nu} for the Ising model.