We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function.
- Authors
Wu, WanQing; Zhang, HuanGuo
- Abstract
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.
- Subjects
QUANTUM acoustics; MATHEMATICAL optimization; GEOMETRIC vertices; BOOLEAN matrices; ALGEBRA
- Publication
Quantum Information Processing, 2019, Vol 18, Issue 3, p1
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-019-2175-z