July 4, 2019 Duetsch-Jozsa’s Algorithm in Quantum Computing

Duetsch-Jozsa’s Algorithm

Mathematics is as much an aspect of culture as it is a collection of algorithms.

Carl Benjamin Boyer

This article will introduce Duetsch-Jozsa’s Algorithm in the Quantum Algorithms series. In the series so far, we have seen Grover’s Algorithm, Shor’s Algorithm and Simon’s Algorithm. The reader will learn how to implement Duetsch-Jozsa’s Algorithm which is used for search solutions.

The algorithm is a very basic concept in the field of computing and information processing. Solutions for real-life problems are based on algorithms.  Systems are built using heuristics and techniques based on algorithms. An algorithm is defined as a group of commands which perform a task. According to the Meriam-Webster dictionary, the algorithm is a procedure for solving a mathematical problem in a finite number of steps that frequently involves repetition of an operation. It is a step-by-step procedure for solving a problem or accomplishing some end.

Quantum computers solve problems which are almost impossible or computationally challenging for classical computers. Quantum supremacy is related to the domination of quantum computers over classical. Google’s quantum processor is evolving to make this term real.  Qubits are the building blocks for the quantum computer. Classical computers are based on bits and logic gates. Similarly, quantum computers use qubits and quantum gates. Superposition is a state where a qubit can exist with value 0 or 1. Qubits are described as entangled to each other when quantum gates operate on multiple qubits more than 2. A quantum circuit consists of quantum gates in a designed form.

Quantum Algorithms operate on qubits to create a superposition state. If the algorithm needs m qubits, 2^m  (2 power of m) states are possible for modeling different combinations in the algorithmic model. Quantum circuit has gates which are patterns operating on the qubits which are in superposition. Measurement to identify the pattern is performed at the end of the circuit after all quantum operations are done.

Deutsch-Jozsa’s algorithm was discovered to demonstrate the gap between classical and quantum computational power. The algorithm is related to quantum amplitudes which can take both positive and negative values.  Let’s say there is a function g(y) which takes m bit strings y and returns the value 0 or 1. The Deutsch-Jozsa algorithm helps in identifying g whether constant or balanced by performing minimum function evaluations. This algorithm does one evaluation compared to 2m-1+1 evaluations required for the classical algorithm.

The code below shows the Duetsch-Jozsa algorithm implementation. In this implementation, we look at the black box function determination based on Duetsch-Jozsa’s algorithm.

Prerequisites:

1. You need to set up Python3.5 to run the code samples below. You can download from this link.

Problem

Duetsch-Jozsa’s algorithm is used for determining if the function is constant or balanced. Quantum Register class is defined with __init__, Get_Measure and Apply_Operation methods. __init__ constructor takes the number of qbits and initial value.

import numpy as np
from itertools import product
from Quantum_Gates import Quantum_Gate
class Quantum_Register:
    def __init__(self, n_qbits, init):
        self._n = n_qbits
        assert len(init) == self._n
        self._data = np.zeros((2 ** self._n), dtype=np.complex64)
        self._data[int('0b' + init, 2)] = 1

Get_Measure method of the Quantum_Register class calculates the probabilities and the states. This method returns the string which has measured state and the number of qubits.

def Get_Measure(self):
        probs = np.real(self._data) ** 2 + np.imag(self._data) ** 2
        states = np.arange(2 ** self._n)
        mstate = np.random.choice(states, size=1, p=probs)[0]
        return f’{mstate:>0{self._n}b}'

Apply_Operation method of the Quantum_Register class takes the parameter gate and sets the data to the product of the matrices gate’s _data and Quantum Register instance _data.

  def Apply_Operation(self, gate):
        assert isinstance(gate, Quantum_Gate)
        assert self._n == gate._n
        self._data = gate._data @ self._data

