Quantum computing. Defining and detecting quantum speedup

Troels F Rønnow¹, Zhihui Wang², Joshua Job³, Sergio Boixo⁴, Sergei V Isakov⁵, David Wecker⁶, John M Martinis⁷, Daniel A Lidar⁸, Matthias Troyer⁹

Affiliations

¹ Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland.
² 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.
³ 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.
⁴ Google, 150 Main Street, Venice Beach, CA 90291, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA.
⁵ Google, Brandschenkestrasse 110, 8002 Zurich, Switzerland.
⁶ Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA.
⁷ Department of Physics, University of California Santa Barbara, CA 93106-9530, USA.
⁸ 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.
⁹ Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland. troyer@phys.ethz.ch.

PMID: 25061205
DOI: 10.1126/science.1252319

Quantum computing. Defining and detecting quantum speedup

Troels F Rønnow et al. Science. 2014.

. 2014 Jul 25;345(6195):420-4.

doi: 10.1126/science.1252319. Epub 2014 Jun 19.

Authors

Troels F Rønnow¹, Zhihui Wang², Joshua Job³, Sergio Boixo⁴, Sergei V Isakov⁵, David Wecker⁶, John M Martinis⁷, Daniel A Lidar⁸, Matthias Troyer⁹

Affiliations

¹ Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland.
² 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.
³ 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.
⁴ Google, 150 Main Street, Venice Beach, CA 90291, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA.
⁵ Google, Brandschenkestrasse 110, 8002 Zurich, Switzerland.
⁶ Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA.
⁷ Department of Physics, University of California Santa Barbara, CA 93106-9530, USA.
⁸ 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.
⁹ Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland. troyer@phys.ethz.ch.

PMID: 25061205
DOI: 10.1126/science.1252319

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.

PubMed Disclaimer

Publication types

Actions
Actions

LinkOut - more resources

Full Text Sources
- Atypon
- Ovid Technologies, Inc.
Other Literature Sources
- The Lens - Patent Citations Database
- scite Smart Citations

Save citation to file

Email citation

Add to Collections

Add to My Bibliography

Your saved search

Create a file for external citation management software

Your RSS Feed

Quantum computing. Defining and detecting quantum speedup

Affiliations

Quantum computing. Defining and detecting quantum speedup

Authors

Affiliations

Abstract

Publication types

LinkOut - more resources

Full Text Sources

Other Literature Sources