I'd like to take the opportunity to clear a misunderstanding that I've seen in several threads related to quantum computing.

—————————————————————————————————————————————————————————

The classes of complexity of interest here are P, NP, BPP, and BQP.

— P corresponds to the problems that can be solved by a classical computer (deterministic Turing machine) in polynomial time. For example finding a shortest path between nodes in a graph is in this complexity class.

— NP corresponds to the problems where “verifying a solution” is in P. In other words, it's “easy” to check if a solution is actually valid. We know that P ⊆ NP which means that when it's easy to find a solution, it's also easy to check that a solution is valid (but we don't know if the opposite is true). This class contains interesting problems such as prime factorization on which all the current Web's security depends. It's easy to check if a factorization is valid, but it's hypothesized that it's hard to actually find it. Now the interesting part is that we're not sure it's actually true, so the security house of cards might actually tumble at some point (if it hasn't already secretly).

— BPP contains all the problems that you can solve in polynomial time (so like P) but with a chance of less than 1/3 of being incorrect! In practice, we run the algorithm several times to reduce the probability of being wrong to less than 2^(−ck) (c is a positive constant, k is the number of times it's run).

— BQP is probably the most interesting class here. It's just like BPP but on a quantum computer. Now the interesting part is that we don't know (yet) an efficient way of finding the prime factorization on a classical computer. But on a quantum computer, we have the infamous Shor's algorithm which can solve this problem in polynomial time with a bounded error!

—————————————————————————————————————————————————————————

The current knowledge about complexity classes is that P ⊆ BPP ⊆ BQP. We don't know how NP and BQP relate to each other.

What does this mean? We don't know if quantum computers can solve harder problems theoretically. But they seem to do sometimes in practice to the best of our knowledge. Coming back to the Shor's algorithm example, we don't know any classical algorithm that can solve the prime factorization problem as efficiently. But this doesn't mean that such an algorithm doesn't exist!

Now you might think that all of this is only theoretical considerations that only mathematicians care about. After all, we don't care if theoretically there might exist efficient classical algorithms for supposedly hard problems if we don't find them anyway right? This is a valid observation. If big enough quantum computers become a reality one day, we'll be able to solve some hard problems right away. However in the meantime, we might totally find efficient classical algorithms making quantum computers less useful. Actually, it has already happened last year[1]! A recommendation problem that we thought was intractable by classical means (but easy to solve with quantum computers) turned out to be solvable more easily than expected by a classical computer. This classical algorithm draws inspiration from quantum algorithms however. So if anything, quantum computing will force us to look at problems from another perspective and solve them in novel ways.

[1] https://arxiv.org/abs/1807.04271