Quantum_Gate class has __init__, __GetMatProd__ and __GetExponent methods. The __init__ constructor takes matrix as parameters and sets the _n to integer value of matrix first element’s logarithmic value of base 2. 

 import numpy as np
from itertools import product
class Quantum_Gate:
    def __init__(self, matrix):
        self._data = np.array(matrix, dtype=np.complex64)
        assert len(self._data.shape) == 2
        assert self._data.shape[0] == self._data.shape[1]
        self._n = np.log2(self._data.shape[0])
        assert self._n.is_integer()
        self._n = int(self._n)

__GetMatProd__ method of Quantum_Gate takes other as the parameter and returns a Quantum_Gate initialized with kronecker product of instance _data and other’s _data.

    def __GetMatProd__(self, other):
        return Quantum_Gate(np.kron(self._data, other._data))

__GetExponent__ takes the parameters n and modulo. The method returns a Quantum_Gate initialized with kronecker product of _data instance copy and _data instance.

    def __GetExponent__(self, n, modulo=None):
        x = self._data.copy()
        for _ in range(n - 1):
            x = np.kron(x, self._data)
        return Quantum_Gate(x)

Quantum_Gate instances are created for gates I, H, X, Y and Z. U method is defined which takes f and n as parameters. It returns the Quantum_Gate U which has instate and outstate as the real and imaginary parts.

I_Gate = Quantum_Gate([[1, 0], [0, 1]])
H_Gate = Quantum_Gate(np.array([[1, 1], [1, -1]]) / np.sqrt(2))
X _Gate = Quantum_Gate([[0, 1], [1, 0]])
Y_Gate = Quantum_Gate([[0, -1j], [1j, 0]])
Z_Gate  = Quantum_Gate([[1, 0], [0, -1]])
def U_Gate(f, n):
    m = n + 1
    U = np.zeros((2**m, 2**m), dtype=np.complex64)
    def bin2int(xs):
        r = 0
        for i, x in enumerate(reversed(xs)):
            r += x * 2 ** i
        return r
    for xs in product({0, 1}, repeat=m):
        x = xs[:~0]
        y = xs[~0]
        z = y ^ f(*x)
        instate = bin2int(xs)
        outstate = bin2int(list(x) + [z])
        U[instate, outstate] = 1
    return Quantum_Gate(U)

The Check_Constant method takes parameters g and n.  A quantum register is created with parameters n+1 and product of ‘0’ and n+’1’.  The quantum register is applied with operations H_Gate, U Gate and the product of H_Gate and I_Gate.

from Quantum_Register import Quantum_Register
from Quantum_Gates import H_Gate, I_Gate, U_Gate
def Check_Constant(g, n):
    q = Quantum_Register(n + 1, '0' * n + '1')
    q.Apply_Operation(H_Gate ** (n + 1))
    q.Apply_Operation(U_Gate(f, n))
    q.Apply_Operation(H_Gate ** n @ I_Gate)
    return q.Get_Measure()[:~0] == '0' * n

Functions g1, g2, g3, and g4 are defined below. g1 takes y and returns y.

def g1(y):
    return y

g2 takes y as input value and returns value 1.

def g2(y):
    return 1

g3 takes y and z as input values and returns the Binary XOR of y and z.

def g3(y, z):
    return y ^ z

g4 takes y, z, and w  as input values and returns the zero value.

def g4(y, z,w):
    return 0
print('g(y) = y is {}'.format('constant function' if Check_Constant(g1, 1) else 'balanced function'))
print('g(y) = 1 is {}'.format('constant function' if Check_Constant(g2, 1) else 'balanced function'))
print('g(y, z) = y ^ z is {}'.format('constant function' if Check_Constant(g3, 2) else 'balanced function'))
print('g(y, z, w) = 0 is {}'.format('constant function' if Check_Constant(g4, 3) else 'balanced function'))

Instructions for Running the Code

#running the Deutsch Jozsa’s Algorithm python code
python Deutsch_Jozsa.py

Output