{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:26:07Z","timestamp":1777645567209,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2021,11,27]],"date-time":"2021-11-27T00:00:00Z","timestamp":1637971200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2021,11,27]]},"abstract":"<jats:p>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 \u025b-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.<\/jats:p>\n                  <jats:p>\n                    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 \u025b-far from g, where \u025b is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity [Formula: see text]. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is [Formula: see text]. Secondly, we consider 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)| = \u025b and | C( f, g)| = 1 using six queries, while the classical deterministic query complexity for this problem is \u0398(2\n                    <jats:sup>n<\/jats:sup>\n                    ) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus \u025b-far balanced using [Formula: see text] 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\/ \u025b\n                    <jats:sup>2<\/jats:sup>\n                    ). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.\n                  <\/jats:p>","DOI":"10.3233\/fi-2021-2076","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T15:03:16Z","timestamp":1638284596000},"page":"321-344","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":5,"title":["Testing Boolean Functions Properties"],"prefix":"10.1177","volume":"182","author":[{"given":"Xie","family":"Zhengwei","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiu","family":"Daowen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-sen Univ., Guangzhou 510006, China."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cai","family":"Guangya","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[{"name":"Faculty of Informatics, Masaryk University, Brno, Czech Republic."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulo","family":"Mateus","sequence":"additional","affiliation":[{"name":"Instituto de Telecomunica\u00e7\u00f5es, Dept. de Matematica, Instituto Superior T\u00e9cnico, Av. Rovisco Pais 1049-001 Lisbon, Portugal."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2021,11,27]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2021-2076","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2021-2076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:32:35Z","timestamp":1777444355000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2021-2076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,27]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,11,27]]}},"alternative-id":["10.3233\/FI-2021-2076"],"URL":"https:\/\/doi.org\/10.3233\/fi-2021-2076","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,27]]}}}