Assessing fault-tolerant quantum advantage for $k$-SAT with structure

Martijn Brehm, Jordi Weggemans

For many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overloo…