July 18, 2019 Bernstein Vazirani Algorithm in Quantum Computing

Bernstein Vazirani’s Algorithm

Mathematics is the language in which the gods speak to people

– Plato

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

An algorithm is defined in computer science as a specification for solution of a class of problems. Tasks related to mathematical derivations, processing of information and logic are executed by an algorithm. An algorithm is executed in a classical computer using a programming language in a given amount of time and space.  The algorithm goes through a sequence of multiple states resulting in an output and end state. Algorithms can be random, and moving from one state to another can be because of random logic. Every step in the algorithm is well stated and effectively executed by the computer. The program which executes the algorithm ends successfully.

Quantum computers are based on qubits and not bits which have values of 0 or 1. Classical computers execute logical operations on a definite state of a bit. Qubit is related to the spin of an electron or the photon’s polarisation. Qubits can exist in a state called superposition which is of value 0 or 1 and a state in between 0 and 1. Qubits can exist in an entangled state with other qubits.

Quantum computation of a size of 20-30 qubits can be executed on a classical computer. The current quantum algorithms can be viewed as proofs of principle.  These algorithms surely show speedups over the classical algorithms. Quantum algorithms can find solutions to optimization problems. There have been quantum algorithms developed for solutions to multiple linear equations being simultaneously solved. Quantum algorithms have the potential to beat classical algorithms for similar problems.

Bernstein Vaziran’s algorithm is related to finding the black box function called Oracle. It has a string of bits which is based on a secret string. The goal of the algorithm is to find the string of bits which gives us the dot product of the oracle string.

The classical algorithm for finding the secret string is to use m bits one to find out each bit in the secret string. The dot product of the secret string will be based on the bit location m which can be 0 or 1.

The code below shows the Bernstein Vazirani algorithm’s implementation. In this implementation, we look at the Quantum Oracle function determination based on Bernstein Vazirani’’s algorithm.

Prerequisites:

1. You need to set up Python3.5 to run the code samples below. You can download from this link.
2. Install pyquil using pip.
3. Install the forest SDK from the Riggetti site.

Problem

Bernstein Vazirani’s algorithm is used for determining the mathematical function g quantum oracle function, which is a black box operator which gives a dot product of a secret string. This is similar to Deutsch-Jozsa algorithm in that an unitary operator represents the black box. In this algorithm, the first m qubits are transformed using Hadamard and then the black box function is applied. Finally a final hadamard is used to find the output vector over the m qubits. Get Qubit Strings method  takes n and returns n qubit string.

import itertools
import numpy as np
import pyquil.api as api
from pyquil.gates import *
from pyquil.quil import Program
def Get_Qubit_Strings(n):
    qubit_strings = []
    for q in itertools.product(['0', '1'], repeat=n):
        qubit_strings.append(''.join(q))
    return qubit_strings

Get_Black_Box_Map method  returns the dot product x.a in a dictionary.

    def Get_Black_Box_Map(n, a):
    qubs = Get_Qubit_Strings(n)
    d_blackbox = {}
    for q in qubs:
        dot_prod = 0
        for i, xx in enumerate(q):
            dot_prod += a[i] * int(xx)
        d_blackbox[q] = dot_prod % 2
    return d_blackbox

A Get_Qubit_Ket method  takes qub_string as the input and returns the kronecker product of the basis ket of n-bit string and qubit string.

def Get_Qubit_Ket(qub_string):
    e0 = np.array([[1], [0]])
    e1 = np.array([[0], [1]])
    d_qubstring = {'0': e0, '1': e1}
    ket = d_qubstring[qub_string[0]]
    for i in range(1, len(qub_string)):
        ket = np.kron(ket, d_qubstring[qub_string[i]])
    return ket

Get_Projection_Op method takes input qub_string  and returned the kronecker product of the ket basis and transpose of the ket.

def Get_Projection_Op(qub_string):
    ket = Get_Qubit_Ket(qub_string)
    bra = np.transpose(ket)
    proj = np.kron(ket, bra)
    return proj

Get_Black_Box method takes input n and vector a  and returns the unitary representation of the output of the black box operation on n+1 qubits.

def Get_Black_Box(n, a):
    d_bb = Get_Black_Box_Map(n, a)
    N = 2**(n+1)
    unitary_rep = np.zeros(shape=(N, N))
    for k, v in d_bb.items():
        unitary_rep += np.kron(Get_Projection_Op(k), np.eye(2) + v*(-np.eye(2) + np.array([[0, 1], [1, 0]])))
    return unitary_rep

Control qubits of size 8 are picked and random value is chosen for the vector a. Unitary function is defined and starting state is prepared.  Hadamard is applied n times and Unitary function is applied. QVMConnection is initialized and classical register and program is executed on the qvm. The measured value of the first qubits are printed.

p = Program()
n = 8
a = np.random.randint(low=0, high=2, size=n)
print ("Random value of a: ", a)
p.defgate("U_f", Get_Black_Box(n, a))
for n_ in range(1, n+1):
    p.inst(I(n_))
p.inst(X(0))
p.inst(H(0))
for n_ in range(1, n+1):
    p.inst(H(n_))
p.inst(("U_f",) + tuple(range(n+1)[::-1]))
for n_ in range(1, n+1):
    p.inst(H(n_))
classical_regs = list(range(n))
for i, n_ in enumerate(list(range(1, n+1))[::-1]):
    p.measure(n_, classical_regs[i])
qvm = api.QVMConnection()
measure_n_qubits = qvm.run(p, classical_regs)
measure_n_qubits = [item for sublist in measure_n_qubits for item in sublist]
print ("measured values of the first %s qubits " %n, measure_n_qubits)

Instructions for Running the Code

pip install pyquil
qvm -S
#running the Bernstein Vazirani's Algorithm python code
python Bernstein_Vazirani.py

Output