跳转至

Grover

QuICT.algorithm.quantum_algorithm.Grover 

Grover(targ_bit_len: int, oracle: CompositeGate)

Grover's algorithm for solving unstructured search problem.

References

[1]: Nielsen, M.A., & Chuang, I.L. (2010). Quantum Computation and Quantum Information, p.248.

[2]: Brassard, Gilles, Peter Hoyer, Michele Mosca, and Alain Tapp. “Quantum Amplitude Amplification and Estimation,” 305:53-74, 2002. https://doi.org/10.1090/conm/305/05215.

Parameters:

  • targ_bit_len (int) –

    Length of the target bit string(s).

  • oracle (CompositeGate) –

    The oracle that flip the targets' phase.

Source code in QuICT/algorithm/quantum_algorithm/grover/grover.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def __init__(
    self,
    targ_bit_len: int,
    oracle: CompositeGate
):
    """
    Args:
        targ_bit_len (int): Length of the target bit string(s).
        oracle (CompositeGate): The oracle that flip the targets' phase.
    """
    if max(oracle.qubits) < targ_bit_len - 1:
        raise ValueError("Oracle's application space smaller than search space.")

    self.targ_bit_len = targ_bit_len
    self.oracle = oracle
    self.amp_alg = AmplitudeAmplification(work_bits=self.targ_bit_len, targ_phase_flip=self.oracle)

circuit 

circuit(iteration: int, include_measure: bool = False) -> Circuit

Grover search for f with custom oracle

Parameters:

  • iteration (int) –

    Number of grover iteration in the circuit.

  • include_measure (bool, default: False ) –

    When set to True the, output will have measurement gates on working qubits.

Returns: Circuit: The grover search circuit.

Source code in QuICT/algorithm/quantum_algorithm/grover/grover.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def circuit(
    self,
    iteration: int,
    include_measure: bool = False
) -> Circuit:
    """ Grover search for f with custom oracle

    Args:
        iteration (int): Number of grover iteration in the circuit.
        include_measure (bool): When set to `True` the, output will have measurement gates on working qubits.
    Returns:
        Circuit: The grover search circuit.
    """

    amp_circ = self.amp_alg.circuit(iteration=iteration)

    if include_measure:
        for i in range(self.targ_bit_len):
            Measure | amp_circ(i)

    return amp_circ

run 

run(n_solution: int, backend=StateVectorSimulator(), shots: int = 1) -> Dict[str, int]

With given number of solutions, construct the grover circuit and run.

Parameters:

  • n_solution (int) –

    Number of solution.

  • backend (Any, default: StateVectorSimulator() ) –

    Device to run the quantum algorithm.

  • shots (int, default: 1 ) –

    Number of experiments to run.

Source code in QuICT/algorithm/quantum_algorithm/grover/grover.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def run(
    self,
    n_solution: int,
    backend=StateVectorSimulator(),
    shots: int = 1
) -> Dict[str, int]:
    """ With given number of solutions, construct the grover circuit and run.

    Args:
        n_solution (int): Number of solution.
        backend (Any): Device to run the quantum algorithm.
        shots (int): Number of experiments to run.
    """

    it_opt = self._grover_it_num(self.targ_bit_len, n_solution)
    logger.info(f"Building grover circuit with optimal iteration num: {it_opt}.")

    return self.amp_alg.run(iteration=it_opt, backend=backend, shots=shots)

run_iterative 

run_iterative(solution_checker: Callable[[str], bool], backend=StateVectorSimulator()) -> Union[Tuple[str, int], None]

Run the grover search via a gradually-shrink-search-space strategy. Use this method if the number of solution is unknown.

Parameters:

  • solution_checker (Callable[[str], bool]) –

    A callable that given a string as input, output if it's a valid solution.

  • backend (Any, default: StateVectorSimulator() ) –

    Device to run the quantum algorithm.

Source code in QuICT/algorithm/quantum_algorithm/grover/grover.py 
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
def run_iterative(
    self,
    solution_checker: Callable[[str], bool],
    backend=StateVectorSimulator()
) -> Union[Tuple[str, int], None]:
    """ Run the grover search via a gradually-shrink-search-space strategy. Use this method if the
        number of solution is unknown.

    Args:
        solution_checker (Callable[[str], bool]): A callable that given a string as input, output
            if it's a valid solution.
        backend (Any): Device to run the quantum algorithm.
    """
    n_sol_init = 1 << self.targ_bit_len
    while n_sol_init > 0:
        # get current grover iteration number
        it_num = self._grover_it_num(self.targ_bit_len, n_sol_init)
        logger.info(f"Trying with number of solution : {n_sol_init} with grover iteration = {it_num}.")
        # run qaa
        res_dict = self.amp_alg.run(iteration=it_num, backend=backend, shots=1)
        for key in res_dict:
            if solution_checker(key):
                logger.info(f"Successfully found solution: {key}.")
                return key, it_num
        # update next guess
        n_sol_init = int(n_sol_init / ALPHA)
    logger.info(f"Fail finding target with grover.")

    return None