{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T04:35:37Z","timestamp":1773462937281,"version":"3.50.1"},"reference-count":69,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T00:00:00Z","timestamp":1526947200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes \"quantum computational supremacy\". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.<\/jats:p>","DOI":"10.22331\/q-2018-05-22-65","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T17:39:50Z","timestamp":1527010790000},"page":"65","source":"Crossref","is-referenced-by-count":51,"title":["Anticoncentration theorems for schemes showing a quantum speedup"],"prefix":"10.22331","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4766-7967","authenticated-orcid":false,"given":"Dominik","family":"Hangleiter","sequence":"first","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3727-8092","authenticated-orcid":false,"given":"Juan","family":"Bermejo-Vega","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]},{"given":"Martin","family":"Schwarz","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3033-1292","authenticated-orcid":false,"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2018,5,22]]},"reference":[{"key":"1","unstructured":"J. Preskill, Bull. Am. Phys. Soc. 58 (2013), arXiv:1203.5813."},{"key":"2","unstructured":"S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollw\u00f6ck, J. Eisert, and I. Bloch, Nature Phys. 8, 325 (2012), arXiv:1101.2659."},{"key":"3","doi-asserted-by":"publisher","unstructured":"J.-Y. Choi, S. Hild, J. Zeiher, P. Schau\u00df, A. Rubio-Abadal, T. Yefsah, V. Khemani, D. A. Huse, I. Bloch, and C. Gross, Science 352, 1547 (2016), arXiv:1604.04178.","DOI":"10.1126\/science.aaf8834"},{"key":"4","doi-asserted-by":"publisher","unstructured":"S. Braun, M. Friesdorf, S. S. Hodgman, M. Schreiber, J. P. Ronzheimer, A. Riera, M. del Rey, I. Bloch, J. Eisert, and U. Schneider, Proc. Natl. Ac. Sc. 112, 3641 (2015), arXiv:1403.7199.","DOI":"10.1073\/pnas.1408861112"},{"key":"5","unstructured":"S. Aaronson and A. Arkhipov, Th. Comp. 9, 143 (2013), arXiv:1011.3245."},{"key":"6","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys. Rev. Lett. 117, 080501 (2016), arXiv:1504.07999.","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, Quantum 1, 8 (2017).","DOI":"10.22331\/q-2017-04-25-8"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics , 1 (2018), arXiv:1608.00263.","DOI":"10.1038\/s41567-018-0124-x"},{"key":"9","doi-asserted-by":"publisher","unstructured":"X. Gao, S.-T. Wang, and L.-M. Duan, Phys. Rev. Lett. 118, 040502 (2017), arXiv:1607.04947.","DOI":"10.1103\/PhysRevLett.118.040502"},{"key":"10","doi-asserted-by":"publisher","unstructured":"J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Phys. Rev. X 8, 021010 (2018), arXiv:1703.00466.","DOI":"10.1103\/PhysRevX.8.021010"},{"key":"11","doi-asserted-by":"publisher","unstructured":"T. Morimae, Phys. Rev. A 96, 040302 (2017), arXiv:1704.03640.","DOI":"10.1103\/PhysRevA.96.040302"},{"key":"12","doi-asserted-by":"publisher","unstructured":"J. Miller, S. Sanders, and A. Miyake, Phys. Rev. A 96, 062320 (2017), arXiv:1703.11002.","DOI":"10.1103\/PhysRevA.96.062320"},{"key":"13","unstructured":"C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, ``Boson sampling in the light of sample complexity,'' arXiv:1306.3995."},{"key":"14","unstructured":"S. Aaronson and A. Arkhipov, ``BosonSampling is far from uniform,'' arXiv:1309.7460."},{"key":"15","doi-asserted-by":"publisher","unstructured":"D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Quantum Sci. Technol. 2, 015004 (2017), arXiv:1602.00703.","DOI":"10.1088\/2058-9565\/2\/1\/015004"},{"key":"16","unstructured":"T. Kapourniotis and A. Datta, (2017), arXiv:1703.09568."},{"key":"17","doi-asserted-by":"publisher","unstructured":"L. Stockmeyer, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, 118 (1983).","DOI":"10.1145\/800061.808740"},{"key":"18","doi-asserted-by":"publisher","unstructured":"A. P. Lund, M. J. Bremner, and T. C. Ralph, npj Quant. Inf. 3, 15 (2017), arXiv:1702.03061.","DOI":"10.1038\/s41534-017-0018-2"},{"key":"19","unstructured":"M. Schwarz and M. V. den Nest, (2013), arXiv:1310.6749."},{"key":"20","unstructured":"R. Jozsa and M. V. d. Nest, Quant. Inf. Comp 14, 0633\u20130648 (2014), arXiv:1305.6190."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Y. Nakata, M. Koashi, and M. Murao, New J. Phys. 16, 053043 (2014), arXiv:1311.1128.","DOI":"10.1088\/1367-2630\/16\/5\/053043"},{"key":"22","doi-asserted-by":"publisher","unstructured":"D. Gross, K. Audenaert, and J. Eisert, J. Math. Phys. 48, 052104 (2007), arXiv:quant-ph\/0611002.","DOI":"10.1063\/1.2716992"},{"key":"23","doi-asserted-by":"publisher","unstructured":"F. G. S. L. Brand\u00e3o, A. W. Harrow, and M. Horodecki, Commun. Math. Phys. 346, 397 (2016).","DOI":"10.1007\/s00220-016-2706-8"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proc. Roy. Soc. 467, 2126 (2010), arXiv:1005.1407.","DOI":"10.1098\/rspa.2010.0301"},{"key":"25","doi-asserted-by":"crossref","unstructured":"B. M. Terhal and D. P. DiVincenzo, Quant. Inf. Comp. 4, 134 (2004), arXiv:quant-ph\/0205133.","DOI":"10.26421\/QIC4.2-5"},{"key":"26","doi-asserted-by":"publisher","unstructured":"G. Kuperberg, Theory of Computing 11, 183 (2015).","DOI":"10.4086\/toc.2015.v011a006"},{"key":"27","doi-asserted-by":"publisher","unstructured":"K. Fujii and T. Morimae, New J. Phys. 19, 033003 (2017), arXiv:1311.2128.","DOI":"10.1088\/1367-2630\/aa5fdb"},{"key":"28","unstructured":"A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, (2018), arXiv:1803.04402."},{"key":"29","unstructured":"R. L. Mann and M. J. Bremner, arXiv:1711.00686."},{"key":"30","doi-asserted-by":"publisher","unstructured":"S. Aaronson, ``P$\\neq$NP?'' in Open problems in mathematics (Springer, 2016).","DOI":"10.1007\/978-3-319-32162-2"},{"key":"31","doi-asserted-by":"publisher","unstructured":"L. Fortnow, in Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05 (ACM, 2005).","DOI":"10.1145\/1060590.1060609"},{"key":"32","doi-asserted-by":"publisher","unstructured":"R. M. Karp and R. J. Lipton, in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80 (1980).","DOI":"10.1145\/800141.804678"},{"key":"33","doi-asserted-by":"publisher","unstructured":"C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009), arXiv:quant-ph\/0606161.","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"34","doi-asserted-by":"publisher","unstructured":"E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Commun. Math. Phys. 355, 905 (2017), arXiv:1606.01914.","DOI":"10.1007\/s00220-017-2950-6"},{"key":"35","doi-asserted-by":"publisher","unstructured":"A. W. Harrow and R. A. Low, Commun. Math. Phys. 291, 257 (2009), arXiv:0802.1919.","DOI":"10.1007\/s00220-009-0873-6"},{"key":"36","unstructured":"H. Zhu, R. Kueng, M. Grassl, and D. Gross, (2016), arXiv:1609.08172."},{"key":"37","doi-asserted-by":"publisher","unstructured":"J. Emerson, Y. S. Weinstein, M. Saraceno, S. Lloyd, and D. G. Cory, Science 302, 2098 (2003).","DOI":"10.1126\/science.1090790"},{"key":"38","doi-asserted-by":"publisher","unstructured":"W. G. Brown, Y. S. Weinstein, and L. Viola, Phys. Rev. A 77, 040303 (2008), arXiv:0802.2675.","DOI":"10.1103\/PhysRevA.77.040303"},{"key":"39","doi-asserted-by":"publisher","unstructured":"C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, R. Barends, B. Burkett, Y. Chen, and Z. Chen, (2017), Science 13 360, Issue 6385, (2018).","DOI":"10.1126\/science.aao4309"},{"key":"40","doi-asserted-by":"publisher","unstructured":"P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, Inf. Proc. Lett. 75, 101 (2000), arXiv:quant-ph\/9906054.","DOI":"10.1016\/S0020-0190(00)00084-3"},{"key":"41","doi-asserted-by":"crossref","unstructured":"A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation, Graduate studies in mathematics (American Mathematical Society, 2002).","DOI":"10.1090\/gsm\/047"},{"key":"42","unstructured":"Y. Shi, Quant. Inf. Comp. 3, 84 (2003), arXiv:quant-ph\/0205115."},{"key":"43","doi-asserted-by":"publisher","unstructured":"A. Paetznick and B. W. Reichardt, Phys. Rev. Lett. 111, 090505 (2013), arXiv:1304.3709.","DOI":"10.1103\/PhysRevLett.111.090505"},{"key":"44","doi-asserted-by":"publisher","unstructured":"P. W. Shor, in Proc. of 37th Conf. Found. Comp. Sci. (1996) pp. 56-65, arXiv:quant-ph\/9605011.","DOI":"10.1109\/SFCS.1996.548464"},{"key":"45","unstructured":"E. Knill, R. Laflamme, and W. Zurek, (1996), arXiv:quant-ph\/9610011."},{"key":"46","doi-asserted-by":"publisher","unstructured":"E. Knill, R. Laflamme, and W. H. Zurek, Proc. Roy. Soc. A 454, 365 (1998).","DOI":"10.1098\/rspa.1998.0166"},{"key":"47","doi-asserted-by":"publisher","unstructured":"D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).","DOI":"10.1038\/46503"},{"key":"48","doi-asserted-by":"publisher","unstructured":"R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003), arXiv:quant-ph\/0301052.","DOI":"10.1103\/PhysRevA.68.022312"},{"key":"49","unstructured":"L. A. Goldberg and H. Guo, (2014), arXiv:1409.5627."},{"key":"50","doi-asserted-by":"publisher","unstructured":"A. Y. Kitaev, Russ. Math. Surv. 52, 1191 (1997).","DOI":"10.1070\/RM1997v052n06ABEH002155"},{"key":"51","unstructured":"M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000)."},{"key":"52","doi-asserted-by":"publisher","unstructured":"C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM J. Comp. 26, 1510 (1997), arXiv:quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"},{"key":"53","doi-asserted-by":"publisher","unstructured":"S. Aaronson, Proc. Roy. Soc. A 461, 2063 (2005), arXiv:quant-ph\/0412187.","DOI":"10.1098\/rspa.2005.1546"},{"key":"54","doi-asserted-by":"publisher","unstructured":"H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahl\u00e9n, ACM Trans. Algorithms 10, 21:1 (2014).","DOI":"10.1145\/2635812"},{"key":"55","doi-asserted-by":"publisher","unstructured":"S. X. Cui and Z. Wang, J. Math. Phys. 56, 032202 (2015).","DOI":"10.1063\/1.4914941"},{"key":"56","doi-asserted-by":"publisher","unstructured":"A. Bocharov, M. Roetteler, and K. M. Svore, Phys. Rev. A 91, 052317 (2015), arXiv:1409.3552.","DOI":"10.1103\/PhysRevA.91.052317"},{"key":"57","unstructured":"R. Cleve, D. Leung, L. Liu, and C. Wang, Quant. Inf. Comp. 16, 0721 (2016), arXiv:1501.04592."},{"key":"58","doi-asserted-by":"publisher","unstructured":"R. Koenig and J. A. Smolin, J. Math. Phys. 55, 122202 (2014), arXiv:1406.2170.","DOI":"10.1063\/1.4903507"},{"key":"59","unstructured":"J. Eisert, M. Friesdorf, and C. Gogolin, Nature Phys 11, 124 (2015), arXiv:1408.5148."},{"key":"60","doi-asserted-by":"publisher","unstructured":"A. Polkovnikov, K. Sengupta, A. Silva, and M. Vengalattore, Rev. Mod. Phys. 83, 863 (2011), arXiv:1007.5331.","DOI":"10.1103\/RevModPhys.83.863"},{"key":"61","unstructured":"R. Jozsa, (2006), arXiv:quant-ph\/0603163."},{"key":"62","doi-asserted-by":"publisher","unstructured":"R. Impagliazzo and R. Paturi, in Proc. XIV IEEE Conf. Comp. Compl. (1999) pp. 237-240.","DOI":"10.1109\/CCC.1999.766282"},{"key":"63","unstructured":"S. Aaronson and L. Chen, (2016), arXiv:1612.05903."},{"key":"64","unstructured":"M. Ozols, How to generate a random unitary matrix (Mar, 2009)."},{"key":"65","unstructured":"F. Mezzadri, (2006), arXiv:math-ph\/0609050."},{"key":"66","doi-asserted-by":"publisher","unstructured":"Y. S. Weinstein and C. S. Hellberg, Phys. Rev. A 72, 022331 (2005).","DOI":"10.1103\/PhysRevA.72.022331"},{"key":"67","doi-asserted-by":"publisher","unstructured":"K. Zyczkowski and M. Kus, J. Phys. A 27, 4235 (1994).","DOI":"10.1088\/0305-4470\/27\/12\/028"},{"key":"68","doi-asserted-by":"publisher","unstructured":"M. Pozniak, K. Zyczkowski, and M. Kus, J. Phys. A 31, 1059 (1998), arXiv:chao-dyn\/9707006.","DOI":"10.1088\/0305-4470\/31\/3\/016"},{"key":"69","doi-asserted-by":"crossref","unstructured":"F. Haake, Quantum signatures of chaos, Springer Series in Synergetics, Vol. 54 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010).","DOI":"10.1007\/978-3-642-05428-0"}],"container-title":["Quantum"],"original-title":[],"language":"en","deposited":{"date-parts":[[2022,8,24]],"date-time":"2022-08-24T00:48:29Z","timestamp":1661302109000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2018-05-22-65\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,22]]},"references-count":69,"URL":"https:\/\/doi.org\/10.22331\/q-2018-05-22-65","relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,22]]},"article-number":"65"}}