For questions about either: comparing the performance of a quantum algorithm with a classical algorithm (or set of classical algorithms) independent of devices; or the ratio of time to solution of a quantum device running a specific algorithm to a classical device running a specific algorithm.
As per the paper Defining and detecting quantum speedup, the definition of quantum speedup has a few variants:
Device dependent definition
- Denoting the time for a specific implementation of an algorithm on a classical device to solve a problem of size $N$ as $C\left(N\right)$ and the time for a specific implementation of an algorithm on a quantum device as $Q\left(N\right)$, the first definition of quantum speedup is $$S\left(N\right) = \frac{C\left(N\right)}{Q\left(N\right)}$$
Device independent definitions
Here, independent of devices, a classical algorithm is compared with a quantum algorithm and speedup is the same ratio as for 1. comparing the quantum algorithm, taking time $Q\left(N\right)$, with the classical algorithm, taking time $C\left(N\right)$.
- Provable quantum speedup:
there exists a proof that no classical algorithm can outperform a given quantum algorithm
e.g. Grover's algorithm
Strong quantum speedup:
using the performance of the best classical algorithm ... whether such an algorithm is known or not
Quantum speedup:
comparing to the best available classical algorithm instead of the best possible classical algorithm
- Potential quantum speedup:
compared to a specific classical algorithm or a set of classical algorithms
- Limited quantum speedup:
comparing specifically with classical algorithms that “correspond” to the quantum algorithm in the sense that they implement the same algorithmic approach, but on classical hardware.
e.g. comparing quantum annealing with simulated annealing
