Source code for grover

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
This module is aimed to provide the user means to study the Grover algorithm and
especially how the entanglement changes during its execution using the Mermin 
evaluation.
"""
from sage.all import *

import csv
import time
from copy import copy
import os

from mermin_eval import *
from run_circuit import *


[docs]def target_state_ket_list_to_vector(target_state_ket): r""" Converts the target state from a digit list to a vector. Example: `|5>_4 = |0101> = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)` so : >>> target_state_ket_list_to_vector([0,1,0,1]) (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) :param list[int] target_state_ket: List of digit of the boolean expression of the sate looked for. :returns: vector -- Vector corresponding to the target state. """ n = len(target_state_ket) t = 0 target_state_ket_reversed = copy(target_state_ket) target_state_ket_reversed.reverse() for i in range(n): t += target_state_ket_reversed[i]*2**i result = zero_vector(field, 2**n) result[t] = 1 return result
[docs]def target_state_ket_vector_to_string(target_state_ket): r""" Converts the target state from a vector to a string containing a digit list. Example: `|5>_4 = |0101> = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)` so : >>> v = vector((0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)) >>> target_state_ket_vector_to_string(v) '0101' :param vector target_state_ket: Vector corresponding to the target state. :returns: string -- List of digit of the boolean expression of the searched sate. """ N = len(target_state_ket) n = log(N)/log(2) i = 0 while i < N and target_state_ket[i] != 1: i += 1 if target_state_ket[i] != 1: raise ValueError("argument target_state_ket is not in the appropriate" + " shape: it should be a vector of size 2^n with only zeros except" + " for one coefficient being 1, given : " + str(target_state_ket)) result = "{0:b}".format(i) while len(result) < n: result = "0" + result return result
[docs]def target_state_ket_string_to_vector(target_state_ket): r""" Converts the target state from a string containing a digit list to a vector. Example: ``|5>_4 = |0101> = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)`` so : >>> target_state_ket_string_to_vector("0101") (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) :param str target_state_ket: List of digit of the boolean expression of the searched sate. :returns: vector -- Vector corresponding to the target state. """ n = len(target_state_ket) t = int(target_state_ket, 2) result = zero_vector(field, 2**n) result[t] = 1 return result
[docs]def grover(target_state_vector, verbose=False, file_name=None, use_precomputed=False, artificial=False): r""" Prints in terminal or in file ``file_name`` the Mermin evaluation of each step of the Grover algorithm. Example: >>> grover(target_state_ket_string_to_vector("0000")) [0.168628057515893, 1.32148634347176, 1.01189404012546, 0.469906068135870] :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :param bool verbose: If ``verbose`` then extra run information will be displayed in terminal. :param str file_name: File name for the registration of the Mermin evaluation for each step of the algorithm, in csv format. :param bool use_precomputed: for some states, the optimal Mermin polynomial has been precomputed, use this option to speed up the overall computation. :param bool artificial: Due to technological limits, it is not always possible to compute the states of Grover's algorithm in a realistic simulator. This parameters allows the user to use a non realistic simulator which is way quicker. :returns: any -- Result of this function depends on file_name. If a file name is given ``qft_main`` returns None, otherwise, it returns an array with the evaluation values. """ end_loop_states = time_step("Run", grover_run, (target_state_vector, artificial, verbose), verbose) M_opt = time_step("Optimization", grover_optimize, (target_state_vector, use_precomputed, verbose), verbose) return time_step("Evaluation", grover_evaluate, (end_loop_states, M_opt, file_name), verbose)
[docs]def time_step(step_name, step_function, step_args, verbose=False): r""" Times a function, with time information displayed if ``verbose``. Example: >>> result = time_step("Add_10", lambda a : a + 10, [5], True) Add_10 starts now Add_10 complete, took 1.81198120117e-05s >>> result 15 :param str setp_name: Name of the step, used for display. :param function step_function: Function to be timed. :param tuple step_args: Arguments of the function. :param bool verbose: If `verbose` then extra run information will be displayed in terminal. :returns: any -- The output of ``step_function(*step_args)```. """ if verbose: print(step_name + " starts now") start_time = time.time() result = step_function(*step_args) end_time = time.time() interval = end_time - start_time if verbose: print(step_name + " complete, took " + str(interval) + "s") return result
[docs]def grover_run(target_state_vector, artificial=False, verbose=False): r""" Runs a simulation of the grover algorithm. :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :param bool artificial: due to technological limits, it is not always possible to compute the states of Grover's algorithm in a realistic simulator. This parameters allows the user to use a non realistic simulator which is way quicker. :param bool verbose: If `verbose` then extra run information will be displayed in terminal. :returns: list[vectors] -- the states at the end of each loop. """ if artificial: end_loop_states = grover_artifical(target_state_vector) else: end_loop_states = grover_vanilla(target_state_vector, verbose) return end_loop_states
[docs]def grover_optimize(target_state_vector, use_precomputed=False, verbose=False): r""" Computes the optimal Mermin operator to evaluate the entanglement in the Grover algorithm :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :param bool use_precomputed: For some states, the optimal Mermin polynomial has been precomputed, use this option to speed up the overall computation. :param bool verbose: If `verbose` then extra run information will be displayed in terminal. :returns: matrix -- The optimal Mermin operator. """ if use_precomputed: precomputed_filename = "precomputed_opti.csv" else: precomputed_filename = None M_opt = mermin_operator_opti(target_state_vector, precomputed_filename=precomputed_filename, verbose=verbose) return M_opt
[docs]def grover_evaluate(end_loop_states, M_opt, file_name): r""" Uses the previously found optimal mermin operator to evaluate the entanglement for each state in ``end_loop_states``. :param list[matrix] end_loop_states: The states at the end of each loop, these are vectors transformed to column matrix. :param matrix M_opt: The optimal Mermin operator. :param str file_name: File name for the registration of the Mermin evaluation for each step of the algorithm, in csv format. :returns: any -- Result of this function depends on file_name. If a file name is given ``qft_main`` returns None, otherwise, it returns an array with the evaluation values. """ if file_name == None: result = [] for state in end_loop_states: result.append(abs((state.transpose().conjugate()*M_opt*state)[0][0])) return result else : lines, i = [["iteration", "intricationValue"]], 0 for state in end_loop_states: lines.append([i, (state.transpose().conjugate()*M_opt*state)[0][0].real()]) i += 1 if not os.path.exists(os.path.dirname(file_name)) and os.path.dirname(file_name) != '': os.makedirs(os.path.dirname(file_name)) with open(file_name, 'wb+') as writeFile: writer = csv.writer(writeFile) writer.writerows(lines) writeFile.close() return None
[docs]def grover_vanilla(target_state_vector, verbose=False): r""" Computes the successive states at the end of the loop using a realistic simulation of the execution of Grover's algorithm (using the simulator from ``run_circuit.sage``). :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :param bool verbose: If `verbose` then extra run information will be displayed in terminal. :returns: list[vector] -- List of states after each application of the diffusion operator (as well as the initial state). """ N = len(target_state_vector) if verbose: print("Layers preparation") layers, k_opt = grover_layers_kopt(target_state_vector) V0 = vector([0, 1] + [0]*(2*N-2)) if verbose: print("Layers preparation done") states = run(layers, V0)[0] end_loop_states = [matrix(states[1]).transpose()] for i in range(k_opt): end_loop_states.append(matrix(states[4*(i)+5]).transpose()) for i in range(len(end_loop_states)): halved = vector([end_loop_states[i][2*k,0] for k in range(end_loop_states[i].nrows()/2)]) end_loop_states[i] = matrix(halved.normalized()).simplify().transpose() return end_loop_states
[docs]def grover_layers_kopt(target_state_vector): r""" Computes the circuit for Grover's algorithm using the circuit format used for the ``run`` function from ``run_circuit.sage``. :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :returns: (list[list[matrix]],int) -- Circuit for Grover's algorithm and optimal value found for ``k_opt``. """ X = matrix([[0, 1], [1, 0]]) H = matrix(field, [[1, 1], [1, -1]])/sqrt(2) I2 = matrix.identity(2) N = len(target_state_vector) n = log(N)/log(2) ket_zero = matrix([1]+[0]*(N-1)) symmetry = 2*ket_zero.transpose()*ket_zero-matrix.identity(N) loop = [[oracle(target_state_vector)], [H]*n+[I2],[symmetry,I2],[H]*n+[I2]] k_opt = round((pi/4)*sqrt(N)) layers = [[H]*(n+1)] for _ in range(k_opt): layers += loop return layers, k_opt
[docs]def oracle(target_state_vector): r""" The oracle O satisfies `O|x,y> = |x,f(x)+y>` where `f(x)=1` if `x` is the element looked for and `f(x)=0` otherwise. Example: The oracle flips the qubit where the target is, so : >>> oracle(target_state_ket_string_to_vector("101")) [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1] :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :returns: matrix -- The matrix corresponding to the oracle. """ N = len(target_state_vector) state_matrix = matrix(target_state_vector) I2n = matrix.identity(N*2) I2 = matrix.identity(2) X = matrix([[0, 1], [1, 0]]) return I2n + kronecker(state_matrix.transpose()*state_matrix, X - I2)
[docs]def grover_artifical(target_state_vector): r""" To accelerate the computation of the states, the alternative to ``grover_vanilla`` is to work directly on the vectors. INdeed, we know what the effects of each steps are, so we don't need to apply the gates we can simply change the vectors accordingly. For big dimensions, this is a way more efficient method. :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :returns: list[vector] -- List of states after each application of the diffusion operator (as well as the initial state). """ N = len(target_state_vector) n = log(N)/log(2) k_opt = round((pi/4)*sqrt(N)) V0 = vector([1]+[0]*(N-1)) H = matrix(field, [[1, 1], [1, -1]])/sqrt(2) hadamard_layer = kronecker_power(H, n) V = hadamard_layer * V0 end_loop_states = [matrix(V).transpose()] for k in range(k_opt): V = oracle_artificial(target_state_vector, V) V = diffusion_artificial(V) end_loop_states.append(matrix(V).transpose()) return end_loop_states
[docs]def oracle_artificial(target_state_vector, V): r""" Flips the coefficient of ``V`` corresponding to the state ``target_state_vector``. :param vector[int] target_state_vector: State searched by Grover's algorithm (only single item searches are supported for now). :param vector V: The running state in Grover's algorithm. :returns: vector -- ``V`` with the correct coefficient flipped. """ result = copy(V) for i in range(len(target_state_vector)): if target_state_vector[i] == 1: result[i] = -V[i] return result
[docs]def diffusion_artificial(V): r""" Performs the inversion about the mean for ``V``. :param vector V: The running state in Grover's algorithm . :returns: vector -- ``V`` Inverted about the mean. """ result = vector(field, [0]*len(V)) m = mean(V) for i in range(len(V)): result[i] = 2 * m - V[i] return result