Verification at Scale

Verification at scale asks how limited measurements can support a precise claim about a quantum device when full state reconstruction or exact classical simulation is unaffordable. The answer depends on the claim: estimating one observable, certifying a target state, validating a channel, and verifying an arbitrary computation require different evidence and assumptions.

Helpful background. State tomography explains reconstruction costs; shadow tomography develops property estimation. This page compares the guarantees those procedures can provide, rather than replacing their derivations.

A certificate has a claim and a failure probability

A verifier should accept a device satisfying the target specification with high probability: this is completeness. Its soundness error bounds the acceptance probability of any device outside the allowed specification, under the stated assumptions. A high acceptance rate by itself says nothing about whether bad devices also pass. Tests often leave a tolerance region between the clearly good and clearly bad cases. Measurement calibration, independence assumptions, computational power, and access to the device are part of the guarantee.

A general $n$-qubit density matrix has $4^n-1$ real parameters. Estimating a small family of observables can require vastly less information. But low cost is obtained by narrowing the target or using additional structure; it does not make the entire unknown state known.

The survey by Eisert and collaborators organizes these distinctions among characterization, benchmarking, and certification. In practice one should begin with the scientific quantity the user needs and then choose the weakest sufficient certificate.

Local observations can miss global differences

For $n\ge2$, consider the $n$-qubit GHZ state and its incoherent mixture,

$$\begin{aligned} |\mathrm{GHZ}\rangle&= \frac{|0\rangle^{\otimes n}+|1\rangle^{\otimes n}}{\sqrt2},\\ \rho_{\mathrm{mix}}&= \frac{\bigl(|0\rangle\langle0|\bigr)^{\otimes n} +\bigl(|1\rangle\langle1|\bigr)^{\otimes n}}{2}. \end{aligned}$$

Their reductions on every proper subset of qubits coincide: tracing out even one qubit kills the off-diagonal coherence. Nevertheless, $X^{\otimes n}$ has expectation one in the GHZ state and zero in the mixture. Agreement on all low-weight marginals therefore cannot certify arbitrary global coherence.

This example explains why a test can be strong for its intended observables and weak for another task. It does not show that global properties always require exponentially many samples: ideal measurement of each qubit in the $X$ basis and multiplication of its $\pm1$ outcomes directly measures $X^{\otimes n}$. This yields one bounded sample per preparation regardless of $n$. Readout errors can attenuate the measured parity and require separate treatment. The probability that every local setting happens to be $X$ in an independent uniform random-Pauli experiment is instead $3^{-n}$. Choosing measurements for the intended question can matter more than reconstructing many unrelated properties.

Structure can convert energy into a fidelity bound

Suppose a known Hamiltonian has a unique ground state $|\psi_0\rangle$, known ground energy $E_0$, and certified spectral gap at least $\Delta>0$. Its spectral decomposition gives

$$H-E_0 I\ge \Delta\bigl(I-|\psi_0\rangle\langle\psi_0|\bigr).$$

For any state $\rho$, defining $F_0=\langle\psi_0|\rho|\psi_0\rangle$ yields

$$F_0\ge1-\frac{\operatorname{Tr}(\rho H)-E_0}{\Delta}.$$

Here $F_0$ is the squared overlap convention for pure-target fidelity. If a confidence interval gives an upper energy bound $E_{\mathrm{up}}$, substitute it for the unknown energy. With $E_{\mathrm{up}}-E_0=0.03\Delta$, one certifies $F_0\ge0.97$ at that confidence level. A negative lower bound on fidelity is merely uninformative and can be replaced by zero.

The assumptions do the work. A guessed gap is insufficient; a degenerate ground space gives a subspace-weight bound instead of a unique-state fidelity. Measuring many Hamiltonian terms can also be costly, and systematic measurement bias can invalidate the energy interval. This is a useful certificate only when the Hamiltonian structure and measurement precision are accessible.

Shadows and interaction address different problems

Classical-shadow methods estimate selected properties through randomized measurements. Their sample complexity depends on the observables and measurement ensemble, often summarized by a shadow norm, as well as logarithmically on the number of requested properties. The logarithmic dependence is not a promise of inexpensive estimation for every observable: nonlocal observables can have large shadow norms. Huang, Kueng, and Preskill establish this tradeoff.

Interactive verification instead changes how a computation is performed and checked. Mahadev’s classical-verifier protocol obtains computational soundness under a quantum hardness assumption for learning with errors. This is an established conditional theorem; it does not provide assumption-free verification of an arbitrary archived output file, nor does the theorem alone establish practical overhead.

Trusted small quantum verifiers, cryptographic assumptions, restricted state families, and physical calibration are different resources. A comparison should state which are available before calling a procedure scalable.

Compose the errors that matter

For an observable estimate, distinguish sampling uncertainty from preparation error, measurement-model error, and classical numerical error. If bounded outcome samples in $[-1,1]$ are independent, Hoeffding’s inequality gives

$$\Pr(|\widehat\mu-\mu|\ge\epsilon) \le2e^{-N\epsilon^2/2}.$$

Repeated sampling controls this statistical term, not an unknown calibration bias. If the measured observable differs from the intended one by operator norm at most $b$, its expectation can shift by at most $b$ regardless of sample count.

For example, suppose an energy estimate lies $0.01\Delta$ above the known ground energy. If a statistical upper error is $0.02\Delta$ and a separately justified bound on measurement bias is $0.015\Delta$, the safe energy excess is $0.045\Delta$, giving $F_0\ge0.955$. Collecting more samples reduces the statistical allowance, but leaves the bias allowance. If the gap or bias bounds themselves fail with nonzero probability, combine those failure probabilities with the sampling one, for example by a union bound.

The verification research guide discusses open questions and selected approaches. A scalable test must retain its exact target, trusted resources and total error as the device grows.

Exercises

How many independent bounded samples suffice under the Hoeffding bound for additive error $0.02$ with failure probability at most $0.01$?

Solution

One needs $N\ge2\log(200)/(0.02)^2$, or $26\,492$ samples after rounding up. This conservative bound assumes the samples correspond to the intended observable and the device distribution is stationary.

A two-dimensional ground space has a known gap to excitations. What does the energy argument certify, and why is that weaker than certifying one specified superposition?

Solution

It gives $\operatorname{Tr}(\rho P_0)\ge1-(E-E_0)/\Delta$ for the ground-space projector $P_0$. Energy is identical for every state inside that space, including mixtures, so it cannot distinguish a desired coherent superposition from another ground-space state.

An energy confidence bound fails with probability at most $0.01$, and a separately estimated calibration bound fails with probability at most $0.02$. What confidence follows for a fidelity bound that needs both, without assuming independence?

Solution

The probability that at least one required bound fails is at most $0.01+0.02=0.03$. Thus the combined statement has at least 97% coverage under the two procedures’ assumptions. Neither taking the larger confidence nor multiplying the two confidences is justified without further information. Reusing data does not invalidate this union bound if each individual probability guarantee remains valid.

References

• J. Eisert et al., “Quantum certification and benchmarking,” Nature Reviews Physics 2, 382–390 (2020). doi:10.1038/s42254-020-0186-4.
• H.-Y. Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,” Nature Physics 16, 1050–1057 (2020). Author preprint.
• U. Mahadev, “Classical verification of quantum computations,” 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, 259–267 (2018). Author preprint.

Further reading

Verification of quantum simulation treats model and device validation; blind and delegated quantum computation separates privacy from verification.