Computational complexity studies the resources (mostly, time and space) required to solve a problem on a computer. It classifies problems based on how difficult they are to solve for different types of computers, such as a classical computer or a [quantum computer]. Most classes are about decision problems, that is, yes-no questions (e.g. “Is this number prime?” or “Are there any subsets in this list of numbers that add up to zero?”). Some classes are about counting problems, which instead count the number of “yes” answers (e.g. “How many subsets in this list of numbers add up to zero?”).
Main classical complexity classes
- P: Decision problems solvable in polynomial time by a classical computer.
- NP: Decision problems whose solutions can be verified in polynomial time by a classical computer.
- PSPACE: Decision problems solvable with polynomial space by a classical computer.
- EXPTIME: Decision problems solvable in exponential time by a classical computer.
These classes are listed in increasing order of inclusion: all problems in P are also in NP, all problems in NP are in PSPACE… It is widely believed, but not proved, that NP is strictly bigger than P, i.e., that for some problems, we can easily check that a solution is correct, but that the solutions can’t be computed efficiently (meaning, in polynomial time). Integer factorization is one such example: given an integer, we don’t know how to efficiently decide if it can be decomposed into product of smaller numbers, but given two numbers, it is easy to multiply them to verify if their product gives the right number.
Main quantum complexity classes
- BQP: Decision problems solvable in polynomial time by a quantum computer with bounded error.
- QMA: Decision problems whose solutions can be efficiently verified by a quantum computer. It’s the quantum analog of NP.
Frequently asked questions about computational complexity
- How are classical and quantum complexity classes related? It’s widely believed that BQP is strictly bigger than P, as exemplified by Integer factorization: using Shor’s algorithm, a quantum computer can find a solution in polynomial time, but we don’t know how to do that with a classical computer.
- What’s #P? #P is the class of counting problems associated to decision problems in NP, so #P problems are harder to solve than NP problems. An example of a #P problem is the computation of the permanent of a matrix, which is a polynomial is the entries of the matrix.
- How is #P related to photonic quantum computing? When photons are sent through a linear-optical interferometer to perform [Boson sampling], the probability of detecting the photons in a specific configuration is related to the permanent of a matrix. Because this is difficult to compute classically, but easy to perform with a photonic quantum processing unit, it’s a good way to show a quantum computational advantage.
- Does NP mean non-polynomial? No, NP means non-deterministic polynomial. This name comes from the fact that NP problems can be solved in polynomial time by a non-deterministic computing machine.