Simon’s Algorithm in Quantum Computing
Simon’s Algorithm
I remember that mathematicians were telling me in the 1960s that they would recognize computer science as a mature discipline when it had 1,000 deep algorithms. I think we've probably reached 500.Donald Knuth
This article will introduce Simon's Algorithm in the Quantum Algorithms series. In the series so far, we have seen Grover’s Algorithm and Shor’s Algorithm. The reader will learn how to implement Simon's Algorithm which is used for training the quantum neural nets.
The word Algorithm is derived from the word ‘algebra’. It is after the mathematician from Arabia whose name was Al Khwarizmi. It is a group of commands which takes an input and gives the output after processing the commands. Algorithms are used in different areas for solving problems such as data compression, encryption, optimization and prediction. Algorithms are designed through a process by a set of engineers with a background in maths. Enterprises hire designers and engineers to design new algorithms for search and optimization.
Quantum computing is based on the characteristics of quantum mechanics. Quantum computers provide solutions to problems with exponential speed. The solutions are used in different domains from retail to finance. The return on investment from quantum computing is expected to be very high and there are plans for faster adoption of the quantum computer. Quantum computer hardware is very challenging to design and manufacture. The challenges are related to noise and loss of quantum coherence. The current research is focusing on bringing down the error.
Quantum algorithms are shorter compared to classical ones. Quantum algorithms can be run on both classical and quantum computers. The execution speed expected from these algorithms on quantum computers beats the speed of classical ones. Once we have the quantum computer hardware in place, we expect exponential speedup on the quantum computers.
Polynomial time order algorithms which take exponential order of time can be executed on the quantum computer. The classical computer will be used for the problems which have solutions that can efficiently be run on classical.
Simon’s problem is related to finding a black box function g(x) where g(x) = g(y) and x= y ⊕ s.
s ∈ {0, 1}n and ⊕ represents bitwise addition based on module two. The solution is to determine the s by evaluating g. This solution is of the order of exponential time. Simon’s quantum algorithm solves the problem in the order of O(n) evaluations of function g. The solution is based on finding the values to satisfy a linear system based equation.
The code below shows the Simon’s algorithm implementation. In this implementation, we look at the black box function determination based on Simon’s algorithm.
Prerequisites:
You need to set up Python3.5 to run the code samples below. You can download from this link.
You need to set up Pyquil to run this code sample. Pyquil can be downloaded from the website.
Problem
Simon’s algorithm is used for determining the black box function to satisfy a set of values. Simons_Algorithm class is used for finding the solutions to Simon’s problem. The initial values are set to None in the __init__ function.
from collections import defaultdict
import numpy as np
from mock import patch
from collections import defaultdict
from operator import xor
from typing import Dict, Tuple, List
import numpy as np
import numpy.random as rd
from pyquil import Program
from pyquil.api import QuantumComputer
from pyquil.gates import H, MEASURE
class Simons_Algorithm(object):
def __init__(self):
self.qc_unitary_function_mapping = None
self.n_qc_qubits = None
self.n_qc_ancillas = None
self._qc_qubits = None
self.qc_computational_qubits = None
self.qc_ancillas = None
self.qc_simon_circuit = None
self._qc_dict_of_linearly_indep_bit_vectors = {}
self.search_mask = None
self.qc_bit_map = None
self.cs_classical_register = None
Get Simon circuit method of Simons_Algorithm class implements the quantum algorithm.
The input qubits are transformed with Walsh Hadamard operations and Oracle operation.
The output is the simon’s circuit based program.
def _Get_Simon_Circuit(self) - Program:
qc_simon_circuit = Program()
qc_oracle_name = "SIMONS_ORACLE"
qc_simon_circuit.defgate(oracle_name, self.unitary_function_mapping)
qc_simon_circuit.inst([H(i) for i in self.qc_computational_qubits])
qc_simon_circuit.inst(tuple([oracle_name] + sorted(self._qc_qubits, reverse=True)))
qc_simon_circuit.inst([H(i) for i in self.qc_computational_qubits])
return qc_simon_circuit
Initialize attributes takes the inputs bit string map and dictionary of key and values. The method of the Simons_Algorithm class takes the inputs and initializes the attributes.
def _Initialize_Attributes(self, bitstring_map: Dict[str, str]) - None:
self.qc_bit_map = bitstring_map
self.n_qc_qubits = len(list(bitstring_map.keys())[0])
self.n_qc_ancillas = self.n_qubits
self._qc_qubits = list(range(self.n_qubits + self.n_ancillas))
self.qc_computational_qubits = self._qubits[:self.n_qubits]
self.qc_ancillas = self._qubits[self.n_qubits:]
self.qc_unitary_function_mapping, _ = self._compute_unitary_oracle_matrix(bitstring_map)
self.qc_simon_circuit = self._construct_simon_circuit()
self._qc_dict_of_linearly_indep_bit_vectors = {}
self.search_mask = None
Get_Compute_Unitary_Oracle_Matrix method of Simons_Algorithm class takes the input map of bitstrings as a dictionary. The method finds the unitary matrix based on the oracle function encoding. It returns the dense matrix which has the permutation of the values from the dictionary.
@staticmethod
def _Get_Compute_Unitary_Oracle_matrix(qc_bitstring_map: Dict[str, str]) - Tuple[np.ndarray,Dict[str, str]]:
n_bits = len(list(qc_bitstring_map.keys())[0])
ufunc = np.zeros(shape=(2 ** (2 * n_bits), 2 ** (2 * n_bits)))
index_mapping_dict = defaultdict(dict)
for b in range(2**n_bits):
pad_str = np.binary_repr(b, n_bits)
for k, v in qc_bitstring_map.items():
index_mapping_dct[pad_str + k] = bitwise_xor(pad_str, v) + k
i, j = int(pad_str+k, 2), int(Apply_Bitwise_Xor(pad_str, v) + k, 2)
ufunc[i, j] = 1
return ufunc, index_mapping_dict
Get_Mask method of Simons_Algorithm class takes the inputs quantum computer and dictionary of bit strings. The method searches for the mask using the mask array algorithm. It returns the bit string map if the mask is found. Otherwise, it throws an exception.
def Get_Mask(self, quantum_computer: QuantumComputer, bitstring_map: Dict[str, str]) - str:
self._Initialize_Attributes(bitstring_map)
self._Get_Sample_Independent_Bit_Vectors(quantum_computer)
self._Apply_Inverse_Mask_Equation()
if self._Verify_Mask_If_Correct():
return self.search_mask
else:
raise Exception(“Valid mask is not found")
The Get_Sample_Independent_Bit_Vectors method of the Simons_Algorithm class takes input as the quantum computer and creates a dictionary of bitstrings. The independent bit vectors attribute is updated with sampled bit strings.
def _Get_Sample_Independent_Bit_Vectors(self, quantum_computer: QuantumComputer) - None:
while len(self._qc_dict_of_linearly_indep_bit_vectors) < self.n_qubits - 1:
program = Program()
simon_ro = program.declare('ro', 'BIT', len(self.computational_qubits))
program += self.qc_simon_circuit
program += [MEASURE(qubit, ro) for qubit, ro in zip(self.qc_computational_qubits, simon_ro)]
executable = quantum_computer.compile(program)
sampled_bit_string = np.array(quantum_computer.run(executable)[0], dtype=int)
self._Update_Dict_Of_Indep_Bit_Vectors(sampled_bit_string)
Apply Inverse Mask Equation method of Simons_Algorithm class finds the bit mask related to the input function.
def _Apply_Inverse_Mask_Equation(self) - None:
missing_msb = self._Update_Missing_Msb_Vector()
upper_triangular_matrix = np.asarray(
[tup[1] for tup in sorted(zip(self._qc_dict_of_linearly_indep_bit_vectors.keys(),
self._qc_dict_of_linearly_indep_bit_vectors.values()),
key=lambda x: x[0])])
msb_unit_vec = np.zeros(shape=(self.n_qc_qubits,), dtype=int)
msb_unit_vec[missing_msb] = 1
self.search_mask = binary_back_substitute(upper_triangular_matrix, msb_unit_vec).tolist()
Update_Dict_of_Indep_Bit_Vectors method of the Simons Algorithm takes the input as the np.ndarray type. This method creates a dictionary of the vectors which are independent. Bit Vector z is added to the dictionary. The matrix created will be in the upper triangular form.
def _Update_Dict_of_Indep_Bit_Vectors(self, qc_z: np.ndarray) - None:
if (qc_z == 0).all() or (qc_z == 1).all():
return None
msb_z = Get_Most_Significant_Bit(qc_z)
if msb_z not in self._qc_dict_of_linearly_indep_bit_vectors.keys():
self._qc_dict_of_linearly_indep_bit_vectors[msb_z] = z
else:
conflict_z = self._qc_dict_of_linearly_indep_bit_vectors[msb_z]
not_z = [xor(conflict_z[idx], z[idx]) for idx in range(len(z))]
if (np.asarray(not_z) == 0).all():
return None
msb_not_z = Get_Most_Significant_Bit(np.asarray(not_z))
if msb_not_z not in self._qc_dict_of_linearly_indep_bit_vectors.keys():
self._qc_dict_of_linearly_indep_bit_vectors[msb_not_z] = not_z
Update_Missing_Msb_Vector method of the Simons_Algorithm class searches the provenance value in the linearly independent bit vectors. The method updates the collection by adding the unit vector.
def _Update_Missing_Msb_Vector(self) - int:
missing_msb = None
for idx in range(self.n_qc_qubits):
if idx not in self._qc_dict_of_linearly_indep_bit_vectors.keys():
missing_msb = idx
if missing_msb is None:
raise ValueError(“Unable to search the provenance")
augment_vec = np.zeros(shape=(self.n_qc_qubits,))
augment_vec[missing_msb] = 1
self._dict_of_linearly_indep_bit_vectors[missing_msb] = augment_vec.astype(int).tolist()
return missing_msb
Verify_Mask_If_Correct method of the Simons_Algorithm class verifies the given mask if it is correct by checking the reproduction of the input function.
def _Verify_Mask_If_Correct(self) - bool:
mask_str = ''.join([str(b) for b in self.search_mask])
return all([self.qc_bit_map[k] == self.qc_bit_map[Apply_Bitwise_Xor(k, mask_str)]
for k in self.qc_bit_map.keys()])
The Create_One_to_One_Bitmap method takes the mask as the parameter and returns the bit map function for the mask. Bitmap function is returned as the dictionary having the possible string values from bit strings.
def Create_One_to_One_Bitmap(qc_mask: str) - Dict[str, str]:
n_bits = len(qc_mask)
form_string = "{0:0" + str(n_bits) + "b}"
bit_map_dict = {}
for index in range(2**n_bits):
bit_string = form_string.format(index)
bit_map_dict[bit_string] = Apply_Bitwise_Xor(bit_string, qc_mask)
return bit_map_dict
Create_Valid_Two_To_One_Bitmap method of the Simons_Algorithm class takes the search mask and random seed as the input parameters.It is a helper method which creates a Two to One mapping function.
def Create_Valid_Two_To_One_Bitmap(qc_mask: str, qc_random_seed: int = None) - Dict[str, str]:
if qc_random_seed is not None:
rd.seed(qc_random_seed)
bit_map = create_one_to_one_bitmap(qc_mask)
n_samples = int(len(bit_map.keys()) / 2)
range_of_2to1_map = list(rd.choice(list(sorted(bit_map.keys())), replace=False, size=n_samples))
list_of_bitstring_tuples = sorted([(key, value) for key, value in bit_map.items()], key=lambda x: x[0])
bit_map_dict = {}
for count in range(n_samples):
bitstring_tup = list_of_bitstring_tuples[count]
val = range_of_2to1_map[count]
bit_map_dict[bitstring_tup[0]] = val
bit_map_dict[bitstring_tup[1]] = val
return bit_map_dict
Check_If_Unitary method takes the np.ndarray typed matrix and returns the boolean true if the matrix is unitary.
STR_PADDED_BIN_BITS = “{0:0{1:0d}b}”
def Check_If_Unitary(qc_matrix: np.ndarray) - bool:
rows, cols = qc_matrix.shape
if rows != cols:
return False
return np.allclose(np.eye(rows), qc_matrix.dot(matrix.T.conj()))
Get_Most_Significant_Bit method takes the np.ndarray of 1s and 0s and searches the position of the most significant bit.
def Get_Most_Significant_Bit(qc_lst: np.ndarray) - int:
return np.argwhere(np.asarray(qc_lst) == 1)[0][0]
Apply_Bitwise_Xor method takes two bit strings as the inputs and returns the padded binary bit string.
def Apply_Bitwise_Xor(qc_bs0: str, qc_bs1: str) - str:
if len(qc_bs0) != len(qc_bs1):
raise ValueError(“The strings length is not equal")
n_bits = len(qc_bs0)
return STR_PADDED_BIN_BITS.format(xor(int(qc_bs0, 2), int(qc_bs1, 2)), n_bits)
Get_Binary_Back_Substitute method takes two np.ndarrays as input to apply back substitution on a binary system of equations.
def Get_Binary_Back_Substitute(QC_W: np.ndarray, qc_s: np.ndarray) - np.ndarray:
m = np.copy(qc_s)
n = len(qc_s)
for row_num in range(n - 2, -1, -1):
row = QC_W[row_num]
for col_num in range(row_num + 1, n):
if row[col_num] == 1:
m[row_num] = xor(s[row_num], qc_s[col_num])
return m[::-1]
bitmap is created based on the search_mask ‘101’ and random_seed of value 42. The expected map is initialized with different values. Expected reverse bitmap is also created.
search_mask = '110'
bit_map = Create_Valid_Two_to_One_Bitmap(search_mask, random_seed=42)
expected_bit_map = {
'000': '001',
'001': '101',
'010': '000',
'011': '111',
'100': '000',
'101': '111',
'110': '001',
'111': '101'
}
for key, value in bit_map.items():
assert value == expected_bit_map[key]
reverse_bit_map_value = defaultdict(list)
for key, value in bit_map.items():
reverse_bit_map_value[value].append(key)
expected_reverse_bit_map_values = {
'001': ['000', '110'],
'101': ['001', '111'],
'000': ['010', '100'],
'111': ['011', '101']
}
for key, value in reverse_bit_map_value.items():
assert sorted(value) == sorted(expected_reverse_bit_map_values[key])
Quantum computer is initialized from pyquil.api.QuantumComputer to set the values of run_side_effect. Simons_Algorithm instance is created and the mask found is printed.
with patch("pyquil.api.QuantumComputer") as quantum_computer:
quantum_computer.run.side_effect = [
(np.asarray([0, 1, 1], dtype=int), ),
(np.asarray([1, 1, 1], dtype=int), ),
(np.asarray([1, 1, 1], dtype=int), ),
(np.asarray([1, 0, 0], dtype=int), ),
simon_algo = Simons_Algorithm()
result_mask = simon_algo.Get_Mask(quantum_computer, bit_map)
print("mask", search_mask," result mask",result_mask)
Instructions for Running the Code
#Installing pyquil
pip install pyquil
#running the Simon’s Algorithm python code
python Simons.py
Output