Lecture 11. Simple quantum algorithms using oracles

In this lecture, we discussed the black-box model of computation and some simple algorithms that give an advantage in oracle computations. Usually, one distinguishes two kinds of quantum black boxes for describing the action of a Boolean function – $\mathrm{XOR}$-oracles and phase oracles. These two kinds of oracles are equivalent, but their application appears to be useful in different situations. For example, using the phase oracle, it is convenient to study the properties of the Fourier spectrum of a Boolean function: with the help of Walsh-Hadamard transforms and the phase oracle, one can sample from the spectral measure of a Boolean function. Because of this, some problems in the theory of Boolean functions are efficiently solved. For instance, if the function $f$ is a linear Boolean function, then, according to the Bernstein-Vazirani algorithm, we can find out its form in one oracle call; according to the Deutsch-Jozsa algorithm, we can decide whether the Boolean function is constant or balanced in one oracle call. Solving these problems using classical oracles requires a larger number of queries. Given a function $f$ for which $f(x) = f(y)$ if and only if $y = x\oplus s$, Simon's algorithm can find the hidden shift of $s$ in $\mathcal{O}(n)$ oracle calls, while the classical algorithm requires $\mathcal{O}(\sqrt{2^n})$ queries. Simon's algorithm can be significantly generalised to solve hidden subgroup problems for any finite abelian groups.