{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T11:09:44Z","timestamp":1648984184266},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p> We provide an exact quantum query algorithm that identifies uncorrupted codewords from a degree-d generalized Reed-Muller code of length q<jats:sup>n<\/jats:sup> over the finite field of size q. When d is constant, the algorithm needs \ud835\udcaa(n<jats:sup>d-1<\/jats:sup>) quantum queries, which is optimal. Classically, \u03a9(n<jats:sup>d<\/jats:sup>) queries are necessary to accomplish this task, even with constant probability of error admitted. Our work extends a result by Montanaro about learning multilinear polynomials. <\/jats:p>","DOI":"10.1142\/s0129054117500125","type":"journal-article","created":{"date-parts":[[2017,4,4]],"date-time":"2017-04-04T05:50:23Z","timestamp":1491285023000},"page":"185-194","source":"Crossref","is-referenced-by-count":0,"title":["Identifying Generalized Reed-Muller Codewords by Quantum Queries"],"prefix":"10.1142","volume":"28","author":[{"given":"Stefan","family":"Arnold","sequence":"first","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University, D-89069 Ulm, Germany"}]}],"member":"219","published-online":{"date-parts":[[2017,4,3]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_10"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.013"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"p_4","first-page":"449","volume":"34","author":"de Beaudrap J.","year":"2008","journal-title":"Algorithmica"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.2307\/2304500"},{"key":"p_7","first-page":"189","author":"Kasami T.","journal-title":"IEEE Transactions on Information Theory"},{"key":"p_9","first-page":"482","volume":"25","author":"Kothari R.","year":"2014","journal-title":"Leibniz International Proceedings in Informatics"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.002"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1954.1057465"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_54"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970343141X"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117500125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:59:06Z","timestamp":1565096346000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117500125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2]]},"references-count":12,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2017,4,3]]},"published-print":{"date-parts":[[2017,2]]}},"alternative-id":["10.1142\/S0129054117500125"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117500125","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2]]}}}