5.1 Talking to oracles

In this quest, we will look at several quantum algorithms and see how they compare to classical algorithms that solve the same problem. Since it is generally very hard to understand how many elementary operations are required to solve a certain computational problem, in this quest we will look at a simpler measure of algorithm complexity (this is also what computer scientists do when they want to make their life a bit simpler).

When a computer is running a program, it has to perform several different types of operations. The slowest type of operations are those that need to access data. For example, when reading it from the memory, hard drive or – in the worst case – another computer accessible over the internet. Once the relevant piece of data has been read, processing it can be relatively quick. Because of this, we can get a rough idea for how long a certain algorithm will run if we only count those instructions that access data.

You might be familiar with this when opening a complicated web page or a large document. It can take a while for it to load, but once it has loaded, interacting with the web page or scrolling around the document and inserting another line is usually quite quick.

Another way to think about this, which we will use in this quest, is that the information you are trying to access is actually produced by another algorithm or a subroutine within your algorithm. Moreover, this subroutine is very slow. For example, it might be reading the information from the hard disk or accessing it through the internet. Or it might not even have the answer readily available and instead have to produce it from scratch by performing some very complicated calculation. Either way, this subroutine always takes a very long time to come up with the answer, so you want to call it as few times as possible. We call such subroutine an oracle since it is very wise and knows all the answers, but also a bit slow and hence needs to think for a while to deliver the answer.

More formally, a classical oracle is just a function $f\colon\{0,1\}^{n}\to\{0,1\}$ where $\{0,1\}^{n}$ denotes the set of all $n$-bit binary strings. You can think of the input $x\in\{0,1\}^{n}$ to this function as a question and the output, the bit $f(x)$, as the answer. Every time you evaluate the function $f$ on some input, you are asking a question that corresponds to that input, and you get a yes/no answer that corresponds to the value of the function.

For example, you can model the access to a hard drive or memory using an oracle. Say, if you have 4 bits of memory, you can model them as a function $f:\{0,1\}^{2}\to\{0,1\}$ that, given a binary address, returns the corresponding bit. For example, if you want to find out all four bits, you would need to evaluate $f$ four times to get the four values $f(00),f(01),f(10),f(11)$.

What is important to note is that in our setup the kinds of computational problems we are interested to solve are not about finding the value of $f$ on a specific input. Indeed, such problems are trivial since they can be solved by consulting the oracle just once, because this is precisely what the oracle does – it tells you the value of the function on any input of your choice. Hence, the kinds of problems we are interested are more subtle. What we want is to determine some property of the function $f$ by evaluating it as few times as possible.

For example, let’s say we wanted to know whether $f(x)=0$ for all $x\in\{0,1\}^{n}$. In this case, what we could do is to ask the oracle about random values of $x$ until we find one such that $f(x)=1$. We will soon see other examples of such problems.