ABSTRACT
In the last chapter, we introduced the circuit model for quantum computation, where a computation is essentially the evaluation of a function. In the binary system of computation a function is a map f : {0, 1}n 7→ {0, 1}m. The function takes an n-bit input and produces an m-bit output. However, this can be regarded as m functions fi : {0, 1}n 7→ {0, 1}, that take an n-bit input and give a one-bit output, each of which is one bit of f(x). We can thus restrict our attention to n→ 1 functions alone, in other words, we can reduce our problem to questions with yes/no answers, a so-called binary decision problem.
