# 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¶

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.