Quantum Speedup Found for Class of Hard Problems

They're not easily comparable since quantum complexity refers to the upper bound on queries to some black-box "quantum oracle", which exists on the gate-level. A classical parallel would perhaps be queries to a translation lookaside buffer, which can be regarded as a gate-level black-box (I'm sure people who actually work in hardware already smell blood!).

By contrast, classical complexity, as in sorting algorithms, is reasoned about in higher-level programming languages, whose operational complexity is hard to describe down to the bit-level.

I'm curious if anyone more knowledgeable could argue one-way-or-another if this is a boon to the quantum-computers-will-probably-be-faster-in-realization camp.

If I’m reading it right:

    dqi = O(m^2)
    classical = O(2^n)

    m = variables
    n = constraints

The issue is that, apart from the Shor’s algorithm, it is hard to find a quantum algorithm, substantially faster than a classical one.

Moreover, since cost of qubits scale exponentially, a slight reduction in the power of a polynomial-time algorithm is not enough to offer a practical benefit.

I think the goal here is to find more useful algorithms that benefit from quantum computing. Being able to factor primes efficiently is only useful for the sake of the cryptographers' job security :-)

Are you talking about the skepticism from Kalai or more general skepticism (from wider group people, which is more about its application to optimization problem, not prime factoring)?

I’m exaggerating a lot here, but one concern people have with quantum computing is what if it breaks all cryptography, but doesn’t help us solve “useful” problems.

The what if is pulling a lot of weight here but I hope it makes my point.