Grover’s Algorithm#

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

Parameters:

argsQuantumVariable | QuantumArray | Sequence[QuantumVariable | QuantumArray]: The quantum variable, array, or collection thereof that defines the search space for Grover’s algorithm.
oracle_functionCallable: The quantum oracle function. This callable must accept args as its argument and apply a phase flip to tag the target winner state(s). Must uncompute any auxiliary QuantumVariables it uses. If exact is set to True, the oracle function must also support the keyword argument phase, which specifies how much the winner states are phase-shifted (in standard Grover, this would be \(\pi\)).
kwargsdict, optional: A dictionary containing keyword arguments to be passed to the oracle. The default is None.
iterationsint, optional: The exact amount of Grover iterations to perform.
winner_state_amountint, optional: If iterations is not specified, the optimal number of iterations is calculated using the established mathematical formula based on the number of winner states. The default assumption (if omitted) is 1.
exactbool, optional: If set to True, the exact version of Grover’s algorithm will be evaluated. For this, the correct winner_state_amount must be supplied, and the oracle must support the keyword argument phase to apply the calculated fractional phase shift.

Raises:

ValueError: If exact is set to True but winner_state_amount is not specified.
ZeroDivisionError: If winner_state_amount is 0.

Examples

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

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})
    res <<= prec
    return res

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 zero percent measurement probability.