{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T05:06:58Z","timestamp":1718946418577},"reference-count":0,"publisher":"Rinton Press","issue":"13&14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2016,10]]},"abstract":"<jats:p>The k\u2019th frequency moment of a sequence of integers is defined as F_k = Sum_ j n^k _j , where n_j is the number of times that j occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate F_k up to relative error epsilon. We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate F_k. We describe quantum algorithms for F_0, F_2 and F_\u221e in this model which substantially outperform the best possible classical algorithms in certain parameter regimes.<\/jats:p>","DOI":"10.26421\/qic16.13-14-5","type":"journal-article","created":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T05:40:32Z","timestamp":1614318032000},"page":"1169-1190","source":"Crossref","is-referenced-by-count":4,"title":["The quantum complexity of approximating the frequency moments"],"prefix":"10.26421","volume":"16","author":[{"given":"Ashley","family":"Montanaro","sequence":"first","affiliation":[]}],"member":"10955","published-online":{"date-parts":[[2016,10]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T05:40:33Z","timestamp":1614318033000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC16.13-14-5.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10]]},"references-count":0,"journal-issue":{"issue":"13&14","published-online":{"date-parts":[[2016,10]]},"published-print":{"date-parts":[[2016,10]]}},"URL":"https:\/\/doi.org\/10.26421\/qic16.13-14-5","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10]]}}}