Outperforming classical computers with near-term quantum devices: a new optic

DIPC Seminars

Juan Bermejo Vega, Dahlem Center for Complex Quantum Systems, Freie Universität Berlin
Donostia International Physics Center
Add to calendar
Subscribe to Newsletter
Outperforming classical computers with near-term quantum devices: a new optic A near-term goal in the field of quantum computation is to realize a minimal quantum device showing a quantum computational speedup or advantage. (A state of affairs sometimes dubbed ""quantum computational supremacy""). The goal here is to perform a quantum experiment whose outcome cannot be efficiently predicted or simulated on a classical computer. A hope of this program is that performing such an experiment may be much simpler than building a fault- tolerant universal quantum computer. Several candidate quantum devices have been proposed for this task, including boson samplers and Google-AI’s random quantum circuits. In this talk, I will review the current approaches towards demonstrating superior quantum computational power, as well as the major “loopholes” that they face, concerning scalability, complexity-theoretic soundness, and verifiability. I will further introduce a new proposal inspired by cold-atomic quantum simulators that tackles several of these loopholes [1-2]. Our proposal is based on short-time evolutions of translation-invariant Ising models on a 2D square lattice. We show that the latter cannot be efficiently classically simulated (even approximately) assuming plausible complexity-theoretic conjectures analogous to those in boson sampling. Finally, we will discuss how the correctness of our quantum devices can be efficiently certified given the ability to perform reliable single qubit measurements. Our proposal is motivated by optical-lattice cold-atom hardware and provides a path towards demonstrating a verifiable quantum speedup using realistic resources. Based on: [1] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Architectures for quantum simulation showing a quantum speedup, Phys. Rev. X 8, 021010, https://arxiv.org/abs/1703.00466 [2] D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, Anticoncentration theorems for schemes showing a quantum speedup, Quantum 2, 65 (2018), https://arxiv.org/abs/1706.03786 Host: Geza Giedke