A near-term goal in the field of quantum computation is to realize a minimal device showing a quantum speedup (sometimes dubbed "quantum computational supremacy" or "quantum advantage"). The goal here is to perform a proof-of-principle experiment whose outcome cannot efficiently be predicted on a classical computer. In this talk, we will propose simple quantum simulation architectures that show a quantum speedup in a complexity theoretic sense. Specifically, we consider the classical complexity of simulating the dynamics of translation-invariant Ising models on a 2D square lattice. We show that such models cannot be efficiently classically simulated even for constant times, assuming plausible complexity-theoretic conjectures analogous to those in the famous boson sampling problem, or in the quantum experiments being put forward by Google AI. (Specifically, we will argue that approximately sampling from the output distribution of such a device is classically intractable.) Finally, we will discuss how the correctness of our quantum devices can be efficiently certified using fidelity-witness methods, 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
Comments (0)
No comments found!