How would I implement the quantum oracle in Deutsch's algorithm?

Question

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Jozsa algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.

Answer 1

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in.

Implementation

Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. You can select the oracle at random, if you want. Here it is, implemented in Q#:

operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
    body
    {
        mutable inputResult = Zero;
        mutable outputResult = Zero;

        // Allocate two qbits
        using (qbits = Qubit[2])
        {
            // Label qbits as inputs and outputs
            let input = qbits[0];
            let output = qbits[1];

            // Pre-processing
            X(input);
            X(output);
            H(input);
            H(output);

            // Send qbits into black box
            blackBox(input, output);

            // Post-processing
            H(input);
            H(output);

            // Measure both qbits
            set inputResult = M(input);
            set outputResult = M(output);

            // Clear qbits before release
            ResetAll(qbits);
        }

        // If input qbit is 1, then black box is constant; if 0, is variable
        return One == inputResult;
    }
}

What's the point?

(a) Query complexity

Computational complexity is a field concerned with classifying algorithms according to the quantity of resources they consume as a function of input size. These resources include time (measured in steps/instructions), memory, and also something called query complexity. Query complexity is concerned with the number of times an algorithm has to query a black-box oracle function.

The Deutsch oracle problem is interesting to complexity theorists because the quantum algorithm only has to query the black box once, but the classical algorithm has to query it twice. With the generalized Deutsch-Jozsa problem where an $n$-bit oracle contains a function which is either constant or balanced, the quantum algorithm again only has to query it once but the (deterministic) classical algorithm requires $2^{n-1}$ queries.

It should be noted that a probabilistic classical algorithm exists which solves the Deutsch-Jozsa problem in much fewer than $2^{n-1}$ queries by randomly sampling oracle inputs: if the oracle continues to output the same value no matter the input, the probability that the oracle is constant grows very quickly. This means Deutsch-Jozsa is not a good candidate for a quantum supremacy/advantage problem, which leads into...

(b) Applications in the real world

If you aren't a complexity theorist, you might reasonably not care very much about query complexity and instead want to know why the Deutsch oracle problem is important in a "no rules" world where you're allowed to look inside the black box. Trying to analyze an oracle problem as a non-oracle problem is fraught with difficulty, and I don't believe anybody has solved the question of the best classical algorithm for the Deutsch oracle problem when you are allowed to analyze the oracle circuit. You might think - what is there to analyze? There are only four possible circuits! In fact, it is much more complicated.

If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:

Identity: $C_{1,0}$

Negation: $X_0C_{1,0}$

Constant-0: $\mathbb{I}_4$

Constant-1: $X_0$

However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:

$$H_0Z_0H_0\,.$$

It turns out that, for any input, you could ever give:

$$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle\,.$$

This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $X_0$:

$$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0\,.$$

So we have:

$$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle\,.$$

So you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) into your quantum Deutsch Oracle algorithm instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are. So an algorithm which "cheats" and looks inside the black box doesn't have quite as simple a time as you might think. Consider the case of I, a stranger on the internet, giving you a very complicated circuit guaranteed to be constant or variable then asking you which it is. Not something so easily solved by just looking at it!

(c) Important for historical & pedagogical reasons

Primarily, the Deutsch Oracle problem is important for historical and pedagogical reasons. It's the first algorithm taught to students because it's the simplest, and seems to demonstrate quantum speedup as long as you don't ask too many questions. It also serves as a good launching point for learning Simon's Periodicity Problem and then Shor's Algorithm.

Answer 2

There is no way to build the oracle in a way which would not defeat the point of Deutsch's algorithm - that's why it is an oracle-based algorithm.

The only way would be if you would come up with an incredibly hard to compute function (this is, an incredibly long circuit) which would take one input bit $x$ and give one output bit $f(x)$ (but on the way could use as many ancillas as you want), and where for some reason you would only be interested whether $f(0)=f(1)$. Then, you could use Deutsch's algorithm to save half the time (since you have to run this circuit only once).

