Quantum Advantage and Utility

Quantum advantage is a comparison between specified computational procedures on a specified task. Utility asks whether the delivered answer has value under the user’s accuracy, turnaround, reliability, and resource constraints. Neither term has a single universal operational definition. A defensible claim states its meaning before displaying a speedup.

Helpful background. Algorithmic benchmarking defines matched tasks and comparators; resource estimation converts a logical workload into physical requirements. Verification of quantum advantage explains how to test an experimental comparison.

The input, output and accuracy define the task

Describe a computational task by

$$\mathcal T=(\mathcal I,\mathcal O,\epsilon,\delta,\mathcal A),$$

where $\mathcal I$ is the input family, $\mathcal O$ the requested output, $\epsilon$ its error tolerance, $\delta$ the allowed failure probability, and $\mathcal A$ the input-access assumptions. A quantum state proportional to a solution vector and an explicit classical list of that vector’s entries are different outputs. Coherent oracle access and a disk file are different inputs.

An asymptotic separation can be established in a declared model without establishing a practical crossover. An experimental runtime comparison can establish a finite-instance advantage without proving asymptotic scaling. A scientifically useful estimate can be valuable even if a classical method eventually proves faster. These claims answer different questions and should retain different labels.

Preskill’s discussion of noisy intermediate-scale computation emphasizes the gap between controlling a many-qubit device and identifying valuable computational applications. Here that gap becomes a task and resource accounting problem, not a forecast.

Time to an accepted answer

Suppose one independent attempt takes time $t$ and yields a correct, accepted output with probability $p$. If failure is heralded, the expected serial completion time is $t/p$. To achieve at least one success with probability $1-\delta$, the required number of attempts is

$$r=\left\lceil\frac{\log\delta}{\log(1-p)}\right\rceil.$$

For unheralded algorithmic failure, repeating does not by itself identify the correct answer. One needs a verifier, majority procedure with justified assumptions, or another confidence-amplification method. The cost of that mechanism belongs in the comparison.

For stages executed sequentially, the total time includes

$$T_Q=T_{\mathrm{load}}+T_{\mathrm{compile}} +T_{\mathrm{execute}}+T_{\mathrm{verify}}+T_{\mathrm{readout}}.$$

The terms must include all retries and must not count the same operation twice. A pipelined implementation instead needs its actual schedule: adding durations of overlapping stages overestimates wall-clock time. Calibration and setup can be added or amortized over a stated number of jobs. Repeated measurements and mitigation also consume time. Report single-job latency separately from the rate at which a parallel system completes jobs.

Consider a hypothetical solver taking $0.2$ s per attempt. It announces a candidate with probability $a=0.01$; otherwise it reports failure immediately. Each candidate then takes one second to verify. Suppose a candidate is correct with conditional probability $q$, the verifier recognizes correctness perfectly, and unsuccessful cycles restart independently. The mean completion time obeys

$$\mathbb E[T]=0.2+a(1)+(1-aq)\mathbb E[T], \qquad \mathbb E[T]=\frac{0.2+a}{aq}.$$

For $q=1$, this is $21$ s; for $q=0.5$, it is $42$ s. Comparing only the $0.2$ s circuit with a five-second classical solve reverses the decision in both cases. Perfect verification detects bad candidates; it does not make every candidate correct. If the verifier itself makes errors, its completeness and soundness must also enter the calculation. This example illustrates a cost comparison, not a hardware forecast.

Quality and classical effort form a joint frontier

A comparator must target the same output and accuracy. Exact state-vector simulation is not automatically the best classical approach to estimating one local observable. Approximate tensor networks, problem-specific solvers, randomized estimators, and reduced models can be relevant.

Conversely, a classical approximation with an uncontrolled error does not establish a matched result merely because it runs quickly. Describe what is proved, what is empirically checked, and which instances defeat the method. Record algorithm versions, tuning budget, hardware, precision, and energy if energy is part of the claim.

Let $C_Q(n,\epsilon)$ and $C_C(n,\epsilon)$ be costs at matched problem size and error. The formal crossover solves $C_Q=C_C$. If $C_Q=a n^2$ and $C_C=b n^3$, then $n_\star=a/b$. Improving the classical prefactor $b$ by a factor of ten pushes the crossover ten times farther out. A superior exponent can coexist with an inaccessible finite-size crossover.

Beverland and collaborators provide a layered resource-estimation framework for linking algorithms, error correction, and physical qubits. Its lasting lesson is the dependence of application costs on several architectural layers; any quoted numerical estimate must retain the assumptions and application used to obtain it.

Compare a range of instances and uncertainties

A robust comparison varies accuracy, size, and noise within a meaningful range, reports uncertainty, and makes the strongest plausible classical alternative reproducible. A single favorable instance can motivate investigation but cannot characterize a whole workload distribution. If selecting instances after seeing the results, account for that selection.

An unresolved practical crossover is a research question, not a promise that one will appear. An established theorem or demonstrated benchmark should retain its precise scope. The verification and advantage research guide discusses open questions and selected approaches to testing such claims.

Exercises

A protocol accepts each independent attempt with probability $0.2$. How many attempts are needed for success probability at least $0.99$? Does this answer change if acceptance can include incorrect results?

Solution

The requirement is $0.8^r\le0.01$, so $r=21$. This certifies acceptance only. If accepted outputs can be wrong, a reliability model and verification procedure are still needed to certify correctness.

A quantum procedure costs $10^5n$ operations and a classical one $n^2$. What happens to the crossover when quantum loading adds $2n^2$ operations?

Solution

Ignoring loading gives a crossover at $n=10^5$. With loading, quantum cost is $10^5n+2n^2>n^2$ for every positive $n$. The claimed advantage was conditional on an input-access model whose implementation eliminated it in this example.

An experimental claim quotes a ratio of mean runtimes, $\overline T_C/\overline T_Q=2$. Does that imply every instance is twice as fast on the quantum solver?

Solution

No. The ratio summarizes the chosen workload and can hide instances where either solver loses. For two equally weighted instances, take classical times $(1,9)$ and quantum times $(4,1)$. Their means are $5$ and $2.5$, so the ratio is two, although the quantum solver is four times slower on the first instance. Paired results and the workload distribution explain which users benefit. An average of instance-by-instance ratios is also a different statistic from the ratio of averages.

References

• M. E. Beverland et al., “Assessing requirements to scale to practical quantum advantage,” arXiv:2211.07629 (2022). Author preprint.
• J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018). doi:10.22331/q-2018-08-06-79.

Further reading

Questions for comparing quantum claims helps interpret the comparison; negative results and limitations explains what failed crossovers can establish.