pyqpanda_alg.QFinance.grover

Module Contents

Classes

Grover

This class provides a framework for Grover Search algorithm [1].

GroverAdaptiveSearch

This class provides a framework for Grover Adaptive Search [2].

Functions

iter_num(q_num, sol_num)

Calculate the optimal number of iterations in Grover search.

iter_analysis(q_num, sol_num[, iternum])

Calculate the amplification probability and rotation angle for given amplitude

amp_operator([q_input, q_flip, q_zero, in_operator, ...])

Construct complete Grover amplitude amplification operator.

mark_data_reflection([qubits, mark_data])

Can be used to construct a phase flip operator for given target states.

class pyqpanda_alg.QFinance.grover.Grover(in_operator=None, flip_operator=None, zero_flip=None, mark_data=None, amplify_operator=None)

This class provides a framework for Grover Search algorithm [1].

Parameters

in_operator : callable f(qubits)

Operator/Circuit of the initial search state for the algorithm, default Hadamards.

flip_operator : callable f(qubits)

Operator/Circuit of marking the good states by phase-flip. Default doing a pauli-Z gate at the last qubit.

zero_flip : callable f(qubits)

Operator/Circuit of reflects 0s by phase-flip. Default doing a zero-controled pauli-Z gate on qubits.

mark_data : str, list[str]

Marked target state. Default None. Only used when simply marking a known query state, as the designed flip_operator part.

amplify_operator : callable f(qubits)

Constructed complete Grover amplitude amplification operator circuit. Default None. For users’ special designed amplitude amplification operator.

References

[1] L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

cir(q_input=None, q_flip=None, q_zero=None, iternum: int = 1)

Get full circuit of Grover search.

Parameters

q_input : QVec

Target qubit(s) for in_operator (initial preparation circuit). Using Hadamard gates to create the uniform superposition at the beginning most of time. Although in most simple cases it includes the full workspace qubits, auxiliary qubits can be excluded when dealing with some complex problems.

q_flip : QVec

Target qubit(s) for flip_operator.

q_zero : QVec

Target qubit(s) for zero_flip.

iternum : int

The number of iterations. In another word number of repetition of applying the Grover operator.

Returns

circuit : QCircuit

Full quantum circuit for given Grover search.

Examples

An example for implementing an Grover search for state where q_0 and q_1 is 1.

>>> import pyqpanda as pq
>>> from pyqpanda_alg.QFinance import grover
>>> m = pq.CPUQVM()
>>> m.initQVM()
>>> q_state = m.qAlloc_many(3)
>>> def mark(qubits):
>>>     cir = pq.QCircuit()
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     cir << pq.Z(qubits[2])
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     return cir
>>> demo_search = grover.Grover(flip_operator=mark)
>>> prog = pq.QProg()
>>> prog << demo_search.cir(q_input=q_state[:2], q_flip=q_state, q_zero=q_state[:2], iternum=1)
>>> res = m.prob_run_dict(prog, q_state[:2])
>>> print(res)
>>> print(prog)
{'00': 0.0, '01': 0.0, '10': 0.0, '11': 1.0000000000000004}
          ┌─┐             ┌─┐ ┌─┐     ┌─┐ ┌─┐
q_0:  |0>─┤H├ ─■─ ─── ─■─ ┤H├ ┤X├ ─■─ ┤X├ ┤H├
          ├─┤  │       │  ├─┤ ├─┤ ┌┴┐ ├─┤ ├─┤
q_1:  |0>─┤H├ ─■─ ─── ─■─ ┤H├ ┤X├ ┤Z├ ┤X├ ┤H├
          └─┘ ┌┴┐ ┌─┐ ┌┴┐ └─┘ └─┘ └─┘ └─┘ └─┘
q_2:  |0>──── ┤X├ ┤Z├ ┤X├ ─── ─── ─── ─── ───
              └─┘ └─┘ └─┘
pyqpanda_alg.QFinance.grover.iter_num(q_num, sol_num)

Calculate the optimal number of iterations in Grover search.

Parameters

q_num : int

The number of qubits in the search space. Search space size: \(N = 2 ^ {\text {q_num}}\).

sol_num : int

Number of target solution states.

Returns

num : The optimal number of iterations in Grover search.

Examples

An example for the case we show in the Grover search circuit. And we know there is only one solution to be found. And total 2 qubits for the search space.

