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

Question

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.

Answer 1

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.

Answer 2

@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);
    }
}

Answer 3

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$ (constant):

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

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

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

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

Answer 4

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')