Anzeige
Erschienen in:
01.01.2021
An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
Erschienen in: Quantum Information Processing | Ausgabe 1/2021
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
This paper modifies Chen’s algorithm, which is the first exact quantum algorithm for testing 2-junta, and proposes an exact quantum learning algorithm for finding dependent variables of the Boolean function \( f: \left\{ {0, 1} \right\}^{n} \to \left\{ {0, 1} \right\} \) with one uncomplemented product of three variables. Typically, the dependent variables are obtained by evaluating the function \( 2n \) times in the worst case. However, our proposed quantum algorithm only requires \( O\left( {\log_{2} n} \right) \) function operations in the worst case. In addition, the average number to perform the function is evaluated. Our algorithm requires an average of \( 7.23 \) function operations at the most when \( n \ge 16 \). We also show that our algorithm cannot solve \( k \)-junta problem with one uncomplemented product if \( 4 \le k < n/2 \).