{
"cells": [
{
"cell_type": "markdown",
"id": "ac096ad9",
"metadata": {},
"source": [
"# Computer science: P/NP space & quantum computing"
]
},
{
"cell_type": "markdown",
"id": "5c3c26ab",
"metadata": {},
"source": [
"Author: Alexandra Semposki\n",
"\n",
"Maintainer: Alexandra Semposki"
]
},
{
"cell_type": "markdown",
"id": "df1a9aa6",
"metadata": {},
"source": [
"## Introduction to computer science"
]
},
{
"cell_type": "markdown",
"id": "106df284",
"metadata": {},
"source": [
"### Quantum Algorithms\n",
"\n",
"#### Shor's Algorithm\n",
"\n",
"#### Grover's Search Algorithm\n",
"\n",
"#### Deutsch-Josza Algorithm"
]
},
{
"cell_type": "markdown",
"id": "e1c67425",
"metadata": {},
"source": [
"## Computational complexity theory\n",
"\n",
"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](https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/)."
]
},
{
"cell_type": "markdown",
"id": "dfc86357",
"metadata": {},
"source": [
"### P vs. NP\n",
"\n",
"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. \n",
"\n",
"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].\n",
"\n",
"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]. \n",
"\n",
"```{admonition} Polynomial Time\n",
"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. \n",
"```\n",
"\n",
"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__."
]
},
{
"cell_type": "markdown",
"id": "885d0a1c",
"metadata": {},
"source": [
"### BQP\n",
"\n",
"__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].\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"id": "4e6c1682",
"metadata": {},
"source": [
"### BPP\n",
"\n",
"__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. \n",
"\n",
"Scientists are still working out whether __BPP__ is equal to __P__, but have not come to a definitive conclusion yet [2]. "
]
},
{
"cell_type": "markdown",
"id": "8036e0ae",
"metadata": {},
"source": [
"### Bonus: PSPACE\n",
"\n",
"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]. "
]
},
{
"cell_type": "markdown",
"id": "056c66b9",
"metadata": {},
"source": [
"## Looking ahead: approaching computational problems with quantum computers\n",
"\n",
"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. \n",
"\n",
"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. "
]
},
{
"cell_type": "markdown",
"id": "13beeb28",
"metadata": {},
"source": [
"## References\n",
"\n",
"[1] Nielsen, M. A., & Chuang, I. L. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.\n",
"\n",
"[2] Hartnett, Kevin. “A Short Guide to Hard Problems.” Quanta Magazine, 16 July 2018, linked [here](www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/)."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.11"
}
},
"nbformat": 4,
"nbformat_minor": 5
}