Error mitigation of BQP computations using measurement-based verification

We present a modular error mitigation protocol for running bounded-error quantum polynomial time (BQP) computations on a quantum computer with time-dependent noise. Utilizing existing tools from quantum verification and measurement-based quantum computation, our protocol interleaves standard computation rounds alongside test rounds for noise sampling and inherits an exponential bound (in the number of circuit runs) on the probability that a returned classical output is correct. We introduce a postselection technique called to address time-dependent noise and reduce overhead. The result is an error mitigation protocol which requires minimal noise assumptions, making it straightforwardly implementable on existing, noisy intermediate-scale quantum devices. 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.