# 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 select the Grover Search option from the Built-in Algorithms pane. . This will populate the Synthesis Model pane with a grover model, as can be seen in the following snippet.

<!-- prettier-ignore -->
??? note "qmod"
json
{
"functions": [
{
"name": "expr_predicate",
"port_declarations": {
"a": {
"name": "a",
"size": {
"expr": "4"
},
"quantum_type": {
"kind": "qint"
},
"direction": "inout"
},
"b": {
"name": "b",
"size": {
"expr": "4"
},
"quantum_type": {
"kind": "qint"
},
"direction": "inout"
},
"res": {
"name": "res",
"size": {
"expr": "1"
},
"direction": "inout"
}
},
"body": [
{
"expr_str": "a + b == 7 and a & b == 8",
"result_var": {
"name": "res"
},
"inplace_result": true
}
]
},
{
"name": "main",
"port_declarations": {
"a": {
"name": "a",
"size": {
"expr": "4"
},
"quantum_type": {
"kind": "qint"
},
"direction": "output"
},
"b": {
"name": "b",
"size": {
"expr": "4"
},
"quantum_type": {
"kind": "qint"
},
"direction": "output"
}
},
"body": [
{
"function": "grover_search",
"params": {
"num_qubits": {
"expr": "8"
},
"reps": {
"expr": "4"
}
},
"function_params": {},
"outputs": {
"gsq": {
"name": "gsq"
}
},
"operands": {
"oracle_op": {
"body": [
{
"function": "simple_oracle",
"function_params": {},
"inouts": {
"target": {
"name": "oq"
}
},
"operands": {
"predicate": {
"body": [
{
"function": "expr_predicate",
"function_params": {},
"inouts": {
"a": {
"name": "vars",
"start": {
"expr": "0"
},
"end": {
"expr": "4"
}
},
"b": {
"name": "vars",
"start": {
"expr": "4"
},
"end": {
"expr": "8"
}
},
"res": {
"name": "result"
}
}
}
]
}
}
}
]
}
}
},
{
"function": "split",
"params": {
"out1_size": {
"expr": "4"
},
"out2_size": {
"expr": "4"
}
},
"function_params": {},
"inputs": {
"in": {
"name": "gsq"
}
},
"outputs": {
"out1": {
"name": "a"
},
"out2": {
"name": "b"
}
}
}
],
"local_handles": [
{
"name": "gsq"
}
]
}
],
"classical_execution_code": "\nresult = sample()\nsave({'result': result})\n",
"constraints": {
"max_width": 25
}
}



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