> we caveat the speedup result we find by noting that [...] the oracle we construct in this work can be efficiently simulated by a classical computer.

T_T

You could replace the quantum chip with a classical signal processor decoding the gates to perform, feeding them to a Clifford simulator, and it would solve the problem just fine. They're just arbitrarily declaring that the classical computer isn't allowed to do the thing that solves the problem fast, because that would "violate the black box condition", despite the fact that their quantum compilation and error mitigation pipeline also has to violate the black box condition.

As with many quantum papers, you should ignore the headline and just focus on how large the circuits are:

> Our current implementation of Simon’s problem requires roughly 400 two-qubit gates (after compilation) and 60 qubits

So a few hundred gates. A few times smaller than random circuit sampling experiments from 2019, though much cheaper to verify and simulate.

whether they claim to possess a high fidelity magic state is also relevant.