Deutsch’s Algorithm

Deutsch’s Algorithm is a concise demonstration of the differences in computational complexity between classical and quantum algorithms for certain problems. For Desutch’s algorithm, we begin with a function which takes in a bit and outputs a bit. This can be represented as \(f: \{0,1\} \longrightarrow \{0,1\}\). The function \(f\) has the property that it either constant or balanced. The goal of Deutsch’s Algorithm is to determine whether our given function is constant or whether it is balanced.

A constant function is “A balanced function is a function such that the outputs are the same regardless of the inputs, i.e., if \(f(0) = 0\) then \(f(1) = 1\) or if \(f(0) = 1\) then \(f(1) = 0\). “, the outputs are the same regardless of the inputs, i.e., in the case of \(f: \{0,1\} \longrightarrow \{0,1\}\), there are are two ways in which this can occur: \(f(0) = f(1) = 0\) or \(f(0) = f(1) = 1\).

A balanced function is defined such that the ouputs are balanced across their possibilities, i.e., if \(f(0) = 0\) then \(f(1) = 1\) or if \(f(0) = 1\) then \(f(1) = 0\).

Classically, if we are given a function \(f: \{0,1\} \longrightarrow \{0,1\}\), we can determine if it is constant or balanced by evaluating the function at \(0\) and at \(1\). This is carried out in the code below:

# Treat the code snippet below like a black box, i.e., you don't have access to the value of the property argument and can just query f with different inputs.


def f(x, property='constant'):

    if property == 'constant':

        # The output is a 1 regardless of the input; we can also make the output to be 0.

        if x == 0:
            return 1
        elif x == 1:
            return 1

    if property == 'balanced':

        # The output depends on the input.

        if x == 0:
            return 1
        elif x == 1:
            return 0

Let us now classically find out if the function we defined above is constant or balanced.

if f(0) == 0:
    if f(1) == 0:
        print('The function is constant')
    elif f(1) == 1:
        print('The function is balanced')

elif f(0) == 1:
    if f(1) == 1:
        print('The function is constant')
    elif f(1) == 0:
        print('The function is balanced')

The function is constant

If you step through the if statements above, you may notice that we require 2 calls to the function to determine its property. That is, we have to query \(f\) twice.

The claim is that Deutsch’s Algorithm can determine if a given function is constant or balanced with just 1 function evalulation, demonstrating quantum advantage.

Below we first outline Deutsch’s Algorithm and work through the math to verify that it does as promised. Then, we provide the implementation in CUDA-Q.

XOR \(\oplus\)

You may have seen the \(\oplus\) symbol floating around. This is the exclusive OR or the XOR operation. It follows the rules of addition modulo 2. For example,

1. \(3\oplus5 = (3+5)_{\%2} = 8_{\%2} = 0\)

2. \(5\oplus4 = (5+4)_{\%2} = 9_{\%2} = 1\)

A quick way to perform the \(\oplus\) calculation is if the result of the addition is an even number, the result is 0 otherwise 1.

Quantum oracles

Suppose we have \(f(x): \{0,1\} \longrightarrow \{0,1\}\). We can compute this function on a quantum computer using oracles which we treat as black box functions that yield the output with an appropriate sequence of logical gates.

Above you see an oracle represented as \(U_f\) which allows us to transform the state \(\ket{x}\ket{y}\) into:

\[\begin{aligned} U_f\ket{x}\ket{y} = \ket{x}\ket{y \oplus f(x)} \end{aligned}\]

If \(y = 0\), then \(U_f\ket{x}\ket{y} = U_f\ket{x}\ket{0} = \ket{x}\ket{0 \oplus f(x)} = \ket{x}\ket{f(x)}\), since \(f(x)\) can either be \(0\) or \(1\) and \(0 \oplus 0 = 0\) and \(0 \oplus 1 = 1\).

This is remarkable because by setting \(\ket{y} = \ket{0}\), we can extract the value of \(f(x)\) by measuring the value of the second qubit.

Phase oracle

Since \(f(x)\) can be either \(0\) or \(1\), we have that \(0 \oplus f(x) = 0 \oplus 0 = 0 = f(x)\) or \(0 \oplus f(x) = 0 \oplus 1 = 1 = f(x)\).

