{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:53:52Z","timestamp":1776106432013,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires \u0398 (2\n            <jats:sup>n<\/jats:sup>\n            ) queries to an\n            <jats:italic>n<\/jats:italic>\n            -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted \u03bb, with query complexities that depend polynomially on \u03bb. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in\n            <jats:italic>n<\/jats:italic>\n            , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of\n            <jats:italic>n<\/jats:italic>\n            . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.\n          <\/jats:p>","DOI":"10.1145\/3456509","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T10:06:14Z","timestamp":1625825174000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Quantum and Randomised Algorithms for Non-linearity Estimation"],"prefix":"10.1145","volume":"2","author":[{"given":"Debajyoti","family":"Bera","sequence":"first","affiliation":[{"name":"IIIT-Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sapv","family":"Tharrmashastha","sequence":"additional","affiliation":[{"name":"IIIT-Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1826"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 11th International Workshop on Coding and Cryptography (WCC\u201919)","author":"Bera Debajyoti","year":"2019"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Conference on Cryptology in India. Springer, 415\u2013432","author":"Bera Debajyoti","year":"2019"},{"key":"e_1_2_1_4_1","unstructured":"Debajyoti Bera and SAPV Tharrmashastha. 2021. Quantum Algorithms for Entropy Testing and Gapped k-Distinctness. arXiv:2103.09033. Retrieved from https:\/\/arxiv.org\/abs\/2103.09033.  Debajyoti Bera and SAPV Tharrmashastha. 2021. Quantum Algorithms for Entropy Testing and Gapped k-Distinctness. arXiv:2103.09033. Retrieved from https:\/\/arxiv.org\/abs\/2103.09033."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12095-015-0150-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_2_1_8_1","unstructured":"\u00c7a\u011fda\u015f \u00c7al\u0131k. 2013. Nonlinearity computation for sparse Boolean functions. arXiv:1305.0860. Retrieved from https:\/\/arxiv.org\/abs\/1305.0860.  \u00c7a\u011fda\u015f \u00c7al\u0131k. 2013. Nonlinearity computation for sparse Boolean functions. arXiv:1305.0860. Retrieved from https:\/\/arxiv.org\/abs\/1305.0860."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756169.1756219"},{"key":"e_1_2_1_10_1","unstructured":"Kaushik Chakraborty and Subhamoy Maitra. 2013. Improved quantum test for linearity of a Boolean function. arxiv:quant-ph\/1306.6195. Retrieved from https:\/\/arxiv.org\/abs\/1306.6195.  Kaushik Chakraborty and Subhamoy Maitra. 2013. Improved quantum test for linearity of a Boolean function. arxiv:quant-ph\/1306.6195. Retrieved from https:\/\/arxiv.org\/abs\/1306.6195."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"374","DOI":"10.3103\/S1066530710040046","article-title":"Mode estimation for discrete distributions","volume":"19","author":"Dutta Santanu","year":"2010","journal-title":"Math. Methods Stat."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_13_1","unstructured":"Xiaoyu He Xiaoming Sun Guang Yang and Pei Yuan. 2018. Exact quantum query complexity of weight decision problems via Chebyshev polynomials. arXiv:1801.05717. Retrieved from https:\/\/arxiv.org\/abs\/1801.05717.  Xiaoyu He Xiaoming Sun Guang Yang and Pei Yuan. 2018. Exact quantum query complexity of weight decision problems via Chebyshev polynomials. arXiv:1801.05717. Retrieved from https:\/\/arxiv.org\/abs\/1801.05717."},{"key":"e_1_2_1_14_1","first-page":"6","article-title":"Quantum tests for the linearity and permutation invariance of Boolean functions","volume":"84","author":"Hillery Mark","year":"2011","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11128-020-02817-z","article-title":"A quantum algorithm to estimate the Gowers norm and linearity testing of Boolean functions","volume":"19","author":"Jothishwaran C. A.","year":"2020","journal-title":"Quantum Information Processing"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/050639090"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Quantum algorithms for the Goldreich-Levin learning problem","volume":"19","author":"Li Hongwei","year":"2019","journal-title":"Quantum Information Processing"},{"key":"e_1_2_1_18_1","volume-title":"Proc. Roy. Soc. A: Math. Phys. Eng. Sci. 471","author":"Montanaro Ashley","year":"2015"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Quantum Boolean functions","volume":"1","author":"Montanaro Ashley","year":"2010","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"e_1_2_1_20_1","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.704118"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.210501"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456509","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:29Z","timestamp":1750193249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3456509"],"URL":"https:\/\/doi.org\/10.1145\/3456509","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}