  Measurement-based quantum computation (MBQC) is a model of quantum
computation, in which computation proceeds via adaptive single qubit
measurements on a multi-qubit quantum state. It is computationally equivalent
to the circuit model. Unlike the circuit model, however, its classical analog
is little studied. Here we present a classical analog of MBQC whose
computational complexity presents a rich structure. To do so, we identify
uniform families of quantum computations (refining the circuits introduced by
Bremner, Jozsa and Shepherd in Proc. R. Soc. A 467, 459 (2011)) whose output is
likely hard to exactly simulate (sample) classically. We demonstrate that these
circuit families can be efficiently implemented in the MBQC model without
adaptive measurement, and thus can be achieved in a classical analog of MBQC
whose resource state is a probability distribution which has been created
quantum mechanically. Such states (by definition) violate no Bell inequality,
but nevertheless exhibit non-classicality when used as a computational resource
- an imprint of their quantum origin.
