Compared to the extremely slow trial division algorithm (~2^(n/2) for an n bit number), it’s true that Grover’s algorithm (and perhaps this adiabatic algorithm)

Compared to the extremely slow trial division algorithm (~2^(n/2) for an n bit number), it’s true that Grover’s algorithm (and perhaps this adiabatic algorithm) gives a significant speedup (~2^(n/4))—but that’s useless, because the best known classical factoring algorithms are already much faster than that (~5.5^∛n), and Shor’s quantum algorithm would be much, much faster still (~n²). (Note that, strictly speaking, the best classical algorithms are already sub-exponential, i.e., faster than C^n for all C, so there’s no such thing as an “exponential speedup”.) Quotes from Scott Aaronson about the adiabatic factorization of 143: “It doesn’t ‘know’ about the special mathematical properties of factoring that make that an easy problem for quantum computers. In contrast to Shor’s algorithm, we have no reason to think it would be able to factor 10,000 digit numbers in less than astronomical amounts of time.… I didn’t see any evidence that quantum behaviour played a role in finding the factors of 143.” https://www.newscientist.com/article/dn21699-controversial-quantum-computer-beats-factoring-record/ https://www.newscientist.com/article/dn21699-controversial-q...