Circuit-based Analysis of the Deutsch Algorithm

INTRODUCTION

The problem that the Deutsch algorithm solves is expressed in terms of binary functions f: {0,1} → {0,1}. There are four such functions:

We are given one of these four functions but we do not know which one. The goal is to determine whether the function is:
- constant (the output is the same regardless of the input), i.e. f(0)=f(1)
or
- balanced (exactly half of the outputs are 0s and half are 1s), i.e. f(0)≠f(1).

The functions f_0 and f_1 are constant, and the functions f_I and f_X are balanced. However, this algorithm does not reveal which exact function was given.

How many queries do we need to discover whether the function is constant or balanced?

• Using a classical algorithm: 2.
• Using a quantum algorithm: 1.

ORACLE DESIGN

The quantum circuit that implements the Deutsch algorithm looks as follows:

Let us take a closer look at the oracle U_f, which is the part of the quantum circuit that encapsulates the function f(x).

Since the oracle performs the computation ∣x⟩ ∣y⟩ → ∣x⟩ ∣ y ⊕ f (x)⟩, we can check how it behaves for all four functions and for every possible input value.

Function f_0 — constant 0:

The effect of applying the constant 0 oracle is the same as applying identity gates to both qubits.

Function f_1 — constant 1:

The constant 1 oracle inverts the state of the bottom qubit. This can be represented as applying the Pauli X gate on the bottom qubit.

Function f_I — balanced identity:

The balanced identity oracle inverts the state of the bottom qubit only if the top qubit is in the state ∣1⟩. This behavior can be implemented with the CNOT gate.

Function f_X — balanced negation:

After applying the balanced negation oracle the state of the bottom qubit remains unchanged only if the top qubit is in state ∣1⟩. This effect is the same as applying the Pauli X gate to the bottom qubit, and then applying the CNOT gate.

GATE DIFFERENCES BETWEEN ORACLES

It can be observed that the main difference between the constant and balanced oracles is that the latter include the CNOT gate.

If we could detect where the CNOT gate is, we would be able to distinguish the constant and balanced functions.

However, it is not as simple as applying ∣1⟩ to the top qubit and observing whether the value of the bottom qubit changes. In such a case, constant 1 and balanced identity functions would behave in the same way, and constant 0 and balanced negation functions would also be indistinguishable.

We need to detect the CNOT gate using a different approach.

DETECTING THE CNOT GATE

Since in the original algorithm only the measurement result of the top qubit is important, we can add an additional Hadamard gate on the bottom qubit at the end of the circuit.

This trick will help us to observe how the CNOT gate can be detected.

Applying the “Hadamard sandwich” to constant oracles representing the constant functions yields the following results:

Applying the “Hadamard sandwich” to the oracles representing the balanced functions has the following results:

What we can observe is that the control and target qubits of the CNOT gate switch places. This allows us to use the bottom qubit as the control qubit, and it is sufficient to initialize it in state ∣1⟩, and just observe if the output of the top qubit changes its value or not.

The initial state of the top qubit is ∣0⟩, and that of the bottom qubit is ∣1⟩.

- If the oracle represents a constant function, it does not consist of the CNOT gate, and thus the measurement result of the top qubit will be 0.

- If the oracle represents a balanced function, it includes the CNOT gate, so the state of the top qubit will be inverted, which will always return the measurement result of 1.

SUMMARY

The main difference between the constant and balanced oracles is the presence of the CNOT gate in balanced oracles.

The output of the circuit is measured on the top qubit. The measurement result 0 indicates that the oracle does not contain the CNOT gate (constant functions), while the measurement result 1 means that the CNOT gate is present (balanced functions).

If you are interested in this topic, we invite you to sign up for the QNickel6 workshop (21–22.10 & 28–29.10.2023) in which the Deutsch algorithm will be one of the topics: https://www.qaif.org/events/workshops/qnickel6-21-22-10-28-29-10-2023.