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.

Classical computers essentially evaluate functions: given n-bits of input they produce m-bits of output that are uniquely determined by the input; that is, they find the value of f\colon \{0,1\}^n \to \{0,1\}^m for a particular specified n-bit argument. A function with an m-bit value is equivalent to m Boolean functions, each with a one-bit value, so we may 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?