  Error correction will add so much overhead to large quantum computations that
we suspect the most efficient algorithms will use a classical co-processor to
do as much work as possible. We present a method to offload portions of a
quantum computation to a classical computer by producing a superposition of
masks which hide a quantum input. With the masks, we can measure the result
without altering the original input and then perform classical computations on
the measured output. If the task has enough structure, the classical
computations will be equivalent to a quantum computation performed in
superposition. We apply this technique to modular inversion, root-finding,
division with remainder, sparse matrix inversion, and inverting generic group
homomorphisms, achieving at least a constant-factor improvement in quantum
operations for each. Unfortunately, it is difficult to uncompute or invert this
technique because of the measurement, and thus we know of no useful algorithm
which benefits from superposition masking.
