# Implementing four oracles for the Deutsch Algorithm (preferably on IBM Q Experience)

I guess, I understood simple Deutsch Algorithm (if unary function is balanced or constant) as described here: Introduction to quantum computing: The Deutsch algorithm

I need to test it. I was wondering how I would implement all the four function oracles. I was hoping to find it, already implemented somewhere on IBM Quantum Experience.

Could someone please point me to an implementation for the same?

EDIT: Kind of answering the question: I guess my issue was: I was trying to find $$f(x)$$ somewhere inside the bigger black box. But if I let go of that (what if I don't want to?), then things become really simple by realizing: we had function: $$x \rightarrow f(x)$$ But this is not reversible, so we wanted to implement black box with function: $$|x, y\rangle \rightarrow |x, f(x) \oplus y\rangle$$.

So here is what this translates to four possible functions:

1) $$f(x) = 0$$: $$f(x) \oplus y = 0 \oplus y = y$$, So, black box doesn't do anything

2) $$f(x) = 1$$: $$f(x) \oplus y = 1 \oplus y = \bar{y}$$ So, black box simply negate the $$y$$.

3) $$f(x) = \bar{x}$$: $$f(x) \oplus y = \bar{x} \oplus y$$ (which is also $$\overline{x \oplus y}$$)

So, we can implement it in two ways:

Option 1: for $$x$$: not it twice so that finally we get $$x$$. for $$y$$: when $$x$$ is notted once, at that point use it as control to CNOT $$y$$ and output that.

Option 2: $$x$$ is outputted as it is. For $$y$$ take $$x$$ as control and CNOT it. Then NOT it. Here CNOT gives $$x \oplus y$$, and when we NOT it we get $$\overline{(x \oplus y)}$$ which is same as $$\bar{x} \oplus y$$

4) $$f(x) = x:$$ For $$y$$ simply CNOT it with $$x$$, using $$x$$ as control.

I verified it (on IBM Q Experience) and it seems to be working. :-) I see that in all 4 implementation it is possible to not change $$x$$ at all. But yet, when we measure it, it's value is changing!!! I guess I still have to turn my head around that.

An oracle $$U_f$$ is actually $$\mathrm{X}$$ gate (or a negation). The circuit implementing the oracle is following

Qubit $$q_0$$ is input and qubit $$q_{1}$$ is output. Firstly $$\mathrm{X}$$ is applied on $$q_{0}$$. This negate the qubit, however, we want to have an output on $$q_1$$. Therefore, we apply $$\mathrm{CNOT}$$ which in this setting "copy" the $$q_{0}$$ to output $$q_{1}$$. After that the second $$\mathrm{X}$$ returns state of $$q_0$$ back to preserve input value here.

Second and third oracles in the article are same. These examples shows how to build Deutsch-Jozsa algorithm step by step. But they use same oracle as an example.

The fourth oracle is general case of function with more than one input qubit. So, I cannot provide you with implementation unless I have a matrix defining function $$U_f$$.

Note: $$\mathrm{CNOT}$$ gate is so-called controlled negation. In fact it is XOR logical function and can be used for copy qubits (so-called fan-out gate). Meaning of "copy" can be somehow misleading because it is not possible to copy quantum state. But application of $$\mathrm{CNOT}$$ leads to entanglement between qubits and therefore $$q_0$$ and $$q_1$$ behave in same way; they have same value.

• I am a bit confused with CX gate. Is my understanding correct that above line acts as control (solid dot, and is not changed by CX gate) and below line acts as target? – user1953366 Jan 17 at 20:04
• @user1953366: Yes, $q_0$ is control qubit and $q_1$ is target qubit. The $CNOT$ take an output of the function and put it on qubit $q_1$. It is in fact implementation of $|x,y\rangle \rightarrow |x,f(x) \oplus y\rangle$ as described in the article. In terms of my circuit $x = q_0$ and $y = q_1$. – Martin Vesely Jan 17 at 22:09
• Thanks @Martin. I am able to run all the four cases now. Source of my confusion was: I was expecting to find f(x) implementation somewhere inside the blackbox. Apparently thats not how it was done. But what if we ant to take f(x) and wrap it? I'll ask another question for that soon. I'll also edit how I did this in my answer. – user1953366 Jan 18 at 1:20
• @user1953366: Glad my advice helped you. What do you mean by wrapping $f(x)$? It is possible to write custom gate and to hide the oracle. Is it what are you looking for? – Martin Vesely Jan 18 at 8:31

@cgranade and I have a chapter on the Deutsch-Jozsa algorithm (Chapter 7) as well as implementations of the oracles for Q# in our book Learn Quantum Computing with Python and Q#. You can find the code samples for the book in the repo here. In particular, the oracles look like this:

namespace DeutschJozsa {
open Microsoft.Quantum.Intrinsic;

operation ZeroOracle(control : Qubit, target : Qubit) : Unit {
}

operation OneOracle(control : Qubit, target : Qubit) : Unit {
X(target);
}

operation IdOracle(control : Qubit, target : Qubit) : Unit {
CNOT(control, target);
}

operation NotOracle(control : Qubit, target : Qubit) : Unit {
X(control);
CNOT(control, target);
X(control);
}
}

