Application Figure of Merit

This section introduces the different figure of merit employed depending on the application context.

Optimization

Time to Solution (\(TTS\))

The Time To Solution (TSS) was introduced in [1] to evaluate the performance scaling of Quantum Annealers. It quantifies the minimum number of runs \(R\) required to sample the optimal solution at least once within the \(R\) runs with probability \(p\):

where \(s\) is the empirical success probability (i.e., probability of finding the ground state in a single run). The time to solution is then defined as the total time required to perform the \(R\) runs. In its original formulation, TTS accounts solely for the annealing time per run \(t_a\) and does not include additional overheads such as system calibration, initialization, measurement, delays between runs, etc…

Time to Epsilon (\(TT\epsilon\))

The TTS can be extended to the Time to \(\epsilon\)-close solution [2] which is the time required to find a state that is \(\epsilon\)-close to the ground state at least once within the \(R\) runs with probability \(p_{c \leq c^* + \epsilon \lvert c^* \rvert}\). The optimal cost is denoted \(c^*\) (we consider here a minimization problem).

Speedup ratio

The authors of [1] introduce a speedup ratio. \(C(N)\) (resp. \(Q(N)\)) is the time used by a classical (resp. quantum) device to find the optimal or approximate solution to a problem of size \(N\). The speedup ratio can be defined as:

\(C(N)\) (resp. \(Q(N)\)) can be estimated using \(TTS\) or \(TT\epsilon\) figure of merit.

References

1. [1]T. F. Rønnow et al., “Defining and detecting quantum speedup,” science, vol. 345, no. 6195, pp. 420–424, 2014.
2. [2]H. Munoz-Bauza and D. Lidar, “Scaling Advantage in Approximate Optimization with Quantum Annealing,” Physical Review Letters, vol. 134, no. 16, Apr. 2025, doi: 10.1103/physrevlett.134.160601. [Online]. Available at: http://dx.doi.org/10.1103/PhysRevLett.134.160601