mjhjmtu

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza 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.

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: $mathbbI_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|psirangle = X_0|psirangle$

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 =
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix
beginbmatrix
1 & 0 \
0 & -1
endbmatrix
beginbmatrix
frac1sqrt2 & frac1sqrt2 \
frac1sqrt2 & frac-1sqrt2
endbmatrix =
beginbmatrix
0 & 1 \
1 & 0
endbmatrix = X_0$

So we have:

$(H_0(Z_0(H_0|psirangle))) = (((H_0Z_0)H_0)|psirangle) = X_0|psirangle$

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.

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.

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.