• Thanks for your explanation. It is very similar to the video here: youtu.be/F_Riqjdh2oM?t=2279 Unfortunately, I am not able to turn my head around this. When we wrap f(x) around another blackbox, we have: |x0> as input and o/p is: |xf(x)> Issue is (for example with your Zero Oracle):Here input is |x0> (I guess x is target and 0 is control??) so if f(x) is constant ZERO, ZeroOracle makes sense. But if we give input as |11> to this oracle we get output also as |11>. But as per formulation of blackbox we should get output as |10>. – user1953366 Jan 17 at 19:31
• Sarah and I go into a bit more detail in Chapters 6 and 7 of our book, but the way I like to think of it is that if an control state of |0> translates to asking about f(0), then an control state of |+> translates to asking a question about the parity of f(0) and f(1). To make that work, we need our oracles to be reversible, which means that mapping |xy> to |x0> doesn't work: you forget the value of y. That's why each of the oracles in Sarah's answer have the structure that they do: they're reversible representations of each different f. – Chris Granade Jan 17 at 19:47

I implemented them as a "subcircuit" so it looks "hidden" from the "outside".

constant 0:

input = QuantumRegister(1, name='input')
temp = QuantumRegister(1, name='temp')
constant0 = QuantumCircuit(input, temp, name='oracle')
oracle = constant0.to_instruction()


identity:

input = QuantumRegister(1, name='input')
temp = QuantumRegister(1, name='temp')
identity = QuantumCircuit(input, temp, name='oracle')
identity.cx(input, temp)
oracle = identity.to_instruction()


inverts:

input = QuantumRegister(1, name='input')
temp = QuantumRegister(1, name='temp')
invert = QuantumCircuit(input, temp, name='oracle')
invert.cx(input, temp)
invert.x(temp)
oracle = identity.to_instruction()


constant 1:

input = QuantumRegister(1, name='input')
temp = QuantumRegister(1, name='temp')
constant1 = QuantumCircuit(input, temp, name='oracle')
constant1.x(temp)
oracle = constant1.to_instruction()


So you can add the oracle in the algorithm like this:

qr = QuantumRegister(2)
cr = ClassicalRegister(1)
circuit = QuantumCircuit(qr, cr)
circuit.x(qr[1]);
circuit.h(qr)
circuit.append(oracle, [qr[0], qr[1]])
circuit.h(qr[0])
circuit.measure(qr[0], cr[0]);


And you can run it like this:

counts = execute(circuit, backend=local_simulator).result().get_counts()
if '1' in counts:
print('BALANCED')
elif '0' in counts:
print('CONSTANT')


I think this snippet from Cirq's Deutsch's algorithm example (disclosure: I am its author) should be fairly easy to understand:

def make_oracle(q0, q1, secret_function):
""" Gates implementing the secret function f(x)."""

# coverage: ignore
if secret_function[0]:
yield [CNOT(q0, q1), X(q1)]

if secret_function[1]:
yield CNOT(q0, q1)


In the code, secret_function[i] is the value of $$f(i)$$.

If $$f(0) = f(1) = 0$$, nothing happens so the q1 maintains its initial value of 0.

If $$f(0) = f(1) = 1$$, the sequence CNOT(q0, q1), X(q1), CNOT(q0, q1) is applied, which is the same as just X(q1) no matter the value of q0, which means q1 is flipped to 1.

If $$f(0) = 0$$ and $$f(1) = 1$$, then only CNOT(q0, q1) is applied, which means the input is passed through (i.e., q1 is effectively assigned the value of q0).

If $$f(0) = 1$$ and $$f(1) = 0$$, then CNOT(q0, q1), X(q1) is applied, which means the inputs are exchanged after passing through (i.e., q1 is assigned the opposite of the value of q0).

Since you ask about the IBM Quantum Experience, you can produce the four oracle functions as follows in Qiskit:

# Pick a secret function.
secret = [random.randint(0, 1) for _ in range(2)]
def append_oracle(ciruit, secret):
if secret[0]:
circuit.cx(0, 1)
circuit.x(1)
if secret[1]:
circuit.cx(0, 1)

# Create the Deutsch algorithm circuit.
circuit = QuantumCircuit(2, 1)
circuit.x(1)
circuit.barrier()
circuit.h(0)
circuit.h(1)
circuit.barrier()
append_oracle(circuit, secret)
circuit.barrier()
circuit.h(0)
circuit.measure(0, 0)
circuit.draw()


You can of course set secret = [$$f(0)$$,$$f(1)$$] explicitly to each of the four possible combinations of $$f(0)$$ and $$f(1)$$ to output the circuit you want.

You can easily create these using the circuit composer if that's what you want to do:

$$f(0) = f(1) = 0$$ (balanced):

$$f(0) = 0, f(1) = 1$$ (constant):

$$f(0) = 1, f(1) = 0$$ (constant):

$$f(0) = f(1) = 1$$ (balanced):

(You can of course simplify this last circuit by removing the two CNOTs.)