Chapter 10 Quantum algorithms

Overview

About quantum interference in disguise: Hadamard, function evaluation, Hadamard. Also about the early quantum algorithms and how they deal with querying oracles, searching for a needle in a haystack, and estimating periodicity of certain functions. Finally, about phase estimation, hidden order determination, and Shor’s famous algorithm for prime factorisation, via the (inverse) quantum Fourier transform.

To boil down the theory of classical computers to a single sentence, we can say that they essentially evaluate functions: given $n$-bits of input, they produce $m$-bits of output that are uniquely determined by the input. In other words, (very simple) classical computers encode binary functions $$f\colon \{0,1\}^n \to \{0,1\}^m$$ and then compute the value of the output for any particular specified $n$-bit argument. But we can make an even further simplification: a binary function with an $m$-bit output value is equivalent to $m$-many binary functions with $1$-bit output values (which we call Boolean functions). In other words, we might just as well say that the basic task performed by a computer is the evaluation of Boolean functions $$f\colon \{0,1\}^n \to \{0,1\}.$$ How can we adapt this to the world of quantum computing?