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