Anzeige
Erschienen in:
01.03.2019
A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
Erschienen in: Quantum Information Processing | Ausgabe 3/2019
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(F^{n}_{d}\), 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(2^{s})\), where \(s+1=\text {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.