This article will walk through on how to implement the Deutsch algorithm introduced in our previous article The Deutsch-Jozsa algorithm with Google Cirq software library.

Quick Start

You can find all the technical details on how to run this program at this adress:

The good news is that you don't need any python environment installed on your computer: by following the instructions, you will be able to run the program on your favourite browser (via Python Jupiter notebook).

Run the program (either by clicking Cell -> Run All the first time or just by cliking the last cell afterwards) and you will see the quantum circuit randomly generated (corresponding to a random function to evaluate) as well as the result (0 or 1) of the measurement.

In this case, the program chose randomly the function f(x) = 1 to be evaluated (<1,1> means <f(0)=1, f(1)=1) , and measured the final state of the first qubit as 0, as expected (f(x)=1 means f is constant and thus 0 should be measured).


The Program

We recall from our last article the quantum circuit corresponding to the Deutsch algorithm


Its implementation in Cirq syntax is described in the make_deutsch_circuit function below

def make_deutsch_circuit(q0, q1, oracle):
    c = cirq.Circuit()

    # Initialize 2 qubits.
    # Apply Hadamard gate to first qubit and NOT + Hadamard to the second
    c.append([X(q1), H(q1), H(q0)])

    # Append quantum oracle.

    # Apply Hadamard to the first qubit and measure in X basis.
    c.append([H(q0), measure(q0, key='result')])

         # Return circuit
    return c

The most important part of the program concerns of course how the four distinct quantum Oracle (corresponding to the four functions to be evaluated) are implemented.

Let us consider the Cirq function responsible of generating those Oracles

  #Pick a secret 2-bit function and create a circuit to query the oracle.
  secret_function = [random.randint(0, 1) for _ in range(2)]
  oracle = make_oracle(q0, q1, secret_function)
  def make_oracle(q0, q1, secret_function):
   #Gates implementing the secret function f(x).

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

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


As a reminder, the oracle maps the state |x\rangle |y\rangle to |x\rangle |y\oplus f(x)\rangle , where \oplus is addition modulo 2. In other words, the oracle leaves the |x> qubit in its original state, and the |y> qubit is replaced by the XOR operation between y and f(x).

We recall as well the final state in which we should be just before the final measurement of the first qubit

which could be broke down in the four following cases


Case f(x) = 0

We notice that in case of f(x)=0, the make_oracle routine does not return any Oracle (the two if statements are evaluated as false), as expected. Indeed, if f(x)=0

 so that we |x> stays in its original state 1/√2(|0> + |1>) leading to a measurement of 0.

The output of the program would be in this case as per below



Case f(x) = x

Another trivial Oracle to find out is for the case f(x) = x.


Actually if f(0) = 0 and f(1) = 1 the the make_oracle routine only goes through the second if statement and returns the CNOT gate as for the quantum Oracle.

Also, let us double check that the final state of first qubit after the CNOT gate is 1/√2(|0> - |1>) leading to a measurement of 1.


We are all good, i.e the state of the first qubit is the one expected as per the table above.

If you are more into matrix representation, you may wish to follow this path rather



And the result printed out by our program looks like


Case f(x) = Not(x) => f(0) =1, f(1) = 0

If f(0)=1 and f(1)=0, the function goes through the first if evaluation only, which yields to the following quantum circuit [CNOT(q0, q1), X(q1)]

As per above, we should verify that the quantum circuit transforms the first qubit's state to -1/√2(|0> - |1>), leading to a measurement of 1.

Compared to the previous quantum circuit, we just have to apply an extra Pauli-X gate to the second qubit, which yields to:


And the state of the first qubit is -1/√2(|0> - |1>), as expected.


Case f(x) = 1

FInally, the last case to consider is when f(x)=1.

In this particular case, the make_oracle routine goes through the two if statements, leading to the following quantum circuit

Compared to the previous quantum circuit, we just have to apply an extra CNOT gate to the second qubit's state leading to:

 The state of the first qubit after the Oracle is applied is -1/√2(|0> -+|1>), as expected.