title: Quantum computing. Defining and detecting quantum speedup.
abstract: The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.
authors: Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland.
authors: Troels F
authors: TF
authors: Rønnow
authors: Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA. Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA.
authors: Zhihui
authors: Z
authors: Wang
authors: Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA. Department of Physics, University of Southern California, Los Angeles, CA 90089, USA.
authors: Joshua
authors: J
authors: Job
authors: Google, 150 Main Street, Venice Beach, CA 90291, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA.
authors: Sergio
authors: S
authors: Boixo
authors: Google, Brandschenkestrasse 110, 8002 Zurich, Switzerland.
authors: Sergei V
authors: SV
authors: Isakov
authors: Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA.
authors: David
authors: D
authors: Wecker
authors: Department of Physics, University of California Santa Barbara, CA 93106-9530, USA.
authors: John M
authors: JM
authors: Martinis
authors: Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA. Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA. Department of Physics, University of Southern California, Los Angeles, CA 90089, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA. Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, USA.
authors: Daniel A
authors: DA
authors: Lidar
authors: Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland. troyer@phys.ethz.ch.
authors: Matthias
authors: M
authors: Troyer