2.1 Complexity of Computational Problems
In this and the following chapters, we will often speak about computational problems that are hard for classical computers but can be solved efficiently using quantum algorithms and hardware. How can we quantify the hardness of a computational problem? One way to answer this is to analyse problems from the computational resource perspective: how much time and memory are needed to solve them? This leads to the concept of complexity classes. Important examples are as follows:
- The class P (polynomial) is the set of decision problems solvable by a deterministic Turing machine in polynomial time.
- The class NP (non-deterministic polynomial) is the set of decision problems solvable by a non-deterministic Turing machine in polynomial time.
These definitions, in turn, require us to specify the following objects:
- A decision problem is a computational problem that can be posed as a Yes-No question of the input values.
- Polynomial time means that the running...
