2014/01/13 by Troels F. Rønnow, Zhihui Wang, Joshua Job +7 · 2 voices · 606 citations
Computer Science · Engineering · Physics and Astronomy · #Advancements in Semiconductor Devices and Circuit Design #Algorithm #Benchmark (surveying) #Computer science #Parallel computing #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum and electron transport phenomena #Quantum computer #Quantum mechanics #Qubit #Speedup #Theoretical computer science #quant-ph
paper · pdf · doi:10.1126/science.1252319
published in Science 345(6195), 420-424 (American Association for the Advancement of Science)
arxiv created 2014/01/13 · arxiv published 2014/01/13 · openalex publication_date 2014/06/20 · arxiv updated 2015/05/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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.