5.2 Quantum algorithms
In this section we will see several quantum algorithms that can solve a computational problem much faster than any classical algorithm. Such speedups are very surprising because quantum mechanics at first glance does not appear to have anything to do with computation. Nevertheless, quantum-mechanical phenomena such as interference can enable very impressive computational speedups. As already explained earlier, we are working in a computational setting where we count only the number of questions. That is, assuming the ability to evaluate some function on any input, on how many inputs do you need to evaluate it to determine some property of . Equivalently, having access to an oracle that can evaluate , how many times do you need to use this oracle to determine some property of .