DOI: 10.1126/science.1252319. Defining and detecting quantum speedup

10.1126/science.1252319

Crossref journal-article

American Association for the Advancement of Science (AAAS)

Science (221)

Abstract

How to benchmark a quantum computer Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. Rønnow et al. describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems. Science , this issue p. 420

Bibliography

RÃ¸nnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014). Defining and detecting quantum speedup. Science, 345(6195), 420â424.

Authors 9

Troels F. Rønnow (first)
Zhihui Wang (additional)
Joshua Job (additional)
Sergio Boixo (additional)
Sergei V. Isakov (additional)
David Wecker (additional)
John M. Martinis (additional)
Daniel A. Lidar (additional)
Matthias Troyer (additional)

References 36 Referenced 454

P. W. Shor in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE New York 1994) pp. 124–134.
10.1007/BF02650179
10.1126/science.273.5278.1073
10.1145/8312.8317
10.1103/PhysRevLett.79.325
10.1137/S0097539796300933
10.1103/PhysRevA.88.022316
10.1103/PhysRevE.58.5355
10.1126/science.284.5415.779
10.1126/science.1057726
10.1126/science.220.4598.671
10.1103/PhysRevB.66.094203
10.1126/science.1068774
10.1088/0305-4470/15/10/028
10.1103/PhysRevB.82.024511
10.1088/0953-2048/23/6/065004
10.1088/0953-2048/23/10/105014
10.1038/nature10012
10.1038/nphys2900
S. Boixo T. Albash F. M. Spedalieri N. Chancellor D. A. Lidar http://arxiv.org/abs/1212.1739 (2012).
W. Vinci T. Albash A. Mishra P. A. Warburton D. A. Lidar http://arxiv.org/abs/1403.4228 (2014).
J. A. Smolin G. Smith http://arxiv.org/abs/1305.4904 (2013).
L. Wang T. F. Rønnow S. Boixo S. V. Isakov Z. Wang D. Wecker D. A. Lidar J. M. Martinis M. Troyer http://arxiv.org/abs/1305.5837 (2013).
S. W. Shin G. Smith J. A. Smolin U. Vazirani http://arxiv.org/abs/1401.7087 (2014).
10.1007/s11128-010-0200-3
10.1103/PhysRevLett.109.050501
10.1103/PhysRevX.4.021008
10.1038/ncomms4243
S. Isakov I. Zintchenko T. Rønnow M. Troyer http://arxiv.org/abs/1401.1084 (2014).
10.1007/BF01011918
10.1016/0010-4655(90)90186-5
10.1016/S0004-3702(99)00059-4
10.1103/PhysRevLett.93.207203
C. C. McGeoch C. Wang in Proceedings of the ACM Conference on Computing Frontiers (ACM New York 2013) pp. XX–XX.
10.1103/PhysRevLett.95.250503
S. Santra G. Quiroz G. V. Steeg D. A. Lidar http://arxiv.org/abs/1307.3931 (2013).

Dates

Type	When
Created	11 years, 2 months ago (June 20, 2014, 12:53 a.m.)
Deposited	1 year, 7 months ago (Jan. 10, 2024, 3:21 p.m.)
Indexed	13 hours, 40 minutes ago (Aug. 28, 2025, 8:47 a.m.)
Issued	11 years, 1 month ago (July 25, 2014)
Published	11 years, 1 month ago (July 25, 2014)
Published Print	11 years, 1 month ago (July 25, 2014)

Funders 0

None

BibTeX

