{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T01:38:58Z","timestamp":1778895538380,"version":"3.51.4"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2016,2,9]],"date-time":"2016-02-09T00:00:00Z","timestamp":1454976000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein\u2013Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformity<jats:italic>\u03b4<jats:sub>f<\/jats:sub><\/jats:italic>of a Boolean function<jats:italic>f<\/jats:italic>. Smaller differential uniformity is, shorter time is needed.<\/jats:p>","DOI":"10.1017\/s0960129516000013","type":"journal-article","created":{"date-parts":[[2016,2,9]],"date-time":"2016-02-09T10:53:20Z","timestamp":1455015200000},"page":"1-13","source":"Crossref","is-referenced-by-count":18,"title":["A quantum algorithm to approximate the linear structures of Boolean functions"],"prefix":"10.1017","volume":"28","author":[{"given":"HONGWEI","family":"LI","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"LI","family":"YANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,2,9]]},"reference":[{"key":"S0960129516000013_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"S0960129516000013_ref7","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0164"},{"key":"S0960129516000013_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60590-8_6"},{"key":"S0960129516000013_ref12","volume-title":"Introduction to Cryptography (in chinese)","author":"Feng","year":"1999"},{"key":"S0960129516000013_ref5","unstructured":"Brassard G. and H\u00f8yer P. (1997). An exact quanum polynimial-time algorithm for Simon's problem. In: Proceedings of the 5th Israeli Symposium on the Theory of Computing Systems (ISTCS'97), 12\u201323."},{"key":"S0960129516000013_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"S0960129516000013_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF00203964"},{"key":"S0960129516000013_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9168-0"},{"key":"S0960129516000013_ref16","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0960129516000013_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"S0960129516000013_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129512000151"},{"key":"S0960129516000013_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"S0960129516000013_ref4","unstructured":"Brassard G. , Dupuis F. , Gambs S. and Tapp A. (2011). An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance. arXiv: 1106.4267v1 [quant-ph] 21 Jun. 2011."},{"key":"S0960129516000013_ref10","doi-asserted-by":"crossref","first-page":"215","DOI":"10.26421\/QIC11.3-4-2","article-title":"Uniform approximation by (quantum) polynomials","volume":"11","author":"Drucker","year":"2011","journal-title":"Quantum Information and Computation"},{"key":"S0960129516000013_ref17","first-page":"68","volume-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science","author":"Kahn","year":"1988"},{"key":"S0960129516000013_ref15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.062329"},{"key":"S0960129516000013_ref13","first-page":"324","article-title":"Character of linear structure of Boolean functions","volume":"17","author":"Feng","year":"1995","journal-title":"Journal of Electronics (in Chinese)"},{"key":"S0960129516000013_ref9","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"S0960129516000013_ref11","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008399109102"},{"key":"S0960129516000013_ref3","first-page":"11","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"Bernstein","year":"1993"},{"key":"S0960129516000013_ref22","first-page":"569","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08)","author":"O'Donnell","year":"2008"},{"key":"S0960129516000013_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129516000013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,3]],"date-time":"2022-06-03T18:31:17Z","timestamp":1654281077000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129516000013\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,9]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["S0960129516000013"],"URL":"https:\/\/doi.org\/10.1017\/s0960129516000013","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,9]]}}}