Grover Search Algorithm

Amplitude Amplification

The amplitude amplification algorithm boosts the amplitude of being in a certain subspace of a Hilbert space[1]. Using the Grover operator, the state shifts towards the 'good' states—which are marked by the oracle—by some amount.

Many algorithms utilize amplitude amplification because it offers a quadratic speedup to the classical counterpart. The most famous application is the Grover search, for finding an item in an unordered list in \(O(\sqrt{N})\) uses of the Grover oracle. This is in contrast to the best classic counterpart, which goes over the entire list in \(O(N)\).

The optimal number of Grover iterations needed (which maximizes the probability to be in a good state) depends on the initial probability to be in a 'good' state. Although the probability is not always known, it is still possible to achieve quadratic speedup using randomization[1].

Special Case of Exactly Half Good States

Even though the amplitude amplification algorithm achieves a quadratic speedup, in one particular case it cannot find a valid solution due to how the search works. This happens when exactly half of the states are good states.

Consider the arithmetic oracle \((x + y) \% 2 == 1\). Note that exactly half of the possible values of (x, y) answer that oracle. (These are the states where the least significant bit of x is different from the least significant bit of y). Denote those "good states" as \(|g>\) and the "bad states" as \(|b>\), then start the algorithm with this state:

\(|\Psi> = \frac{1}{\sqrt2} (|g> + |b>)\)

The oracle changes the sign of the good states, so the state changes to this:

\(O|\Psi> = \frac{1}{\sqrt2} (-|g> + |b>)\)

The diffuser \(I-2|s><s|\) changes the state to this:

\(G|\Psi> = \frac{1}{\sqrt2} (|g> - |b>)\)

This means that each activation of the Grover operator does not change the probability of measuring a good state.

Syntax

Construct: construct_grover_model

Parameters:

• definitions: List[Tuple[str, RegisterUserInput]] - The definitions of the variables for the problem.
• expression: str – The expression for problem.
• num_reps: int – The number of repetitions of the grover layer in the model.

Example

SDKIDE

This snippet shows how to run a Grover problem using the SDK.

from classiq import (
    synthesize,
    execute,
    show,
    construct_grover_model,
    RegisterUserInput,
)
from classiq.execution import ExecutionDetails
from classiq import set_constraints, Constraints

grover_model = construct_grover_model(
    definitions=[
        ("a", RegisterUserInput(size=4)),
        ("b", RegisterUserInput(size=4, is_signed=True)),
    ],
    expression="a + b == 7 and a & b == 8",
    num_reps=4,
)
grover_model = set_constraints(grover_model, Constraints(max_width=25))
qprog = synthesize(grover_model)
show(qprog)
res = execute(qprog).result()
results = res[0].value
print(results.counts_of_multiple_outputs(["a", "b"]))

This example runs amplitude amplification using the Grover operator with the oracle for \(a + b == 7 \texttt{ and } a \& b == 8\).

Possible output:

{('1101', '0011'): 125,
 ('0001', '1111'): 111,
 ('1011', '0101'): 123,
 ('0111', '1001'): 129,
 ('0011', '1101'): 142,
 ('1001', '0111'): 133,
 ('0101', '1011'): 111,
 ('1111', '0001'): 126}

*The results should show a higher probability for the "good" solutions (eight in total).

You can also analyze the results to check their validity:

def parse_result(a_str, b_str):
    a = int(a_str[::-1], 2)
    b = int(b_str[::-1], 2) - 16
    print(f"a = {a}, b = {b}, expression = {a + b == 7 and a & b == 8}")


for key in results.counts_of_multiple_outputs(["a", "b"]).keys():
    parse_result(key[0], key[1])

The output for this check:

a = 11, b = -4, expression = True
a = 8, b = -1, expression = True
a = 13, b = -6, expression = True
a = 14, b = -7, expression = True
a = 12, b = -5, expression = True
a = 9, b = -2, expression = True
a = 10, b = -3, expression = True
a = 15, b = -8, expression = True

Indeed, you can see that the assignments that satisfy the expression are sampled.

To run a grover problem from the IDE Model Page select the Grover Search option from the Built In Apps folder in the Models pane:

By modifying the Grover operator editor pane and then clicking the Apply button, the Grover operator is populated in the Model Editor pane.

References

[1]G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation,” arXiv:quant-ph/0005055, vol. 305, pp. 53–74, 2002, doi: 10.1090/conm/305/05215.