# Techniques: Error Mitigation of BQP Computations using Measurement-Based Verification

## What the paper contributes (one paragraph)
The paper gives a modular error mitigation protocol for running BQP (single-bit decision) computations on noisy quantum hardware with time-dependent noise. It reuses verification machinery, interleaving measurement-based computation rounds with trappification test rounds that sample the device error rate without knowing the correct answer, and inherits a theorem bounding the probability of an incorrect classical output exponentially in the number of runs. Its novel ingredient is basketing, a post-selection technique that keeps only consecutive batches of low-noise runs, combined with Bayesian updating to suppress the failure probability exponentially in the number of successful baskets while scaling only linearly in shots. A resource estimation subroutine turns a target confidence into optimal run counts and thresholds. The authors demonstrate the protocol in noisy Qiskit simulation on a 15-qubit measurement pattern that tiles onto IBM heavy-hexagon hardware and supports blind computation. The protocol needs only minimal noise assumptions (Markovian, round-dependent, with independent preparation noise).

## Techniques offered
- **Verification-based error mitigation protocol (interleaved test and computation rounds)** - runs BQP decision computations on a noisy device and returns a classical output together with a certified probability that the output is correct, by interleaving blind computation rounds with verification test rounds.
  - guarantee: statistical bound; the probability that a returned (non-aborted) output is correct is exponentially close to unity in the total number of rounds, given Markovian round-dependent noise.
  - quote: "We present a modular error mitigation protocol for running $\mathsf{BQP}$ computations on a quantum computer with time-dependent noise."
- **Basketing (post-selection on low-noise periods)** - a post-selection technique that uses regularly sampled test-round failure rates to keep only consecutive batches of runs whose noise is below threshold, restoring convergence under fluctuating noise where the underlying verification would abort.
  - guarantee: statistical bound; combined with Bayesian updating it suppresses the failure probability exponentially in the number of successful baskets with only linear scaling in the total number of shots.
  - quote: "We introduce a post-selection technique called \textit{basketing} to address time-dependent noise and reduce overhead."
- **Trappification test rounds for noise sampling and benchmarking** - colourings of the computation graph give indistinguishable test rounds that detect any deviation from correct device behaviour, letting the user benchmark and upper-bound the computation error rate without knowing the correct outcome.
  - guarantee: property test with interactive soundness; a pass/fail check per round implicitly bounds the permitted computation error rate via the blindness-induced indistinguishability of test and computation rounds.
  - quote: "The test rounds serve the purpose of error-detection and allow us to benchmark with high accuracy the error rate of the computation rounds."
- **Resource estimation subroutine** - a minimisation procedure that maps a target success probability (or a fixed run budget) to optimal protocol parameters: total runs, test-round proportion, and the abort threshold.
  - guarantee: static parameter bound; returns optimal n, tau and Phi (or the best achievable correctness bound) subject to the theorem conditions, or aborts if no feasible parameters exist.
  - quote: "We also state the subroutine for a resource estimation procedure, enabling the user to specify some required target accuracy and receive optimal values of parameters for running the protocol."
- **Heavy-hex-tileable universal MBQC measurement pattern** - a concrete 15-qubit measurement-based pattern (realising single- and two-qubit gates) that maps directly onto and tiles across the heavy-hexagon layout of current IBM superconducting hardware to enable universal blind quantum computation.
  - guarantee: none (constructive artefact; demonstrated to compete with current hardware error rates in simulation).
  - quote: "We perform a demonstration of the protocol using classical noisy simulation, presenting a universal measurement pattern which directly maps to (and can be tiled on) the heavy-hex layout of current IBM hardware."

## Where it could apply
- Target primitive(s): sampling and general BQP decision-class circuits (single-bit Boolean output); any MBQC pattern, or circuit-model computations supporting mid-circuit measurement and feed-forward.
- Target application group(s): platforms_tooling, error_correction (as error mitigation / verification tooling).
- Code family / hardware assumptions: measurement-based computation native to photonic hardware; demonstrated on superconducting heavy-hexagon (IBM) layouts; requires Markovian, round-dependent noise with independent state-preparation noise; no specific noise model otherwise.

## Caveats
The protocol is general error mitigation tooling and is suppliable to external sampling or decision-class results, but it certifies a single-bit BQP output rather than an expectation value, so it does not directly supply an estimator bound to VQE or QAOA energies. Like all error mitigation, overhead grows exponentially with circuit depth, limiting it to shallow near-term computations; it also requires mid-circuit measurement with feed-forward and is best suited to devices that exhibit genuinely fluctuating (rather than constant) noise. The verification theorem and the test- and computation-round subroutines are repackaged from prior work (verifBQP); basketing, Bayesian updating, the resource estimation packaging, and the heavy-hex pattern are the paper's own contributions.