  We propose examples of a hybrid quantum-classical simulation where a
classical computer assisted by a small quantum processor can efficiently
simulate a larger quantum system. First we consider sparse quantum circuits
such that each qubit participates in O(1) two-qubit gates. It is shown that any
sparse circuit on n+k qubits can be simulated by sparse circuits on n qubits
and a classical processing that takes time $2^{O(k)} poly(n)$. Secondly, we
study Pauli-based computation (PBC) where allowed operations are
non-destructive eigenvalue measurements of n-qubit Pauli operators. The
computation begins by initializing each qubit in the so-called magic state.
This model is known to be equivalent to the universal quantum computer. We show
that any PBC on n+k qubits can be simulated by PBCs on n qubits and a classical
processing that takes time $2^{O(k)} poly(n)$. Finally, we propose a purely
classical algorithm that can simulate a PBC on n qubits in a time $2^{c n}
poly(n)$ where $c\approx 0.94$. This improves upon the brute-force simulation
method which takes time $2^n poly(n)$. Our algorithm exploits the fact that
n-fold tensor products of magic states admit a low-rank decomposition into
n-qubit stabilizer states.