>>> import pyqpanda as pq
>>> from pyqpanda_alg.QFinance import grover
>>> m = pq.CPUQVM()
>>> m.initQVM()
>>> q_state = m.qAlloc_many(3)
>>> def mark(qubits):
>>>     cir = pq.QCircuit()
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     cir << pq.Z(qubits[2])
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     return cir
>>> demo_search = grover.Grover(flip_operator=mark)
>>> iter_num = grover.iter_num(q_num=len(q_state), sol_num=2)
>>> print('best iter num: ', iter_num)
best iter num:  1
pyqpanda_alg.QFinance.grover.iter_analysis(q_num, sol_num, iternum=1)

Calculate the amplification probability and rotation angle for given amplitude amplification iteration number.

Parameters

q_num : int

The number of qubits in the search space. Search space size: \(N = 2 ^ {\text {q_num}}\).

sol_num : int

Number of target solution states.

iternum : int

Given number of iteration.

Returns

prob, theta : (float, float)

The amplification probability and rotation angle for given iteration.

Examples

An example for the case we show in the Grover search circuit. And we know there is only one solution to be found. And total 2 qubits for the search space.

>>> import pyqpanda as pq
>>> from pyqpanda_alg.QFinance import grover
>>> m = pq.CPUQVM()
>>> m.initQVM()
>>> q_state = m.qAlloc_many(3)
>>> def mark(qubits):
>>>     cir = pq.QCircuit()
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     cir << pq.Z(qubits[2])
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     return cir
>>> demo_search = grover.Grover(flip_operator=mark)
>>> prob, angle = grover.iter_analysis(q_num=len(q_state), sol_num=2, iternum=1)
>>> print('prob for getting one of the solution with given iter num 1:', prob)
>>> prob, angle = grover.iter_analysis(q_num=len(q_state), sol_num=2, iternum=2)
>>> print('prob for getting one of the solution with given iter num 2:', prob)
prob for getting one of the solution with given iter num 1: 1.0
prob for getting one of the solution with given iter num 2: 0.24999999999999956
pyqpanda_alg.QFinance.grover.amp_operator(q_input=None, q_flip=None, q_zero=None, in_operator=None, flip_operator=None, zero_flip=None)

Construct complete Grover amplitude amplification operator. Can be part of Grover/Quantum Count/QAE and other amplitude amplification related algorithm.

Parameters

q_input : QVec

Target qubit(s) for in_operator (initial preparation circuit). Using Hadamard gates to create the uniform superposition at the beginning most of time. Although in most simple cases it includes the full workspace qubits, auxiliary qubits can be excluded when dealing with some complex problems.

q_flip : QVec

Target qubit(s) for flip_operator.

q_zero : QVec

Target qubit(s) for zero_flip.

in_operator : callable f(qubits)

Operator/Circuit of the initial search state for the algorithm, default Hadamards.

flip_operator : callable f(qubits)

Operator/Circuit of marking the good states by phase-flip. Default doing a pauli-Z gate at the last qubit.

zero_flip : callable f(qubits)

Operator/Circuit of reflects 0s by phase-flip. Default doing a zero-controled pauli-Z gate on qubits.

Returns

circuit : QCircuit

Amplitude amplification operator.

Examples

An example for constucting a amplitude amplification operator used in the case we show in the Grover search circuit.

>>> import pyqpanda as pq
>>> from pyqpanda_alg.QFinance import grover
>>> m = pq.CPUQVM()
>>> m.initQVM()
>>> q_state = m.qAlloc_many(3)
>>> def mark(qubits):
>>>     cir = pq.QCircuit()
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     cir << pq.Z(qubits[2])
>>>     cir << pq.Toffoli(qubits[0], qubits[1], qubits[2])
>>>     return cir
>>> print(grover.amp_operator(q_input=q_state[:2], q_flip=q_state, q_zero=q_state[:2], flip_operator=mark))
                      ┌─┐ ┌─┐     ┌─┐ ┌─┐
q_0:  |0>──■─ ─── ─■─ ┤H├ ┤X├ ─■─ ┤X├ ┤H├
           │       │  ├─┤ ├─┤ ┌┴┐ ├─┤ ├─┤
q_1:  |0>──■─ ─── ─■─ ┤H├ ┤X├ ┤Z├ ┤X├ ┤H├
          ┌┴┐ ┌─┐ ┌┴┐ └─┘ └─┘ └─┘ └─┘ └─┘
q_2:  |0>─┤X├ ┤Z├ ┤X├ ─── ─── ─── ─── ───
          └─┘ └─┘ └─┘
pyqpanda_alg.QFinance.grover.mark_data_reflection(qubits: list = None, mark_data=None)

Can be used to construct a phase flip operator for given target states.

Parameters

qubits : QVec

Target qubit(s) for flip_operator.

mark_data : str, list[str]

Marked target state(s).

Returns

flip_operator : QCircuit

A phase flip operator for given target states

