  We present two verification protocols where the correctness of a "target"
computation is checked by means of "trap" computations that can be efficiently
simulated on a classical computer. Our protocols rely on a minimal set of
noise-free operations (preparation of eight single-qubit states or measurement
of four observables, both on a single plane of the Bloch sphere) and achieve
linear overhead. To the best of our knowledge, our protocols are the least
demanding techniques able to achieve linear overhead. They represent a step
towards further reducing the quantum requirements for verification.