Now, this sounds pretty contrived, and it is. On the other hand, it sounds equally contrived that there might be function $f(x)$ where $1 \leq x \leq N$ and $f(x)$ integer, and you would like to find some $y$ such that $f(x+y)=f(x)$, without the need to learn $f(x)$ itself - yet, it turns out this is exactly what is required for factoring.

So the point is that oracle-based algorithms prove that you can get a speed-up if you have a problem with that structure (i.e. where you only want to learn some specific property of a function), but it doesn't tell you if such a problem exists.

So if you want to implement Deutsch, any way of doing the oracle is fine - it is a "proof-of-principle" algorithm and does not yield an actual speed-up on a real problem (at least none we know of).

Answer 3

I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.

The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.

Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.

Answer 4

I think that ahelwer's answer touches on some the ways that we think about the complexity of algorithms. However — given that we don't literally have "oracles" in the real world which we wish to query, you might wonder why we would worry about query complexity, or the idea of oracles at all. I will try to give some perspective on this, and in particular to describe how you might try to think of ways to construct a "Deutsch–Jozsa oracle" in a way that you don't feel as though you're cheating.

(As Norbert Schuch points out, for the Deutsch problem which is the elementary case of Deutsch–Jozsa, there's not much scope for insights, but I expect that your question about oracles applies more generally as well. That's what I'll speak to here.)

An intuition about oracles

The concept of an oracle is a way to allow ourselves to simplify how we talk about computational problems.

The original application of the concept of an oracle was to consider hypothetically what we could do if we could solve difficult problems, even impossible problems, without committing to how we could do it even in principle. But in computational complexity these days — particularly in quantum computation, e.g. in the cases of Deutsch–Jozsa, Bernstein–Vazirani, and other oracle problems — the situation is different: the oracle describes a function which is the basis of the problem. The fact that it is 'an oracle' is a way to structure how we describe the function which is at the centre of the problem: not that we must never contemplate how the function is computed, but that this information is simply not provided as part of the problem, and that we are not concerned with the time or other complexity associated with that function.

When we take this approach, we can actually obtain answers which are related to very difficult questions in computation. For instance, you may know that we do not know how to prove either P ≠ NP or P = NP, but that we can show that there are oracles A such that we can show that P^A ≠ NP^A. What the oracle A does here is not help a computer (more precisely, a deterministic Turing machine or a nondeterministic Turing machine) to solve a problem — it represents the problem which the computer must solve. The fact that we can show in some instances that P^A ≠ NP^A, doesn't mean that P is really different from NP: it just means that just using nondeterminism is really a significant resource for a model of computation to have — it allows you to solve some problems efficiently, and there is no way generically to simulate nondeterminism efficiently on a deterministic computer. So if you want to solve the problem related to what A computes, you absolutely would require some information about the structure of any function which could efficiently compute A.

This is one of the main things that oracles are about: they allow you to talk about ways that models of computation can or cannot solve problems, when you are provided with limited information about the problem.

Using oracle algorithms to solve non-oracle problems

The Deutsch–Jozsa algorithm, or the Bernstein–Vazirani algorithm, are in principles not algorithms which one performs for their own sake. (Well, not really — see the next Section.) They stand for ways that you can solve a problem. What problems do they solve? They allow you to discover certain features of a function you're interested in — whether it is constant/balanced, or what vector is associated in some scalar-valued linear function on vectors.

What functions do you perform them on? — You perform them on any function for which you are interested in the answer.

The description of these as oracle-based algorithms is beside the point. The oracle problems basically allow you to know that, with an ideal quantum computer, you can solve the problem even if you know extremely little about the function, provided that you can actually evaluate the function efficiently in practise. To actually evaluate such a function, of course you will need some description of how to do so, and so you have more information than in the oracle setting; but that doesn't prevent you from using the same algorithm.

What happens when you have more information than in the oracle setting, is that suddenly there are other ways that you might be able to solve the problem. Specifically, it might become possible to solve the problem efficiently classically. (This is the same observation as with P^A ≠ NP^A: it proves that there are problems which are in NP, which any efficient deterministic algorithm would at least require actual structural information to be able to solve — so that when you provide a description of an efficiently computable function rather than an 'oracle', it is possible that the problem will be in P.) It means that the quantum algorithm might not have the same advantage over classical algorithms at solving the particular problem you present — and in fact it may be that the classical approach is better (particularly with the devices we have at the moment).

In the end, just because you have a quantum algorithm to solve something, doesn't mean that it is necessarily the best way to solve something. This is certainly true of the Deutsch–Jozsa algorithm: even in the oracle setting, using randomness is nearly just as good, and it's much better given that we don't have large reliable quantum computers yet! But then again...

"Implementing" an oracle

The purpose of implementing the Deutsch–Jozsa algorithm is the same as implementing "Hello, World!" — not to solve a pressing unsolved problem, but to practise using a tool which you expect will be useful for doing other things.

To practise coding, you should feel absolutely relaxed and comfortable with the idea of implementing an oracle, and with the idea of the computer evaluating the oracle. In principle, this is the point of what you want to do. Even if you are using a classical emulator, in which the classical computer is actually evaluating all branches of the superposition and so explicitly finding the answer to a problem in order to pretend that it is a quantum computer acting in a slightly more roundabout way, so be it — you are practicing how to use a tool which may be useful for other things, and which one day won't be run on a classical computer.

So how should you go about implementing your oracle?

(i) If you are really committed to the idea that you are just getting practise, you don't have to pretend that you are doing anything magical. Come up with just any way to implement the oracle function, even if it is blatantly obvious to the casual observer whether the result is constant or balanced. You're just trying to practise realising an algorithm — don't worry that someone will accuse you of being an impostor, that you're pretending to cure cancer but are actually playing with Lego. You never were pretending to cure cancer, and you are playing with Lego by deliberate choice. Embrace that and just do it.

(ii) If you want to be sure that you aren't cheating somehow (nor the emulator, nor the eventual quantum computer), try to find a way to construct your oracle so that it is difficult to tell whether it is balanced or constant. This itself is not necessarily easy to do. It would be natural to try to do this by describing a function $f(x) = g(x,r)$ for some hidden parameter $r$, but coming up with a function $g(x,r)$ which is either constant or balanced for the evaluation of $x$, for any (or most?) values of $r$, and where it isn't obvious how to solve it classically, is non-trivial.

• For instance, you could let $g(x,r) = x \cdot r$ for $x,r \in \{0,1\}^n$, and consider a circuit which straightforwardly evaluates $g(x,r)$ on an auxiliary qubit. In this case, we would then know that $f(x)$ is either constant or balanced. However, the reason why we know this is because $f(x)$ is obviously balanced if and only if $r \ne 0$, and we could tell that easily from the circuit construction.

• It is conceivable that the above construction could be elaborated / obfuscated somewhat, to obtain a construction which is guaranteed to evaluate either a constant function or a balanced function, and where which of these two occurs is not obvious or even difficult — but I can't think of how, at the moment.

Bear in mind that this actually be very difficult to do — but if you can see a way to do it, it could be very worthwhile: Bravyi, Gossett, and Koening did something like this for the Bernstein–Vazirani problem, and it allowed them to show a small but unconditional separation between quantum and classical complexity, which was one of the more interesting things to occur in quantum complexity in the past several years.

TL;DR

• Don't sweat over the fact that you're 'evaluating' an oracle.

• If you sweat over anything, only worry that an actual description of the function might make it possible to solve the same problem easily without a quantum computer.

• If your motivation is only to get practise with quantum programming, don't even worry about that. Save your worrying for worthier problems, like global warming. In the meantime enjoy playing with Legos while you build to something more.

Answer 5

You have two examples on the IBM Q Experience page about the algorithm. They show an example of a function. This could inspire you for your simulations I hope.