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 \).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Lu, Z.Q.: The elements of statistical learning: data mining, inference, and prediction. J. R. Stat. Soc. Ser. A 173(3), 693–694 (2010)
Mossel, E., O’Donnell, R., Servedio, R.P.: Learning juntas. In: Proc. 35th Ann. ACM Symp. Theo. Comp., 206–212 (2003)
Atıcı, A., Servedio, R.A.: Quantum algorithms for learning and testing juntas. Quantum Inf. Process. 6(5), 323–348 (2007)
Floess, D.F., Andersson, E., Hillery, M.: Quantum algorithms for testing Boolean functions. arXiv:quant-ph/1006.1423 (2010)
Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411–1473 (1997)
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortsch. Phys. Prog. Phys. 46(4–5), 493–505 (1998)
Ambainis, A., Belovs, A., Regev, O., de Wolf, R.: Efficient quantum algorithms for (gapped) group testing and junta testing. In: Proc. 27th Ann. ACM-SIAM Symp. Discr. Alg., 903–922 (2016)
El-Wazan, K., Younes, A., Doma, S.B.: A quantum algorithm for testing juntas in Boolean functions. arXiv:quant-ph/1701.02143 (2017)
Chen, C.-Y.: An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables. Quantum Inf. Process. 19(7), 213 (2020)
Younes, A.: A fast quantum algorithm for the affine Boolean function identification. The Eur. Phys. J. Plus. 130(2), 34 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Chen, CY. An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product. Quantum Inf Process 20, 36 (2021). https://doi.org/10.1007/s11128-020-02953-6
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-020-02953-6