  Suppose we have a small quantum computer with only M qubits. Can such a
device genuinely speed up certain algorithms, even when the problem size is
much larger than M? Here we answer this question to the affirmative. We present
a hybrid quantum-classical algorithm to solve 3SAT problems involving n>>M
variables that significantly speeds up its fully classical counterpart. This
question may be relevant in view of the current quest to build small quantum
computers.
