Grover’s Algorithm#

grovers_alg(qv_list, oracle_function, kwargs={}, iterations=0, winner_state_amount=None, exact=False)[source]#

Applies Grover’s algorithm to a given oracle (in the form of a Python function).

Parameters

qv_listQuantumVariable or list[QuantumVariable]: A (list of) QuantumVariables on which to execute Grover’s algorithm.
oracle_functionfunction: A Python function tagging the winner states.
kwargsdict, optional: A dictionary containing keyword arguments for the oracle. The default is {}.
iterationsint, optional: The amount of Grover iterations to perfrom.
winner_state_amountint, optional: If not given the amount of iterations, the established formula will be used based on the amount of winner states. The default is 1.
exactbool, optional: If set to True, the exact version <https://arxiv.org/pdf/quant-ph/0106071.pdf> of Grover’s algorithm will be evaluated. For this, the correct winner_state_amount has to be supplied and the oracle has to support the keyword argument phase which specifies how much the winner states are phaseshifted (in standard Grover this would be \(\pi\)).

Raises

Exception: Applied oracle introducing new QuantumVariables without uncomputing/deleting

Examples

We construct an oracle that tags the states -3 and 2 on two QuantumFloats and apply Grover’s algorithm to it.

from qrisp import QuantumFloat

#Create list of QuantumFloats
qf_list = [QuantumFloat(2, signed = True), QuantumFloat(2, signed = True)]

from qrisp.grover import tag_state, grovers_alg

def test_oracle(qf_list):

    tag_dic = {qf_list[0] : -3, qf_list[1] : 2}
    tag_state(tag_dic)

grovers_alg(qf_list, test_oracle)

>>> from qrisp.misc import multi_measurement
>>> print(multi_measurement(qf_list))
{(-3, 2): 0.9966, (0, 0): 0.0001, (0, 1): 0.0001, (0, 2): 0.0001, (0, 3): 0.0001,
(0, -4): 0.0001, (0, -3): 0.0001, (0, -2): 0.0001, (0, -1): 0.0001, (1, 0): 0.0001,
(1, 1): 0.0001, (1, 2): 0.0001, (1, 3): 0.0001, (1, -4): 0.0001, (1, -3): 0.0001,
(1, -2): 0.0001, (1, -1): 0.0001, (2, 0): 0.0001, (2, 1): 0.0001, (2, 2): 0.0001,
(2, 3): 0.0001, (2, -4): 0.0001, (2, -3): 0.0001, (2, -2): 0.0001, (2, -1): 0.0001,
(3, 0): 0.0001, (3, 1): 0.0001, (3, 2): 0.0001, (3, 3): 0.0001, (3, -4): 0.0001,
(3, -3): 0.0001, (3, -2): 0.0001, (3, -1): 0.0001, (-4, 0): 0.0001, (-4, 1): 0.0001,
 (-4, 2): 0.0001, (-4, 3): 0.0001, (-4, -4): 0.0001, (-4, -3): 0.0001,
 (-4, -2): 0.0001, (-4, -1): 0.0001, (-3, 0): 0.0001, (-3, 1): 0.0001,
 (-3, 3): 0.0001, (-3, -4): 0.0001, (-3, -3): 0.0001, (-3, -2): 0.0001,
 (-3, -1): 0.0001, (-2, 0): 0.0001, (-2, 1): 0.0001, (-2, 2): 0.0001,
 (-2, 3): 0.0001, (-2, -4): 0.0001, (-2, -3): 0.0001, (-2, -2): 0.0001,
 (-2, -1): 0.0001, (-1, 0): 0.0001, (-1, 1): 0.0001, (-1, 2): 0.0001,
 (-1, 3): 0.0001, (-1, -4): 0.0001, (-1, -3): 0.0001, (-1, -2): 0.0001,
 (-1, -1): 0.0001}

Exact Grovers Algorithm

In the next example, we will showcase the exact functionality. For this we create an oracle, which tags all the states of a QuantumVariable, that contain 3 ones and 2 zeros.

To count the amount of ones we use quantum phase estimation on the operator

\[U = \text{exp}\left(\frac{i 2 \pi}{2^k} \sum_{i = 0}^{n-1} ( 1 - \sigma_{z}^i )\right)\]

from qrisp import QPE, p, QuantumVariable, lifted
from qrisp.grover import grovers_alg, tag_state
import numpy as np

def U(qv, prec = None, iter = 1):
    for i in range(qv.size):
        p(iter*2*np.pi/2**prec, qv[i])

@lifted
def count_ones(qv):
    prec = int(np.ceil(np.log2(qv.size+1)))
    res = QPE(qv, U, precision = prec, iter_spec = True, kwargs = {"prec" : prec})
    return res<<prec

Quick test:

>>> qv = QuantumVariable(5)
>>> qv[:] = {"11000" : 1, "11010" : 1, "11110" : 1}
>>> count_qf = count_ones(qv)
>>> count_qf.qs.statevector()
sqrt(3)*(|11000>*|2> + |11010>*|3> + |11110>*|4>)/3

We now define the oracle

def counting_oracle(qv, phase = np.pi, k = 1):

    count_qf = count_ones(qv)

    tag_state({count_qf : k}, phase = phase)

    count_qf.uncompute()

And evaluate Grover’s algorithm

n = 5
k = 3
qv = QuantumVariable(n)

import math

grovers_alg(qv, counting_oracle, exact = True, winner_state_amount = math.comb(n,k), kwargs = {"k" : k})  # noqa

>>> print(qv)
{'11100': 0.1,
 '11010': 0.1,
 '10110': 0.1,
 '01110': 0.1,
 '11001': 0.1,
 '10101': 0.1,
 '01101': 0.1,
 '10011': 0.1,
 '01011': 0.1,
 '00111': 0.1}

We see that contrary to regular Grover’s algorithm, the states which have not been tagged by the oracle have 0 percent measurement probability.