Examples

An example for searching ‘101’ and ‘001’ using the flip operator given by this function.

>>> import pyqpanda as pq
>>> from pyqpanda_alg.QFinance import grover
>>> m = pq.CPUQVM()
>>> m.initQVM()
>>> q_state = m.qAlloc_many(3)
>>> def mark(qubits):
>>>     return grover.mark_data_reflection(qubits=qubits, mark_data=['101', '001'])
>>> demo_search = grover.Grover(flip_operator=mark)
>>> prog = pq.QProg()
>>> prog << demo_search.cir(q_input=q_state)
>>> res = m.prob_run_dict(prog, q_state)
>>> print(res)
{'000': 0.0, '001': 0.5000000000000002, '010': 0.0, '011': 0.0, '100': 0.0, '101': 0.5000000000000002, '110': 0.0, '111': 0.0}
class pyqpanda_alg.QFinance.grover.GroverAdaptiveSearch(init_value, n_index, init_circuit=None, oracle_circuit=None)

This class provides a framework for Grover Adaptive Search [2].

Parameters

init_value : float

The given initial value of the optimization function.

n_index : int

The number of qubits in the search space. Search space size: N = 2 ** q_num.

init_circuit : callable f(qubits)

Operator/Circuit of the initial search state for the algorithm, default Hadamards.

oracle_circuit : callable f(qubits, value)

Operator/Circuit of marking the better states by phase-flip. Default doing a pauli-Z gate at the last qubit.

References

[2] A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

run(continue_times: int = 3, n_value_function=None, value_function=None, rotation_change='random', process_show=False)

Run the Grover Adaptive Search algorithm to find the minimum.

Parameters

continue_times : int

The maximum number of repeated searches at the current optimal point.

n_value_function : callable f(value)

Function for computing the number of qubits for marking the better states at current best value, variable qubits not included.

value_function : callable f(var_array)

Function for computing the problem value of given varriables array(str given as qpanda state).

rotation_change : str{'random', 'increase'}, optional

The method to get the number of Grover iterations for each search of a search cycle.

  • random : The number of Grover iterations for each search is randomly obtained from a

increasing interval. (Default)

  • increase : The number of Grover iterations for each search is increasing.

process_show : bool

Set to True to print the detail during search.

Returns

minimum_indexes, minimum_res : ( list[list[int]], float)

The optimization result including the solution array and the optimal value.

Examples

An example for minimization of quadratic binary function: x0 * x1 + x0 - x1.

>>> from pyqpanda_alg.QFinance import grover
>>> import numpy as np
>>> import pyqpanda as pq
>>> # flip if x0 * x1 + x0 - x1 - current_min < 0
>>> def flip_oracle_function(q_index_value, current_min):
>>>     q_index = q_index_value[:2]
>>>     q_value = q_index_value[2:]
>>>     n_value = len(q_value)
>>>     factor = np.pi * 2 ** (1 - n_value)
>>>     cal_cir = pq.QCircuit()
>>>     cal_cir << pq.H(q_value)
>>>     for i, q_i in enumerate(q_value):
>>>         cal_cir << pq.U1(q_i, factor * 2 ** i).control(q_index)
>>>         cal_cir << pq.U1(q_i, factor * 2 ** i).control(q_index[0])
>>>         cal_cir << pq.U1(q_i, -factor * 2 ** i).control(q_index[1])
>>>         cal_cir << pq.U1(q_i, factor * 2 ** i * (-current_min))
>>>     cal_cir << pq.QFT(q_value).dagger()
>>>     return cal_cir
>>> demo_search = grover.GroverAdaptiveSearch(init_value=0, n_index=2, oracle_circuit=flip_oracle_function)
>>> def n_value_function(current_min):
>>>     n_value = 2 if current_min == 0 else 3
>>>     return n_value
>>> def value_function(var_array):
>>>     var_array = list(map(int, var_array))[::-1]
>>>     value = var_array[0] * var_array[1] + var_array[0] - var_array[1]
>>>     return value
>>> res = demo_search.run(continue_times=3,
>>>                       n_value_function=n_value_function,
>>>                       value_function=value_function,
>>>                       process_show=True)
>>> print(res)
======searching 1 ,rotation = 1 ======
minimum Key Again:  00
minimum Value No Change:  0
======searching 2 ,rotation = 1 ======
Current minimum Key:  10
Current minimum Value:  -1
======searching 1 ,rotation = 1 ======
minimum Key Again:  10
minimum Value No Change:  -1
======searching 2 ,rotation = 1 ======
======searching 3 ,rotation = 1 ======
rotations:  5
([[0, 1]], -1)