Similarly, \(1 \oplus f(x) = 1 \oplus 0 = 1 = \overline{f(x)}\) or \(1 \oplus f(x) = 1 \oplus 1 = 0 = \overline{f(x)}\) where the bar on top of \(f(x)\) denotes ‘not \(f(x)\)’.

Let us now prove a result which we shall use later:

\[\begin{split}\begin{aligned} U_f\ket{x}\ket{-} &= U_f \ket{x} \tfrac{1}{\sqrt{2}}(\ket{0} - \ket{1}) \\ &= \tfrac{1}{\sqrt{2}} (U_f\ket{x}\ket{0} - U_f\ket{x}\ket{1}) \\ &= \tfrac{1}{\sqrt{2}} (\ket{x}\ket{0 \oplus f(x)} - \ket{x}\ket{1 \oplus f(x)}) \\ &= \tfrac{1}{\sqrt{2}} (\ket{x}\ket{f(x)} - \ket{x}\ket{\overline{f(x)}}) \\ &= \begin{cases} \tfrac{1}{\sqrt{2}} (\ket{x}\ket{0} - \ket{x}\ket{1}) = \ket{x}\ket{-} & f(x) = 0 \\ \tfrac{1}{\sqrt{2}} (\ket{x}\ket{1} - \ket{x}\ket{0}) = -\ket{x}\ket{-} & f(x) = 1 \\ \end{cases} \\ &= (-1)^{f(x)}\ket{x}\ket{-} \end{aligned}\end{split}\]

In summary, \(U_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-}\) where the \(\ket{-}\) qubit was left unchanged and a phase was applied to \(\ket{x}\).

Quantum parallelism

Consider:

\[\begin{split}\begin{aligned} U_f\ket{+}\ket{0} &= U_f \tfrac{1}{\sqrt{2}}(\ket{0}+\ket{1}) \ket{0} \\ &= U_f \tfrac{1}{\sqrt{2}}(\ket{0}\ket{0}+\ket{1}\ket{0}) \\ &= \tfrac{1}{\sqrt{2}}(U_f \ket{0}\ket{0} + U_f \ket{1}\ket{0}) \\ &= \tfrac{1}{\sqrt{2}}(U_f \ket{0}\ket{0} + U_f \ket{1}\ket{0}) \\ &= \tfrac{1}{\sqrt{2}}(\ket{0}\ket{0 \oplus f(0)} + \ket{1}\ket{0 \oplus f(1)}) \\ &= \tfrac{1}{\sqrt{2}}(\ket{0}\ket{f(0)} + \ket{1}\ket{f(1)}) \\ \end{aligned}\end{split}\]

We have calculated information about both \(f(0)\) and \(f(1)\) simultaneously. Quantum mechanics allows for parallelism by exploiting the ability of superposition states.

Deutsch’s Algorithm:

Our aim is to find out if \(f: \{0,1\} \longrightarrow \{0,1\}\) is a constant or a balanced function? If constant, \(f(0) = f(1)\), and if balanced, \(f(0) \neq f(1)\).

We step through the circuit diagram below and follow the math after the application of each gate.

\[\ket{\psi_0} = \ket{01} \tag{1}\]

\[\ket{\psi_1} = H_1H_0\ket{\psi_0} = H_1H_0\ket{01} = \ket{+-} = \frac{1}{\sqrt{2}} (\ket{0}+\ket{1})\ket{-} \tag{2}\]

\[\ket{\psi_2} = U_f\ket{\psi_1} = \frac{1}{\sqrt{2}} (U_f\ket{0}\ket{-} + U_f\ket{1}\ket{-}) \tag{3}\]

using \(U_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-}\) which we proved in the phase oracle section above:

\[\begin{split}\begin{aligned} \ket{\psi_2} = \frac{1}{\sqrt{2}} ((-1)^{f(0)}\ket{0}\ket{-} + (-1)^{f(1)}\ket{1}\ket{-}) \\ = \frac{1}{\sqrt{2}} ((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}) \ket{-} \\ \end{aligned}\end{split}\]

We now drop the second, qubit in the \(\ket{-}\) state from our derivations as the figure above has no further gate operations acting on it. Remember our aim is to find out if \(f(x)\) is a constant or a balanced function. We have the following options:

