Return to Revisions

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? ###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-Josza 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-Josza 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-Josza is not a good candidate for a quantum supremacy/advantage problem, which leads into...

###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 as far as 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!

###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.