Computer science: P/NP space & quantum computing#
Author: Alexandra Semposki
Maintainer: Alexandra Semposki
Introduction to computer science#
Quantum Algorithms#
Shor’s Algorithm#
Grover’s Search Algorithm#
Deutsch-Josza Algorithm#
Computational complexity theory#
This theory describes the classification of different types of problems based on similarities in the resources required to solve them. There are many broad classes of problems, including, e.g., P, NP, BQP, and BPP, and within these there can be more distinct subclasses. We’ll focus on understanding the four mentioned above, and how they relate to the discussion of quantum computers. For an excellent hierarchical guide to complexity classes, check out this article.
P vs. NP#
The two most well-known complexity classes are P and NP. P encompasses all problems that can be solved on a classical computer in an efficient and speedy way, and NP in turn possesses all of the problems that have checkable solutions on a classical computer. The main difference, if you didn’t catch it in the last sentence, is that NP problems may not be quickly solvable on a classical computer. For example, factoring prime numbers cannot easily be done on a classical computer, but checking the solution to this problem—with the solution already in hand—is definitely possible [1]. This is a somewhat subtle difference, but a very crucial one to understanding these classes.
If you’ve been around computer science for any decent length of time, you’ll have heard about “P/NP” before. One of the most intriguing computer science problems out there is whether or not P = NP (this problem is also one of the seven millenium prize problems). This has not yet been proven. There are problems that could help with this, such as NP-complete class problems (a subclass within NP), where their solutions could be adapted for any other NP problem. This would essentially prove that the two classes of problems are equal, as once one can solve NP problems, one has proved they are indeed solvable in a deterministic amount of time and therefore would apply to the P class as well. However, if P\(\neq\)NP, then the opposite is true [1].
The last class to mention here is the NP-hard class. These are problems that are quite similar to NP-complete ones, and in fact some overlap with the NP-complete subclass. One good example of this is the ‘’travelling salesman’’ optimization problem, which has no known solution that could be found within what we call ‘’polynomial time’’ without the use of non-deterministic machines, and also belongs to the class of problems that would solve any other NP problem if solved themselves. However, NP-hard problems do not have to overlap with other NP problems in general [2].
Polynomial Time
Polynomial time is a time classification that refers to the ability to solve a problem within a polynomial scaling of steps (some examples include \(n\) and \(n^{2}\)). This can more easily be understood when contrasted with ‘’exponential time’’ (EXPTIME), where a problem’s number of steps scales exponentially as it is solved. A good example of a problem in EXPTIME is chess—if one scales up the board to a very large number of rows and columns, it is not possible to either solve \textit{or} check if a given solution is the optimal one within polynomial time.
These are all rather abstract concepts to grasp, but we’re getting there! Let’s look now at a couple of more specific classes, BQP and BPP.
BQP#
BQP, or ‘’Bounded-Error Quantum Polynomial Time’’, is the complexity class to which all problems belong that can be solved using quantum computation. This class overlaps quite a bit with P and NP, since we know that all problems in P can also be solved by a quantum computer efficiently. However, there is still some mystery around whether or not BQP fully contains NP [2]. However, this is most likely not true since so far there seem to be problems in NP that do not fit into the BQP class [2].
What does ‘’Bounded-Error’’ mean here? This means that the quantum computer’s maximum error is allowed to be up to some bound; here, for BQP, that bound is stated as 1/3.
BPP#
BPP stands for ‘’Bounded-Error Probabilistic Polynomial Time’’, and this class refers to the subset of problems that can be solved quickly (in polynomial time) that have some probabilistic element—aka, randomness [2]. Obviously, this complexity class contains P. Again, since this is ‘’Bounded-Error’’, there is a tolerance for how far the answer to a given problem can differ from each subsequent solution. For example, when you run a Monte Carlo algorithm, you know that you will not get back the exact same results every time since there is a probabilistic element to the code. However, you know that you can get within a certain tolerance and be confident that your code is still solving the problem correctly. BPP works somewhat like this.
Scientists are still working out whether BPP is equal to P, but have not come to a definitive conclusion yet [2].
Bonus: PSPACE#
Since we’ve covered most of the complexity classes, here’s another one you may run across—PSPACE. This class is a lot like P, but instead of being parameterized by the amount of time it takes to solve the problem, PSPACE contains the problems that are solvable with a polynomial amount of memory. This could mean that the problem is not solvable with respect to time in polynomial time, but can be solved with a reasonable finite amount of storage space. Because of this rule, NP and P are both contained within PSPACE [2].
Looking ahead: approaching computational problems with quantum computers#
So, why all of the fuss over quantum computers? Why are we so excited about them if they cannot solve NP-complete problems? Well, first of all, there is no guarantee that any computer we are able to build, either classical, quantum, or whatever else we may think up, will ever be able to solve those types of problems.
However, we just looked at one algorithm that illustrates the power of quantum computers: Shor’s algorithm. If we can find more algorithms that allow us to exploit the power of quantum computers and their ability to store and manipulate more data than classical computers can, we may still make far greater strides than we could ever do using only their classical cousins. Quantum computing is still very much a frontier field, full of uncertainties and surprises.
References#
[1] Nielsen, M. A., & Chuang, I. L. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.
[2] Hartnett, Kevin. “A Short Guide to Hard Problems.” Quanta Magazine, 16 July 2018, linked here.