Anticoncentration theorems for schemes showing a quantum speedup

Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

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.

Most near-term proposals for demonstrating a quantum speedup are based on sampling from the output probability distribution of certain random circuits. The technique most often used to prove the speedup for these tasks requires complexity-theoretic conjectures about the sampled distribution to be assumed, one of them being that the distribution `anticoncentrates'. Here, we prove this conjecture for two-designs as well as for a scheme based on the constant-time evolution of a translation-invariant Ising model. Our results give rise to a range of schemes exhibiting a quantum speedup that satisfy this condition by construction, covering a number of experimentally relevant settings, including random universal circuits, diagonal unitaries, Clifford+T circuits and instances of quantum simulation schemes.

► BibTeX data

► References

[1] J. Preskill, Bull. Am. Phys. Soc. 58 (2013), arXiv:1203.5813.
arXiv:1203.5813

[2] S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch, Nature Phys. 8, 325 (2012), arXiv:1101.2659.
https://doi.org/doi:10.1038/nphys2232
arXiv:1101.2659

[3] J.-Y. Choi, S. Hild, J. Zeiher, P. Schauß, A. Rubio-Abadal, T. Yefsah, V. Khemani, D. A. Huse, I. Bloch, and C. Gross, Science 352, 1547 (2016), arXiv:1604.04178.
https://doi.org/10.1126/science.aaf8834
arXiv:1604.04178

[4] 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.
https://doi.org/10.1073/pnas.1408861112
arXiv:1403.7199

[5] S. Aaronson and A. Arkhipov, Th. Comp. 9, 143 (2013), arXiv:1011.3245.
arXiv:1011.3245

[6] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys. Rev. Lett. 117, 080501 (2016), arXiv:1504.07999.
https://doi.org/10.1103/PhysRevLett.117.080501
arXiv:1504.07999

[7] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8

[8] 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.
https://doi.org/10.1038/s41567-018-0124-x
arXiv:1608.00263

[9] X. Gao, S.-T. Wang, and L.-M. Duan, Phys. Rev. Lett. 118, 040502 (2017), arXiv:1607.04947.
https://doi.org/10.1103/PhysRevLett.118.040502
arXiv:1607.04947

[10] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Phys. Rev. X 8, 021010 (2018), arXiv:1703.00466.
https://doi.org/10.1103/PhysRevX.8.021010
arXiv:1703.00466

[11] T. Morimae, Phys. Rev. A 96, 040302 (2017), arXiv:1704.03640.
https://doi.org/10.1103/PhysRevA.96.040302
arXiv:1704.03640

[12] J. Miller, S. Sanders, and A. Miyake, Phys. Rev. A 96, 062320 (2017), arXiv:1703.11002.
https://doi.org/10.1103/PhysRevA.96.062320
arXiv:1703.11002

[13] C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, ``Boson sampling in the light of sample complexity,'' arXiv:1306.3995.
arXiv:1306.3995

[14] S. Aaronson and A. Arkhipov, ``BosonSampling is far from uniform,'' arXiv:1309.7460.
arXiv:1309.7460

[15] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Quantum Sci. Technol. 2, 015004 (2017), arXiv:1602.00703.
https://doi.org/10.1088/2058-9565/2/1/015004
arXiv:1602.00703

[16] T. Kapourniotis and A. Datta, (2017), arXiv:1703.09568.
arXiv:1703.09568

[17] L. Stockmeyer, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, 118 (1983).
https://doi.org/10.1145/800061.808740

[18] A. P. Lund, M. J. Bremner, and T. C. Ralph, npj Quant. Inf. 3, 15 (2017), arXiv:1702.03061.
https://doi.org/10.1038/s41534-017-0018-2
arXiv:1702.03061

[19] M. Schwarz and M. V. den Nest, (2013), arXiv:1310.6749.
arXiv:1310.6749

[20] R. Jozsa and M. V. d. Nest, Quant. Inf. Comp 14, 0633–0648 (2014), arXiv:1305.6190.
arXiv:1305.6190

[21] Y. Nakata, M. Koashi, and M. Murao, New J. Phys. 16, 053043 (2014), arXiv:1311.1128.
https://doi.org/10.1088/1367-2630/16/5/053043
arXiv:1311.1128

[22] D. Gross, K. Audenaert, and J. Eisert, J. Math. Phys. 48, 052104 (2007), arXiv:quant-ph/​0611002.
https://doi.org/10.1063/1.2716992
arXiv:quant-ph/0611002

[23] F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Commun. Math. Phys. 346, 397 (2016).
https://doi.org/10.1007/s00220-016-2706-8

[24] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proc. Roy. Soc. 467, 2126 (2010), arXiv:1005.1407.
https://doi.org/10.1098/rspa.2010.0301
arXiv:1005.1407

[25] B. M. Terhal and D. P. DiVincenzo, Quant. Inf. Comp. 4, 134 (2004), arXiv:quant-ph/​0205133.
arXiv:quant-ph/0205133

[26] G. Kuperberg, Theory of Computing 11, 183 (2015).
https://doi.org/10.4086/toc.2015.v011a006

[27] K. Fujii and T. Morimae, New J. Phys. 19, 033003 (2017), arXiv:1311.2128.
https://doi.org/10.1088/1367-2630/aa5fdb
arXiv:1311.2128

[28] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, (2018), arXiv:1803.04402.
arXiv:1803.04402

[29] R. L. Mann and M. J. Bremner, arXiv:1711.00686.
arXiv:1711.00686

[30] S. Aaronson, ``P$\neq$NP?'' in Open problems in mathematics (Springer, 2016).
https://doi.org/10.1007/978-3-319-32162-2

[31] L. Fortnow, in Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05 (ACM, 2005).
https://doi.org/10.1145/1060590.1060609

[32] R. M. Karp and R. J. Lipton, in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80 (1980).
https://doi.org/10.1145/800141.804678

[33] C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009), arXiv:quant-ph/​0606161.
https://doi.org/10.1103/PhysRevA.80.012304
arXiv:quant-ph/0606161

[34] E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Commun. Math. Phys. 355, 905 (2017), arXiv:1606.01914.
https://doi.org/10.1007/s00220-017-2950-6
arXiv:1606.01914

[35] A. W. Harrow and R. A. Low, Commun. Math. Phys. 291, 257 (2009), arXiv:0802.1919.
https://doi.org/10.1007/s00220-009-0873-6
arXiv:0802.1919

[36] H. Zhu, R. Kueng, M. Grassl, and D. Gross, (2016), arXiv:1609.08172.
arXiv:1609.08172

[37] J. Emerson, Y. S. Weinstein, M. Saraceno, S. Lloyd, and D. G. Cory, Science 302, 2098 (2003).
https://doi.org/10.1126/science.1090790

[38] W. G. Brown, Y. S. Weinstein, and L. Viola, Phys. Rev. A 77, 040303 (2008), arXiv:0802.2675.
https://doi.org/10.1103/PhysRevA.77.040303
arXiv:0802.2675

[39] 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).
https://doi.org/10.1126/science.aao4309

[40] P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, Inf. Proc. Lett. 75, 101 (2000), arXiv:quant-ph/​9906054.
https://doi.org/10.1016/S0020-0190(00)00084-3
arXiv:quant-ph/9906054

[41] A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation, Graduate studies in mathematics (American Mathematical Society, 2002).

[42] Y. Shi, Quant. Inf. Comp. 3, 84 (2003), arXiv:quant-ph/​0205115.
arXiv:quant-ph/0205115

[43] A. Paetznick and B. W. Reichardt, Phys. Rev. Lett. 111, 090505 (2013), arXiv:1304.3709.
https://doi.org/10.1103/PhysRevLett.111.090505
arXiv:1304.3709

[44] P. W. Shor, in Proc. of 37th Conf. Found. Comp. Sci. (1996) pp. 56-65, arXiv:quant-ph/​9605011.
https://doi.org/10.1109/SFCS.1996.548464
arXiv:quant-ph/9605011

[45] E. Knill, R. Laflamme, and W. Zurek, (1996), arXiv:quant-ph/​9610011.
arXiv:quant-ph/9610011

[46] E. Knill, R. Laflamme, and W. H. Zurek, Proc. Roy. Soc. A 454, 365 (1998).
https://doi.org/10.1098/rspa.1998.0166

[47] D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).
https://doi.org/10.1038/46503

[48] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003), arXiv:quant-ph/​0301052.
https://doi.org/10.1103/PhysRevA.68.022312
arXiv:quant-ph/0301052

[49] L. A. Goldberg and H. Guo, (2014), arXiv:1409.5627.
arXiv:1409.5627

[50] A. Y. Kitaev, Russ. Math. Surv. 52, 1191 (1997).
https://doi.org/10.1070/RM1997v052n06ABEH002155

[51] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000).

[52] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM J. Comp. 26, 1510 (1997), arXiv:quant-ph/​9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[53] S. Aaronson, Proc. Roy. Soc. A 461, 2063 (2005), arXiv:quant-ph/​0412187.
https://doi.org/10.1098/rspa.2005.1546
arXiv:quant-ph/0412187

[54] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlén, ACM Trans. Algorithms 10, 21:1 (2014).
https://doi.org/10.1145/2635812

[55] S. X. Cui and Z. Wang, J. Math. Phys. 56, 032202 (2015).
https://doi.org/10.1063/1.4914941

[56] A. Bocharov, M. Roetteler, and K. M. Svore, Phys. Rev. A 91, 052317 (2015), arXiv:1409.3552.
https://doi.org/10.1103/PhysRevA.91.052317
arXiv:1409.3552

[57] R. Cleve, D. Leung, L. Liu, and C. Wang, Quant. Inf. Comp. 16, 0721 (2016), arXiv:1501.04592.
arXiv:1501.04592

[58] R. Koenig and J. A. Smolin, J. Math. Phys. 55, 122202 (2014), arXiv:1406.2170.
https://doi.org/10.1063/1.4903507
arXiv:1406.2170

[59] J. Eisert, M. Friesdorf, and C. Gogolin, Nature Phys 11, 124 (2015), arXiv:1408.5148.
https://doi.org/doi:10.1038/nphys3215
arXiv:1408.5148

[60] A. Polkovnikov, K. Sengupta, A. Silva, and M. Vengalattore, Rev. Mod. Phys. 83, 863 (2011), arXiv:1007.5331.
https://doi.org/10.1103/RevModPhys.83.863
arXiv:1007.5331

[61] R. Jozsa, (2006), arXiv:quant-ph/​0603163.
arXiv:quant-ph/0603163

[62] R. Impagliazzo and R. Paturi, in Proc. XIV IEEE Conf. Comp. Compl. (1999) pp. 237-240.
https://doi.org/10.1109/CCC.1999.766282

[63] S. Aaronson and L. Chen, (2016), arXiv:1612.05903.
arXiv:1612.05903

[64] M. Ozols, How to generate a random unitary matrix (Mar, 2009).
http:/​/​home.lu.lv/​~sd20008/​papers/​essays/​Random

[65] F. Mezzadri, (2006), arXiv:math-ph/​0609050.
arXiv:math-ph/0609050

[66] Y. S. Weinstein and C. S. Hellberg, Phys. Rev. A 72, 022331 (2005).
https://doi.org/10.1103/PhysRevA.72.022331

[67] K. Zyczkowski and M. Kus, J. Phys. A 27, 4235 (1994).
https://doi.org/10.1088/0305-4470/27/12/028

[68] M. Pozniak, K. Zyczkowski, and M. Kus, J. Phys. A 31, 1059 (1998), arXiv:chao-dyn/​9707006.
https://doi.org/10.1088/0305-4470/31/3/016
arXiv:chao-dyn/9707006

[69] F. Haake, Quantum signatures of chaos, Springer Series in Synergetics, Vol. 54 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010).

► Cited by (beta)

[1] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics (2018).

(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)