Computational speedups using small quantum devices
This addresses the challenge of leveraging early-stage quantum hardware for practical computational gains, which is incremental in advancing quantum computing applications.
The paper tackles the problem of whether small quantum computers with limited qubits can genuinely speed up algorithms for large-scale problems, specifically demonstrating a hybrid quantum-classical algorithm that significantly speeds up solving 3SAT problems with many variables compared to fully classical methods.
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.