Computational Speedups Using Small Quantum Devices

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 3-satisfiability problems involving $n\gg 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.