Testing Boolean Functions Properties

• Autorzy: Xie Zhengwei , Qiu Daowen , Cai Guangya , Gruska Jozef , Mateus Paulo

Identyfikatory

DOI

10.3233/FI-2021-2076

• Języki publikacji: EN

Abstrakty

EN

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function f , of n variables, is identical with a given function g or is ε-far from g, where ε is the parame- ter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O( 1√ε ). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ( 1 ε ). Secondly, we con- sider the D-J problem from the perspective of functional correlations and let C(f, g) denote the correlation of f and g. We propose an exact quantum algorithm for making distinction between |C(f, g)| = ε and |C(f, g)| = 1 using six queries, while the classical deterministic query com- plexity for this problem is Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε-far balanced using O( 1 ε ) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.

Słowa kluczowe

EN

Deutsch-Jozsa Algorithm; quantum amplitude amplification; identity testing; correlation testing; balancedness testing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 4
• Strony: 321--344
• Opis fizyczny: Bibliogr. 40 poz., tab.

Twórcy

autor

Xie Zhengwei

• School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou

autor

Qiu Daowen

• School of Computer Science and Engineering, Sun Yat-sen Univ., Guangzhou

autor

Cai Guangya

• School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou

autor

Gruska Jozef

• Faculty of Informatics, Masaryk University, Brno,

autor

Mateus Paulo

• Instituto de Telecomunicações, Dept. de Matematica, Instituto Superior Técnico,Lisbon, Portugal

Bibliografia

