# Techniques: Heuristic-free Verification-inspired Quantum Benchmarking

## What the paper contributes (one paragraph)
The paper builds a formal bridge between quantum verification and quantum benchmarking. Its central result is a generic compiler that turns any blind verification protocol with strong security into a benchmarking protocol, by reinterpreting the protocol's accept or reject statistics and exploiting the worst-case to average-case reduction that such verification schemes provide. This yields a Certified Implementable Class of Computations (CICC) benchmark, whose output is a statistical lower bound on the success probability of running any computation in a target class on a black-box device, with no noise-model or hardware assumptions and no heuristics. The authors instantiate the compiler on the robust VBQC protocol to give a concrete, scalable, platform-agnostic benchmark that uses trap computations delegated through universal blind quantum computation, and they reframe this concrete protocol as a randomised certification of graph (resource) states for measurement-based quantum computation.

## Techniques offered
- **Verification-to-benchmarking compiler** - a generic construction that compiles any sufficiently secure blind verification scheme into a benchmarking protocol via a worst-case to average-case reduction, so verification improvements transfer directly to benchmarks.
  - guarantee: statistical lower bound on device success probability with no noise-model or hardware assumptions (heuristic-free), derived from the verification scheme's soundness
  - quote: "As our main contribution, we establish a strong link between these two fields by presenting a generic way of compiling blind verification schemes to benchmarking protocols."
- **Certification-based benchmarking (CICC benchmark)** - a formal benchmark framework that certifies the class of computations a device can implement and returns a certified lower bound z on success probability, satisfying correctness, correctly-flagged extractability, and verifiable extractability.
  - guarantee: statistical bound via Hoeffding's inequality; correctly-flagged and verifiable extractability errors become negligible (exponentially small) in the number of rounds, yielding a certificate of computability
  - quote: "In addition, we prove that from any verification scheme one can efficiently compile a CICC benchmark."
- **Trap-based verification benchmarking from robust VBQC** - a concrete, efficient benchmark instantiating the compiler on the robust VBQC protocol, delegating randomly sampled trap computations via universal blind quantum computation and counting activated traps against a threshold.
  - guarantee: exponential security in the trap-activation gap and number of rounds, with overhead only in time and not in quantum hardware size; generalised stabiliser traps give a secure protocol for any threshold below 1/4
  - quote: "We propose here a concrete efficient benchmarking protocol that utilizes the round-based robust VBQC protocol from \cite{kapourniotis2022unifying}."
- **Graph (resource) state certification** - the concrete protocol viewed as a randomised certification of graph states, checking their usefulness as MBQC resource states and characterising devices by the lattice dimensions (width and depth) they can certifiably run.
  - guarantee: property-test style certification that a 2D cluster or graph state is usable for correct MBQC computations, providing a formal figure of merit over certified graph dimensions
  - quote: "In this sense, one can also understand this benchmarking protocol as a kind of resource state certification process with an added layer of randomization."

## Where it could apply
- Target primitive(s): any classical-input classical-output quantum computation expressible as an MBQC measurement pattern (universal circuits compiled to graph states); sampling, VQE, QAOA, QPE, and Trotterised simulation circuits insofar as they map onto certified graph states
- Target application group(s): platforms_tooling (device benchmarking and characterisation); error_correction (verification, certification); broadly application-agnostic by design
- Code family / hardware assumptions: platform-agnostic and noise-model agnostic; assumes a client that can prepare and send single-qubit states and a server holding graph states; MBQC native, or circuit model with mid-circuit measurements; 2D cluster states as the universal resource

## Caveats
The benchmark requires device consistency (the device must implement the same interactive quantum algorithm across all interactions) and interactive communication with sufficient bandwidth. Circuit-model deployment needs mid-circuit measurements, which are not universally available. The scheme is vulnerable to secret-dependent noise in client-server communication, which is left as an open problem, and it tends to reject current noisy hardware because its guarantees are more stringent than heuristic benchmarks. The supplied assurance is a statistical lower bound under these assumptions rather than an unconditional fidelity estimate.