Prerequisites

Administrative

Technical

Linear Algebra

A solid understanding of linear algebra is a must. See 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

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 [Graham et al., 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.

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)\).

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 machines.

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

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.

Fig. 1 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.