A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function

摘要

The degree of a Boolean function is a basic primitive that has applications in coding theory and cryptography. This paper considers a problem of computing the degree of a perfect nonlinear Boolean function in a quantum system. The details are as follows: Given a promise that the function f is either linear or perfect nonlinear in Fdn, we propose a quantum algorithm 1 to distinguish which case it is with a high probability, where d is an even number. Furtherly, for computing the degree of a perfect nonlinear Boolean function f, we present a quantum Algorithm 2 to solve it by calling quantum Algorithm 1 when d=2. The quantum query complexity of the proposed quantum Algorithm 2 is O(s), and the space complexity (the number of quantum logic gate) is O(2s), where s+1=deg(f). The analysis shows that the quantum Algorithm 2 proposed in this paper is more efficient than any classical algorithm for solving this problem.