@article{R_nnow_2014, title={Defining and detecting quantum speedup}, volume={345}, ISSN={1095-9203}, url={http://dx.doi.org/10.1126/science.1252319}, DOI={10.1126/science.1252319}, number={6195}, journal={Science}, publisher={American Association for the Advancement of Science (AAAS)}, author={Rønnow, Troels F. and Wang, Zhihui and Job, Joshua and Boixo, Sergio and Isakov, Sergei V. and Wecker, David and Martinis, John M. and Lidar, Daniel A. and Troyer, Matthias}, year={2014}, month=jul, pages={420–424} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        28
      ]
    ],
    "date-time": "2025-08-28T12:47:28Z",
    "timestamp": 1756385248209
  },
  "reference-count": 36,
  "publisher": "American Association for the Advancement of Science (AAAS)",
  "issue": "6195",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2014,
        7,
        25
      ]
    ]
  },
  "abstract": "<jats:title>How to benchmark a quantum computer</jats:title>\n          <jats:p>\n            Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. R\u00f8nnow\n            <jats:italic>et al.</jats:italic>\n            describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems.\n          </jats:p>\n          <jats:p>\n            <jats:italic>Science</jats:italic>\n            , this issue p.\n            <jats:related-article xmlns:xlink=\"http://www.w3.org/1999/xlink\" ext-link-type=\"doi\" issue=\"6195\" page=\"420\" related-article-type=\"in-this-issue\" vol=\"345\" xlink:href=\"10.1126/science.1252319\">420</jats:related-article>\n          </jats:p>",
  "DOI": "10.1126/science.1252319",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2014,
        6,
        20
      ]
    ],
    "date-time": "2014-06-20T04:53:02Z",
    "timestamp": 1403239982000
  },
  "page": "420-424",
  "source": "Crossref",
  "is-referenced-by-count": 454,
  "title": "Defining and detecting quantum speedup",
  "prefix": "10.1126",
  "volume": "345",
  "author": [
    {
      "given": "Troels F.",
      "family": "R\u00f8nnow",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Theoretische Physik, ETH (Eidgen\u00f6ssische Technische Hochschule) Zurich, 8093 Zurich, Switzerland."
        }
      ]
    },
    {
      "given": "Zhihui",
      "family": "Wang",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA."
        }
      ]
    },
    {
      "given": "Joshua",
      "family": "Job",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Department of Physics, University of Southern California, Los Angeles, CA 90089, USA."
        }
      ]
    },
    {
      "given": "Sergio",
      "family": "Boixo",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Google, 150 Main Street, Venice Beach, CA 90291, USA."
        },
        {
          "name": "Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA."
        }
      ]
    },
    {
      "given": "Sergei V.",
      "family": "Isakov",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Google, Brandschenkestrasse 110, 8002 Zurich, Switzerland."
        }
      ]
    },
    {
      "given": "David",
      "family": "Wecker",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA."
        }
      ]
    },
    {
      "given": "John M.",
      "family": "Martinis",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Physics, University of California Santa Barbara, CA 93106\u20139530, USA."
        }
      ]
    },
    {
      "given": "Daniel A.",
      "family": "Lidar",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Department of Physics, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA."
        },
        {
          "name": "Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, USA."
        }
      ]
    },
    {
      "given": "Matthias",
      "family": "Troyer",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Theoretische Physik, ETH (Eidgen\u00f6ssische Technische Hochschule) Zurich, 8093 Zurich, Switzerland."
        }
      ]
    }
  ],
  "member": "221",
  "reference": [
    {
      "key": "e_1_3_2_2_2",
      "unstructured": "P. W. Shor in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE New York 1994) pp. 124\u2013134."
    },
    {
      "key": "e_1_3_2_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02650179"
    },
    {
      "key": "e_1_3_2_4_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.273.5278.1073"
    },
    {
      "key": "e_1_3_2_5_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/8312.8317"
    },
    {
      "key": "e_1_3_2_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.79.325"
    },
    {
      "key": "e_1_3_2_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796300933"
    },
    {
      "key": "e_1_3_2_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.88.022316"
    },
    {
      "key": "e_1_3_2_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.58.5355"
    },
    {
      "key": "e_1_3_2_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.284.5415.779"
    },
    {
      "key": "e_1_3_2_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1057726"
    },
    {
      "key": "e_1_3_2_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.220.4598.671"
    },
    {
      "key": "e_1_3_2_13_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevB.66.094203"
    },
    {
      "key": "e_1_3_2_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1068774"
    },
    {
      "key": "e_1_3_2_16_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/0305-4470/15/10/028"
    },
    {
      "key": "e_1_3_2_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevB.82.024511"
    },
    {
      "key": "e_1_3_2_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/0953-2048/23/6/065004"
    },
    {
      "key": "e_1_3_2_19_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/0953-2048/23/10/105014"
    },
    {
      "key": "e_1_3_2_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/nature10012"
    },
    {
      "key": "e_1_3_2_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/nphys2900"
    },
    {
      "key": "e_1_3_2_22_2",
      "unstructured": "S. Boixo T. Albash F. M. Spedalieri N. Chancellor D. A. Lidar http://arxiv.org/abs/1212.1739 (2012)."
    },
    {
      "key": "e_1_3_2_23_2",
      "unstructured": "W. Vinci T. Albash A. Mishra P. A. Warburton D. A. Lidar http://arxiv.org/abs/1403.4228 (2014)."
    },
    {
      "key": "e_1_3_2_24_2",
      "unstructured": "J. A. Smolin G. Smith http://arxiv.org/abs/1305.4904 (2013)."
    },
    {
      "key": "e_1_3_2_25_2",
      "unstructured": "L. Wang T. F. R\u00f8nnow S. Boixo S. V. Isakov Z. Wang D. Wecker D. A. Lidar J. M. Martinis M. Troyer http://arxiv.org/abs/1305.5837 (2013)."
    },
    {
      "key": "e_1_3_2_26_2",
      "unstructured": "S. W. Shin G. Smith J. A. Smolin U. Vazirani http://arxiv.org/abs/1401.7087 (2014)."
    },
    {
      "key": "e_1_3_2_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/s11128-010-0200-3"
    },
    {
      "key": "e_1_3_2_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.109.050501"
    },
    {
      "key": "e_1_3_2_29_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevX.4.021008"
    },
    {
      "key": "e_1_3_2_30_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/ncomms4243"
    },
    {
      "key": "e_1_3_2_31_2",
      "unstructured": "S. Isakov I. Zintchenko T. R\u00f8nnow M. Troyer http://arxiv.org/abs/1401.1084 (2014)."
    },
    {
      "key": "e_1_3_2_32_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01011918"
    },
    {
      "key": "e_1_3_2_33_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0010-4655(90)90186-5"
    },
    {
      "key": "e_1_3_2_34_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0004-3702(99)00059-4"
    },
    {
      "key": "e_1_3_2_35_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.93.207203"
    },
    {
      "key": "e_1_3_2_36_2",
      "unstructured": "C. C. McGeoch C. Wang in Proceedings of the ACM Conference on Computing Frontiers (ACM New York 2013) pp. XX\u2013XX."
    },
    {
      "key": "e_1_3_2_37_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.95.250503"
    },
    {
      "key": "e_1_3_2_38_2",
      "unstructured": "S. Santra G. Quiroz G. V. Steeg D. A. Lidar http://arxiv.org/abs/1307.3931 (2013)."
    }
  ],
  "container-title": "Science",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://www.science.org/doi/pdf/10.1126/science.1252319",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        1,
        10
      ]
    ],
    "date-time": "2024-01-10T20:21:28Z",
    "timestamp": 1704918088000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://www.science.org/doi/10.1126/science.1252319"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2014,
        7,
        25
      ]
    ]
  },
  "references-count": 36,
  "journal-issue": {
    "issue": "6195",
    "published-print": {
      "date-parts": [
        [
          2014,
          7,
          25
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1126/science.1252319"
  ],
  "URL": "http://dx.doi.org/10.1126/science.1252319",
  "relation": {},
  "ISSN": [
    "0036-8075",
    "1095-9203"
  ],
  "subject": [],
  "container-title-short": "Science",
  "published": {
    "date-parts": [
      [
        2014,
        7,
        25
      ]
    ]
  }
}