Grover main

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.

grover.diffusion_artificial(V)

Performs the inversion about the mean for V.

Parameters:V (vector) – The running state in Grover’s algorithm . Returns:vector – V Inverted about the mean.

grover.grover(target_state_vector, verbose=False, file_name=None, use_precomputed=False, artificial=False)

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]

Parameters:

• target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now).
• verbose (bool) – If verbose then extra run information will be displayed in terminal.
• file_name (str) – File name for the registration of the Mermin evaluation for each step of the algorithm, in csv format.
• use_precomputed (bool) – for some states, the optimal Mermin polynomial has been precomputed, use this option to speed up the overall computation.
• artificial (bool) – 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.

grover.grover_artifical(target_state_vector)

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.

Parameters:target_state_vector (vector[int]) – 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).

grover.grover_evaluate(end_loop_states, M_opt, file_name)

Uses the previously found optimal mermin operator to evaluate the entanglement for each state in end_loop_states.

Parameters:

• end_loop_states (list[matrix]) – The states at the end of each loop, these are vectors transformed to column matrix.
• M_opt (matrix) – The optimal Mermin operator.
• file_name (str) – 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.

grover.grover_layers_kopt(target_state_vector)

Computes the circuit for Grover’s algorithm using the circuit format used for the run function from run_circuit.sage.

Parameters:target_state_vector (vector[int]) – 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.

grover.grover_optimize(target_state_vector, use_precomputed=False, verbose=False)

Computes the optimal Mermin operator to evaluate the entanglement in the Grover algorithm

Parameters:

• target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now).
• use_precomputed (bool) – For some states, the optimal Mermin polynomial has been precomputed, use this option to speed up the overall computation.
• verbose (bool) – If \(verbose\) then extra run information will be displayed in terminal.

Returns:

matrix – The optimal Mermin operator.

grover.grover_run(target_state_vector, artificial=False, verbose=False)

Runs a simulation of the grover algorithm.

Parameters:

• target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now).
• artificial (bool) – 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.
• verbose (bool) – If \(verbose\) then extra run information will be displayed in terminal.

Returns:

list[vectors] – the states at the end of each loop.

grover.grover_vanilla(target_state_vector, verbose=False)

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).

Parameters:

• target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now).
• verbose (bool) – 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).

grover.oracle(target_state_vector)

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]

Parameters:target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now). Returns:matrix – The matrix corresponding to the oracle.

grover.oracle_artificial(target_state_vector, V)

Flips the coefficient of V corresponding to the state target_state_vector.

Parameters:

• target_state_vector (vector[int]) – State searched by Grover’s algorithm (only single item searches are supported for now).
• V (vector) – The running state in Grover’s algorithm.

Returns:

vector – V with the correct coefficient flipped.

grover.target_state_ket_list_to_vector(target_state_ket)

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)

Parameters:target_state_ket (list[int]) – List of digit of the boolean expression of the sate looked for. Returns:vector – Vector corresponding to the target state.

grover.target_state_ket_string_to_vector(target_state_ket)

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)

Parameters:target_state_ket (str) – List of digit of the boolean expression of the searched sate. Returns:vector – Vector corresponding to the target state.

grover.target_state_ket_vector_to_string(target_state_ket)

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'

Parameters:target_state_ket (vector) – Vector corresponding to the target state. Returns:string – List of digit of the boolean expression of the searched sate.

grover.time_step(step_name, step_function, step_args, verbose=False)

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

Parameters:

• setp_name (str) – Name of the step, used for display.
• step_function (function) – Function to be timed.
• step_args (tuple) – Arguments of the function.
• verbose (bool) – If \(verbose\) then extra run information will be displayed in terminal.

Returns:

any – The output of step_function(*step_args)`.