\[\begin{split}\begin{aligned} \ket{\psi_{2}}= \begin{cases} \tfrac{1}{\sqrt{2}} (\ket{0} + \ket{1}) & f(0) = 0, f(1) = 0, f(x) \text{ is constant} \\ -\tfrac{1}{\sqrt{2}} (\ket{0} + \ket{1}) & f(0) = 1, f(1) = 1, f(x) \text{ is constant} \\ \tfrac{1}{\sqrt{2}} (\ket{0} - \ket{1}) & f(0) = 0, f(1) = 1, f(x) \text{ is balanced} \\ -\tfrac{1}{\sqrt{2}} (\ket{0} - \ket{1}) & f(0) = 1, f(1) = 0, f(x) \text{ is balanced} \\ \end{cases} \end{aligned}\end{split}\]

\[\begin{split}\begin{aligned} \ket{\psi_{2}} = \begin{cases} \pm \tfrac{1}{\sqrt{2}} (\ket{0} + \ket{1}) = \pm \ket{+} & f(x) \text{ is constant} \\ \pm \tfrac{1}{\sqrt{2}} (\ket{0} - \ket{1})= \pm \ket{-} & f(x) \text{ is balanced} \\ \end{cases} \end{aligned}\end{split}\]

\[\begin{split}\begin{aligned} \ket{\psi_{3}}= H\ket{\psi_{2}} \begin{cases} \pm H\ket{+} = \pm \ket{0} & f(x) \text{ is constant} \\ \pm H\ket{-} = \pm \ket{1} & f(x) \text{ is balanced} \\ \end{cases} \end{aligned}\end{split}\]

We can now measure the first qubit to yield either a \(0\) or a \(1\) to determine if \(f(x)\) is constant or balanced.

Deutsch’s algorithm may not be practically useful but does demonstrate quantum advantage since it uses one function call to determine the property of \(f\) in comparison to two for classical methods.

# Import the CUDA-Q package and set the target to run on NVIDIA GPUs.

import cudaq
import numpy as np

from typing import List

cudaq.set_target("nvidia")

# Here we input the values of [f(0), f(1)] which allows us to represent constant or balanced functions.

fx = [0, 1]

# Let us now code up the circuit shown above following the state Psi after each step.

qubit_count = 2


@cudaq.kernel
def kernel(fx: List[int]):
    qubit_0 = cudaq.qubit()
    qubit_1 = cudaq.qubit()

    # Psi 0
    x(qubit_1)

    # Psi 1
    h(qubit_0)
    h(qubit_1)

    # Psi 2 - oracle
    if fx[0] == 1:
        x.ctrl(qubit_0, qubit_1)
        x(qubit_1)

    if fx[1] == 1:
        x.ctrl(qubit_0, qubit_1)

    # Psi 3
    h(qubit_0)

    # Measure the qubit to yield if the function is constant or balanced.
    mz(qubit_0)


print(cudaq.draw(kernel, fx))

result = cudaq.sample(kernel, fx, shots_count=1)

if np.array(result)[0] == '0':
    print('f(x) is a constant function')
elif np.array(result)[0] == '1':
    print('f(x) is a balanced function')

     ╭───╮          ╭───╮
q0 : ┤ h ├───────●──┤ h ├
     ├───┤╭───╮╭─┴─╮╰───╯
q1 : ┤ x ├┤ h ├┤ x ├─────
     ╰───╯╰───╯╰───╯

f(x) is a balanced function

This algorithm can be generalized to determine if a \(n\)-bit function \(f:{0,1}^n\longrightarrow {0,1}\) is constant or a balanced with only \(\frac{n}{2}\) function evaluations, for \(n\) even. A function if balanced if half of the inputs map to \(0\) and half map to \(1\).

Here we must assume that the function that we are given is either constant or balanced since there are \(n\)-bit functions that are neither constant, nor balanced. For instance the \(2\)-bit function \(f(b_0,b_1) = \max(b_0,b_1)\) is neither balanced, nor constant.

A hint on how you might approach this problem is to first solve the problem for \(n=2\) and see if you can then use that approach to handle \(n\)-bit functions for larger values of \(n\).