An Exact Quantum Algorithm for the 2-Junta Problem

This paper proposes a novel quantum learning algorithm based on Bernstein and Vazirani’s quantum circuit to find the dependent variables of the 2-junta problem. Typically, for a given Boolean function f  : {0, 1} n  → {0, 1} that depends on only 2 out of n variables, the dependent variables are obta...

Full description

Saved in:
Bibliographic Details
Published in:International journal of theoretical physics 2021, Vol.60 (1), p.80-91
Main Author: Chen, Chien-Yuan
Format: Article
Language:English
Subjects:
Algorithms
Boolean algebra
Boolean functions
Circuits
Dependent variables
Elementary Particles
Machine learning
Mathematical analysis
Mathematical and Computational Physics
Physics
Physics and Astronomy
Quantum Field Theory
Quantum Physics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes a novel quantum learning algorithm based on Bernstein and Vazirani’s quantum circuit to find the dependent variables of the 2-junta problem. Typically, for a given Boolean function f  : {0, 1} n  → {0, 1} that depends on only 2 out of n variables, the dependent variables are obtained by evaluating the function 4 n times in the worst-case. However, the proposed quantum algorithm only requires O ( log 2 n ) function operations in the worst-case. Moreover, the algorithm requires an average of 5.3 function operations at the most when n  ≥ 8.
ISSN:0020-7748
1572-9575
DOI:10.1007/s10773-020-04662-3