Return to Revisions

There are two questions here. The first is asking how you might actually implement this in code. 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. 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;
    }
}

The second question asks why this function is at all interesting if you know which black box you're passing in ahead of time. There are two answers here: the first is from the standpoint of query complexity, which is computational complexity as measured by how many times a function has to query an oracle. The reason the Deutsch Oracle problem is interesting is because the quantum solution only has to query the black box once, while the classical solution has to query it twice. The difference is made stark in the generalized Deutsch-Josza problem, where instead of a function on $1$ bit the black box is a function on $n$ bits which is either constant or balanced. Here, the quantum solution still only has to query the black box once, but the classical solution has to query it $2^{n-1}$ times!

There's also an answer we can give about how this function might be useful in real life, which comes down to a property of linear algebra called the associativity of matrix multiplication. 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$

How this relates to the Deutsch Oracle problem is you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) 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.

As a final aside, I unfortunately have to let you down: there's something called the Gottesman-Knill theorem which tells us the Deutsch Oracle problem isn't actually useful for applications outside of teaching students their first quantum algorithm, because we can efficiently simulate it on a classical computer.