Chapter 10 Quantum algorithms

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.

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?