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.
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.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
Quantum Computing
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. Ronnow 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][1]
[1]: /lookup/volpage/345/420?iss=6195
As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any bench-mark should follow-randomized, well-defined, holistic, device independent-and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the is-sue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2 % to 1 % on a 26-qubit circuit with the inclusion of dynamical decoupling.
As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any benchmark should follow -- randomized, well-defined, holistic, device independent -- and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the issue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2% to 1% on a 26-qubit circuit with the inclusion of dynamic decoupling.
One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.
To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is $\ensuremath{\sim}{10}^{8}$ times faster than simulated annealing on conventional computer hardware for problems with approximately 103 variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.