• [1] Fischer E, Kindler G, Ron D, Safra S, Samorodnitsky A. Testing juntas. Journal of Computer and System Sciences, 2004. 68(4):753-787. doi:10.1016/j.jcss.2003.11.004.
• [2] Blais E, Weinstein A, Yoshida Y. Partially symmetric functions are efficiently isomorphism testable. SIAM Journal on Computing, 2015. 44(2):411-432. doi:10.1137/140971877
• [3] Alon N, Blais E, Chakraborty S, Garciasoriano D, Matsliah A. Nearly tight bounds for testing function isomorphism. SIAM Journal on Computing, 2013. 42(2):459-493. doi:10.1137/110832677.
• [4] Chen X, Servedio RA, Tan L, Waingarten E, Xie J. Settling the query complexity of non-adaptive junta testing. Journal of the ACM, 2018. 65(6):40. doi:10.1145/3213772.
• [5] Blais E, Canonne CL, Eden T, Levi A, Ron D. Tolerant junta testing and the connection to sub-modular optimization and function isomorphism. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. SIAM, 2018 pp. 2113-2132. doi:10.1137/1.9781611975031.138. URL https://doi.org/10.1137/1.9781611975031.138.
• [6] Blais E, Odonnell R. Lower bounds for testing function isomorphism. In: 2010 IEEE Conferences on Computational Complexity, Cambridge, Massachusetts, USA, 9-12 June, 2010. IEEE, 2010 pp. 235-246. doi:10.1109/CCC.2010.30.
• [7] Bellare M, Coppersmith D, Hastad J, Kiwi M, Sudan M. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 1996. 42(6):1781-1795. doi:10.1109/18.556674.
• [8] Chakrabarty D, Seshadhri C. An o(n) monotonicity tester for boolean functions over the hypercube. SIAM Journal on Computing, 2016. 45(2):461-472. doi:10.1137/13092770X.
• [9] Chen X, Servedio RA, Tan L. New algorithms and lower bounds for monotonicity testing. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. IEEE Computer Society, 2014 pp. 286-295. doi:10.1109/FOCS.2014.38. URL https://doi.org/10.1109/FOCS.2014.38.
• [10] Friedl K, Santha M, Magniez F, Sen P. Quantum testers for hidden group properties. Fundamenta Informaticae, 2009. 91(2):325-340. doi:10.3233/FI-2009-0046.
• [11] Gruska J. Quantum computing. McGraw Hill, 1999. ISBN 978-0077095031.
• [12] Qiu D, Zheng S. Revisiting Deutsch-Jozsa algorithm. Information and Computation, Received 4 March 2020, Accepted 13 July 2020, Available online 6 August 2020. doi:10.1016/j.ic.2020.104605. URL https://doi.org/10.1016/j.ic.2020.104605.
• [13] Grover LK. A Fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. ACM, 1996 pp. 212-219. doi:10.1145/237814.237866. URL https://doi.org/10.1145/237814.237866.
• [14] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997. 26(5):1484-1509. doi:10.1137/S0097539795293172.
• [15] Buhrman H, Fortnow L, Newman I, Rohrig H. Quantum property testing. SIAM Journal on Computing, 2008. 37(5):1387-1400. doi:10.1137/S0097539704442416.
• [16] Hillery M, Andersson E. Quantum tests for the linearity and permutation invariance of Boolean functions. Physical Review A, 2011. 84(6):062329. doi:10.1103/PhysRevA.84.062329.
• [17] Bravyi S, Harrow AW, Hassidim A. Quantum algorithms for testing properties of distributions. IEEE Transactions on Information Theory, 2011. 57(6):3971-3981. doi:10.1109/TIT.2011.2134250.
• [18] Montanaro A, De Wolf R. A Survey of quantum property testing. Theory of Computing, 2016. 7(7):1-81. doi:10.4086/toc.gs.2016.007.
• [19] Hou X. Classification of cosets of the Reed-Muller code R(m-3, m). Discrete Mathematics, 1994. 128(1):203-224. doi:10.1016/0012-365X(94)90113-9.
• [20] Gao G, Guo Y, Zhao Y. Recent results on balanced symmetric Boolean functions. IEEE Transactions on Information Theory, 2016. 62(9):5199-5203. doi:10.1109/TIT.2015.2455052.
• [21] Cusick T, Cheon Y. Affine equivalence for rotation symmetric Boolean functions in 2k variables. Designs, Codes and Cryptography, 2012. 63(2):273-294. doi:10.1007/s10623-011-9553-6.
• [22] Canright DR, Chung JH, St˘anic˘a P. Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions. Discrete Mathematics, 2015. 338(12):2197-2211. doi:10.1016/j.disc.2015.05.017.
• [23] Fuller JE. Analysis of affine equivalent boolean functions for cryptography. Ph.D. thesis, Queensland University of Technology, 2003. URL https://eprints.qut.edu.au/15828/.
• [24] Batu T, Fortnow L, Fischer E, Kumar R, Rubinfeld R, White P. Testing Random Variables for In-dependence and Identity. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, 14-17 October, 2001. IEEE Computer Society, 2001 pp. 442-451. doi: 10.1109/SFCS.2001.959920. URL https://doi.org/10.1109/SFCS.2001.959920.
• [25] Diakonikolas I, Kane DM, Nikishkin V. Testing identity of structured distributions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. SIAM, 2015 pp. 1841-1854. doi:10.1137/1.9781611973730.123. URL https://doi.org/10.1137/1.9781611973730.123.
• [26] Cai J, Green F, Thierauf T. On the correlation of symmetric functions. Mathematical Systems Theory, 1996. 29(3):245-258. doi:10.1007/BF01201278.
• [27] Castro FN, Medina LA. Linear recurrences and asymptotic behavior of exponential sums of symmetric Boolean functions. The electronic journal of combinatorics, 2011. 18(2):8. doi:10.37236/2004.
• [28] Castro FN, Medina LA. Asymptotic behavior of perturbations of symmetric functions. Annals of Combinatorics, 2014. 18(3):397-417. doi:10.1007/s00026-014-0230-0.
• [29] Castro FN, Medina LA, St˘anic˘a P. Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent. Applicable Algebra in Engineering, Communication and Computing, 2018. 29(5):433-453. doi:10.1007/s00200-018-0351-5.
• [30] Kavut S, Maitra S, Tang D. Construction and search of balanced Boolean functions on even number of variables towards excellent autocorrelation profile. Designs, Codes and Cryptography, 2019. 87(2):261-276. doi:10.1007/s10623-018-0522-1.
• [31] Zhang Y, Yang G, Hung WNN, Zhang J. Computing affine equivalence classes of Boolean functions by group isomorphism. IEEE Transactions on Computers, 2016. 65(12):3606-3616. doi:10.1109/TC.2016.2557329.
• [32] Qiu D, Zheng S. Generalized Deutsch-Jozsa problem and the optimal quantum algorithm. Physical Review A, 2018. 97(6):062331. doi:10.1103/physreva.97.062331.
• [33] Ehlich H, Zeller K. Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift, 1964. 86(1):41-44. doi:10.1007/BF01111276.
• [34] Buhrman H, De Wolf R. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 2002. 288(1):21-43. doi:10.1016/S0304-3975(01)00144-X.344 Z. Xie, et al. / Testing Boolean Functions Properties
• [35] Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences, 1992. 439(1907):553-558. doi:10.1098/rspa.1992.0167.
• [36] Brassard G, Hoyer P, Mosca M, Tapp A. Quantum amplitude amplification and estimation. Contemporary Mathematics, 2002. 305:53-74. doi:10.1090/conm/305/05215.
• [37] Gruska J, Qiu D, Zheng S. Generalisation of the Distributed Deutsch-Jozsa promise problem. Mathematical Structures in Computer Science, 2017. 27(3):311-331. doi:10.1017/S0960129515000158.
• [38] Nayak A, Wu F. The quantum query complexity of approximating the median and related statistics. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, USA, May 1-4, 1999. ACM, 1999 pp. 384-393. doi:10.1145/301250.301349. URL https://doi.org/10.1145/301250.301349.
• [39] Johnson RA, Miller I, Freund JE. Probability and Statistics for Engineers. Pearson Education, 2017. ISBN 978-0321986245.
• [40] Mousavi N. How tight is Chernoff bound. 2010 URL https://ece.uwaterloo.ca/~nmousavi/Papers/Chernoff-Tightness.pdf.