← Back to papers
Computational speedups using small quantum devices
V. Dunjko, V. Dunjko, Y. Ge, J. Cirac·July 24, 2018·DOI: 10.1103/PhysRevLett.121.250501
MedicineComputer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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≫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.