(sec:Prerequisites)= # Prerequisites (sec:administration)= ## Administrative (sec:technical-prerequisites)= ## Technical ## Linear Algebra A solid understanding of linear algebra is a must. See {ref}`sec:linear-algebra` for details. ## Computer Science A few concepts from computer science are needed, especially in order to compare and contrast the behaviour of quantum and classical algorithms. ### Concrete Mathematics :::{margin} These particular results are the simplest case of [Faulhaber's formula]. ::: You should be able to perform simple series (sums) like the following: \begin{gather*} \sum_{i=1}^{n} i = \frac{n(n+1)}{2}, \qquad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}. \end{gather*} The definitive reference on material like this is {cite:p}`Graham:1994`. While this book is much more in-depth than we need, it is the place to go if you ever find yourself needing an analytic solution to a complex sum, or solution to finite-difference equations. :::{margin} We will primarily use this "big-O" notation, but there are other useful comparisons (see the [Family of Bachmann–Landau notations]) for specifying that $T(n)$ grows no **slower** than $g(n)$ -- $T(n) = \Omega\bigl(g(n)\bigr)$ -- or that $T(n)$ behaves the same asymptotically as $g(n)$ -- $T(n) = \Theta\bigl(g(n)\bigr)$, or equivalently, $T(n) = O\bigl(g(n)\bigr)$ and $T(n) = \Omega\bigl(g(n)\bigr)$. ::: ### Asymptotic Notation Time or space (memory) complexity is expressed in terms of [asymptotic notation]. Specifically, suppose that an algorithm takes $T(n)$ steps to solve a problem characterized by size $n$ (e.g. consider performing an unstructured search of $n$ elements.) We say the following: \begin{gather*} T(n) = O\bigl(g(n)\bigr) \end{gather*} iff (if and only if) there exists a positive real number $M$ and a real number $n_0$ such that \begin{gather*} \abs{T(n)} \leq M g(n) \text{ for all } n \geq n_0. \end{gather*} In other words, for large values of $n$, the number of steps $T(n)$ grows no faster than $g(n)$. ::::{admonition} Example: Searching Consider the problem of unstructured searching: finding a specific object from a bag of $n$ objects where there is no other information (such as ordering) about the objects. Classically, one must inspect each object until the desired object is found. In the worst case, this will take $T_{\mathrm{worst}}(n) = n$ steps. In the best case, we might find the object on the first try $T(n) = 1$, but if the objects are randomly distributed, this will only happen with probability $1/n$. Generalizing, the probability of finding the object on the $i$th try ($T(n) = i$) is also $1/n$. Thus, on average, it will take: \begin{gather*} T_{\mathrm{avg}}(n) = \sum_{i=1}^{n} \frac{i}{n} = \frac{n(n+1)}{2n} = \frac{n+1}{2}. \end{gather*} Thus, both $T_{\mathrm{worst}}(n) = O(n)$ (with the coefficient $M \geq 1$ in the previous definition) and $T_{\mathrm{avg}}(n) = O(n)$. Surprisingly, quantum computers can find the object in order $O(\sqrt{n})$ time using Grover's algorithm, providing a provable asymptotic speedup. :::: ### Universal Computation and Turing Machines Classical computation is universal in the sense that all classical computers can be reduced to a generalized [Turing machine]. This allows one to classify computational problems in terms of characteristics of [Turing machine]s. ### Complexity Theory Classical computational problems are characterized by their [computational complexity], which formally describe their computational difficulty. There is a veritable [Complexity Zoo] with over 540 different complexity classes, but for the purposes of this course, you should be familiar with the three most famous classes: #### P: Polynomial-Time Roughly, a decision problem is said to be in the complexity class [P] if it is solvable in polynomial time by a **deterministic** [Turing machine]. I.e. if $T(n) = O(n^p)$ for some finite power $p$. #### NP: Nondeterministic Polynomial-Time A decision problem is said to be in the complexity class [NP] if is solvable in polynomial time by a **non-deterministic** [Turing machine]. It turns out that this is equivalent to being able to **check** if a potential solution is indeed the solution in polynomial time on a **deterministic** [Turing machine]. It is known that P⊆NP, but the most famous outstanding problem in computer science is whether or not P=NP. I.e.: is there a problem in NP that is not in P? #### NP-Complete ::::{margin} I do not recommend this as a retirement strategy! Most mathematicians and computer scientists believe that P≠NP, but a proof has remained outstanding since the problem was formulated in 1971. :::{figure} https://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg Possible relationships between P, NP, NP-hard, and NP-Complete, depending on the resolution of the P vs NP problem. ::: :::: A further subclass of NP are those problems in NP that are as hard as any other problem in NP. If you find a polynomial time solution to any NP-hard problem, then you can prove that P = NP = NP-Complete and you can claim your [million dollar prize](https://claymath.org/millennium-problems/p-vs-np-problem). [P]: [Turing machine]: [Complexity Zoo]: [Church-Turing thesis]: [computational complexity]: [Grover's algorithm]: [Family of Bachmann–Landau notations]: [asymptotic notation]: [Faulhaber's formula]: