Abstract
Quantum devices promise the efficient solution of problems out of reach for classical computers. However, before reaching the ultimate goal of realizing full fault tolerant quantum computers, significant effort have been made towards showing an unambiguous quantum advantage. In this talk, we will discuss prospects of achieving a complexity-theoretic quantum advantage that lives up to mathematically rigorous standards and is experimentally practically feasible with translationally invariant quantum simulators [1-4]. On a mathematical technical level, we will see how proof techniques of black-box verification [3] and of average-case complexity and anticoncentration come into play. On a physical level, we will elaborate on how such schemes may be realized with realistic near-term quantum devices reminiscent of quantum simulators.
Particular emphasis will be put on showing how to prove anti-concentration, building upon recently developed techniques for random circuit sampling. We develop new techniques that exploit the
insight that approximate 2-designs for the unitary group admit anti-concentration. We prove that the 2D translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs, thus obtaining a significantly stronger result [1]. In an interlude interesting in its own right, we will see how higher-order unitary designs can be realized by means of random Clifford gates, into which a number of non-Clifford gates is interspersed that is - remarkably - independent of the system size [5]. If time allows, I will briefly mention ongoing efforts towards proving quantum advantages in distribution learning.
[1] Closing gaps of a quantum advantage with short-time Hamiltonian dynamics, J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, J. Bermejo-Vega, arXiv:1908.08069 (2019).
[2] Architectures for quantum simulation showing a quantum speedup, J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, J. Eisert Phys. Rev. X 8, 021010 (2018).
[3] Sample complexity of device-independently certified quantum supremacy, D. Hangleiter, M. Kliesch, J. Eisert, C. Gogolin, Phys. Rev. Lett. 122, 210502 (2019).
[4] Dynamical structure factors of dynamical quantum simulators, M. Laura Baez, M. Goihl, J. Haferkamp, J. Bermejo-Vega, M. Gluza, J. Eisert, arXiv:1912.06076 (2019).
[5] Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates, J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, I. Roth, arXiv:2002.09524 (2020).