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

SpringerBriefs in computer science

Simon’s Algorithm and Autocorrelation Spectrum

Tharrmashastha Sapv, Debajyoti Bera, Arpita Maitra, Subhamoy Maitra

Published Jan 1, 2021• 2 citations
Publisher
DOI
10.1007/978-981-16-3061-3_4

Related papers

Efficient Quantum Algorithms Related to Autocorrelation Spectrum

Debajyoti Bera, Subhamoy Maitra, Tharrmashastha Sapv

Lecture notes in computer science•Jan 1, 2019•5 citations

Tight Bounds for Simon’s Algorithm

Xavier Bonnetain

Lecture notes in computer science•Jan 1, 2021•18 citations

The Autocorrelation, the Spectrum, and Phase Retrieval

Rick P. Trebino, Erik Zeek

Springer eBooks•Jan 1, 2000•5 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

Feasibility Analysis of Grover-meets-Simon Algorithm

Qianru Zhu, Huiqin Xie, Qiqing Xia +1 more

Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.

arXiv:2301.06706•Jan 17, 2023•1 citation

Exact distributed quantum algorithm for generalized Simon’s problem

Hao Li, Daowen Qiu, Le Luo +1 more

Abstract Simon’s problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor’s algorithm. The generalized Simon’s problem is a natural extension of Simon’s problem, and also a special hidden subgroup problem: Given a function f : {0, 1} n → {0, 1} m , with the property that for any x, y ∈ {0, 1} n , there is some unknown hidden subgroup S ≤ Z n 2 such that f (x) = f (y) iff x ⊕ y ∈ S, where |S| = 2 k for some 0 ≤ k ≤ n (m ≥ n − k). The goal of generalized Simon’s problem is to find the hidden subgroup S. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon’s problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential acceleration compared to the distributed classical algorithm. When contrasted with the centralized quantum algorithm for the generalized Simon’s problem, our algorithm’s oracle requires fewer qubits, thus making it easier to be physically implemented. Particulary, the exact distributed quantum algorithm we develop for the generalized Simon’s problem outperforms the best previously proposed distributed quantum algorithm for Simon’s problem in terms of generalizability and exactness.

arXiv:2307.14315•Acta Informatica•Mar 10, 2024•21 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.
Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.
Abstract Simon’s problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor’s algorithm. The generalized Simon’s problem is a natural extension of Simon’s problem, and also a special hidden subgroup problem: Given a function f : {0, 1} n → {0, 1} m , with the property that for any x, y ∈ {0, 1} n , there is some unknown hidden subgroup S ≤ Z n 2 such that f (x) = f (y) iff x ⊕ y ∈ S, where |S| = 2 k for some 0 ≤ k ≤ n (m ≥ n − k). The goal of generalized Simon’s problem is to find the hidden subgroup S. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon’s problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential acceleration compared to the distributed classical algorithm. When contrasted with the centralized quantum algorithm for the generalized Simon’s problem, our algorithm’s oracle requires fewer qubits, thus making it easier to be physically implemented. Particulary, the exact distributed quantum algorithm we develop for the generalized Simon’s problem outperforms the best previously proposed distributed quantum algorithm for Simon’s problem in terms of generalizability and exactness.