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.
 J. Preskill, Bull. Am. Phys. Soc. 58 (2013), arXiv:1203.5813.
 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.
 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.
 M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys. Rev. Lett. 117, 080501 (2016), arXiv:1504.07999.
 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.
 X. Gao, S.-T. Wang, and L.-M. Duan, Phys. Rev. Lett. 118, 040502 (2017), arXiv:1607.04947.
 D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Quantum Sci. Technol. 2, 015004 (2017), arXiv:1602.00703.
 Y. Nakata, M. Koashi, and M. Murao, New J. Phys. 16, 053043 (2014), arXiv:1311.1128.
 E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Commun. Math. Phys. 355, 905 (2017), arXiv:1606.01914.
 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).
 A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation, Graduate studies in mathematics (American Mathematical Society, 2002).
 Y. Shi, Quant. Inf. Comp. 3, 84 (2003), arXiv:quant-ph/0205115.
 A. Paetznick and B. W. Reichardt, Phys. Rev. Lett. 111, 090505 (2013), arXiv:1304.3709.
 A. Y. Kitaev, Russ. Math. Surv. 52, 1191 (1997).
 M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000).
 M. Ozols, How to generate a random unitary matrix (Mar, 2009).
 K. Zyczkowski and M. Kus, J. Phys. A 27, 4235 (1994).
 F. Haake, Quantum signatures of chaos, Springer Series in Synergetics, Vol. 54 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010).
 Supanut Thanasilp, Jirawat Tangpanitanon, Marc-Antoine Lemonde, Ninnat Dangniam, and Dimitris G. Angelakis, "Quantum supremacy and quantum phase transitions", Physical Review B 103 16, 165132 (2021).
 Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón, "Quantum advantage from energy measurements of many-body quantum systems", Quantum 5, 465 (2021).
 Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin, "Sample Complexity of Device-Independently Certified “Quantum Supremacy”", Physical Review Letters 122 21, 210502 (2019).
 J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).
 Martin Kliesch and Ingo Roth, "Theory of Quantum System Certification", PRX Quantum 2 1, 010201 (2021).
 Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa, "How many qubits are needed for quantum computational supremacy?", Quantum 4, 264 (2020).
 Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk, "Quantum advantage of unitary Clifford circuits with magic state inputs", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2225, 20180427 (2019).
 Kaifeng Bu and Dax Enshan Koh, "Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States", Physical Review Letters 123 17, 170502 (2019).
 Yuki Takeuchi, Yasuhiro Takahashi, and Seiichiro Tani, "Hardness of efficiently generating ground states in postselected quantum computation", Physical Review Research 3 1, 013213 (2021).
 Lucas Kocia and Peter Love, "Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits", Quantum 5, 494 (2021).
 Jirawat Tangpanitanon, Supanut Thanasilp, Ninnat Dangniam, Marc-Antoine Lemonde, and Dimitris G. Angelakis, "Expressibility and trainability of parametrized analog quantum systems for machine learning applications", Physical Review Research 2 4, 043364 (2020).
 Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics 15 2, 159 (2019).
 David T. Stephen, Hendrik Poulsen Nautrup, Juani Bermejo-Vega, Jens Eisert, and Robert Raussendorf, "Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter", Quantum 3, 142 (2019).
 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).
 Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani, "Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error", Physical Review Letters 120 20, 200502 (2018).
 Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani, "Quantum Supremacy and the Complexity of Random Circuit Sampling", arXiv:1803.04402.
 Yuki Takeuchi and Tomoyuki Morimae, "Verification of Many-Qubit States", Physical Review X 8 2, 021060 (2018).
 Tomoyuki Morimae, "Hardness of classically sampling the one-clean-qubit model with constant total variation distance error", Physical Review A 96 4, 040302 (2017).
 Xun Gao and Luming Duan, "Efficient classical simulation of noisy quantum computation", arXiv:1810.03176.
 Ryan L. Mann and Michael J. Bremner, "On the Complexity of Random Quantum Computations and the Jones Polynomial", arXiv:1711.00686.
 Man-Hong Yung and Xun Gao, "Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?", arXiv:1706.08913.
 Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh, "Complexity Classification of Conjugated Clifford Circuits", arXiv:1709.01805.
 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup", arXiv:1905.01504.
 Martin Kliesch and Ingo Roth, "Theory of quantum system certification: a tutorial", arXiv:2010.05925.
 Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random quantum circuits anti-concentrate in log depth", arXiv:2011.12277.
The above citations are from Crossref's cited-by service (last updated successfully 2021-08-04 11:01:43) and SAO/NASA ADS (last updated successfully 2021-08-04 11:01:44). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.