Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Finding the limits of what quantum computers can solve better than classical ones
Researchers proved that for a broad class of optimization problems, even quantum computers face fundamental speed limits when trying to beat classical algorithms. On problems where each variable connects to at most D constraints, any quantum advantage shrinks to just a constant improvement — the hard part (improving by roughly 1/√D) remains equally hard for both quantum and classical machines.
Quantum computing advocates have hoped quantum machines could dramatically outperform classical ones on certain optimization problems. This work draws a precise line: quantum advantage exists only in small constant factors, not in the scaling that matters for large, practical problems. For researchers building quantum algorithms, it means effort should focus on optimizing these constant improvements rather than chasing exponential speedups that the mathematics now shows are unreachable.