> ## Documentation Index
> Fetch the complete documentation index at: https://prod-mint.classiq.io/llms.txt
> Use this file to discover all available pages before exploring further.

# Grover Operator

<Card title="View on GitHub" icon="github" href="https://github.com/Classiq/classiq-library/blob/main/functions/qmod_library_reference/classiq_open_library/grover_operator/grover_operator.ipynb">
  Open this notebook in GitHub to run it yourself
</Card>

The Grover operator is a unitary used in amplitude estimation and amplitude
amplification algorithms [\[1\]](#1).

The Grover operator is given by

$$
Q = Q(A,\chi) = -AS_0A^{-1}S_\chi
$$

where $A$ is a state preparation operator,

$$
A|0 \rangle= |\psi \rangle
$$

$S_\chi$ marks good states and is called an oracle,

$$
S_\chi\lvert x \rangle = 
\begin{cases} 
-\lvert x \rangle & \text{if } \chi(x) = 1 \\
 \phantom{-} \lvert x \rangle & \text{if } \chi(x) = 0 
\end{cases}
$$

and $S_0$ is a reflection about the zero state.

$$
S_0 = I - 2|0\rangle\langle0|
$$

Function: `grover_operator`

Arguments:

* `oracle: QCallable[QArray[QBit]]`

* Oracle representing $S_{\chi}$, accepting quantum state to apply on.

* `space_transform: QCallable[QArray[QBit]]`

* State preparation operator $A$, accepting quantum state to apply on.

* `packed_vars: QArray[QBit]`

* Packed form of the variable to apply the grover operator on.

#

## Example

The following example implements a grover search algorithm using the grover operator for a specific oracle, with a uniform superposition over the search space.

The circuit starts with a uniform superposition on the search space, followed by 2 applications of the grover operator.

```python theme={null}
from classiq import *

VAR_SIZE = 2


class GroverVars(QStruct):
    x: QNum[VAR_SIZE]
    y: QNum[VAR_SIZE]


@qperm
def my_predicate(vars: Const[GroverVars], res: QBit) -> None:
    res ^= (vars.x + vars.y < 4) & ((vars.x * vars.y) % 4 == 2)


@qfunc
def main(vars: Output[GroverVars]):
    allocate(vars)

    hadamard_transform(vars)

    power(
        2,
        lambda: grover_operator(
            lambda vars: phase_oracle(
                predicate=my_predicate,
                target=vars,
            ),
            hadamard_transform,
            vars,
        ),
    )


qprog = synthesize(main, auto_show=True, constraints=Constraints(max_width=15))
```

<Info>
  **Output:**

  ```

  Quantum program link: https://platform.classiq.io/circuit/3BcvqlkqBQJ2ZdIS43PKEgWo0I9
    

  ```
</Info>

And the next is a verification of the amplification of the solutions to the oracle:

```python theme={null}
result = execute(qprog).result_value()
df = result.dataframe
df["predicate"] = (df["vars.x"] + df["vars.y"] < 4) & (
    (df["vars.x"] * df["vars.y"]) % 4 == 2
)
df
```

|    | vars.x | vars.y | counts | probability | bitstring | predicate |
| -- | ------ | ------ | ------ | ----------- | --------- | --------- |
| 0  | 1      | 2      | 989    | 0.482910    | 1001      | True      |
| 1  | 2      | 1      | 956    | 0.466797    | 0110      | True      |
| 2  | 0      | 1      | 13     | 0.006348    | 0100      | False     |
| 3  | 3      | 1      | 13     | 0.006348    | 0111      | False     |
| 4  | 2      | 0      | 11     | 0.005371    | 0010      | False     |
| 5  | 0      | 2      | 9      | 0.004395    | 1000      | False     |
| 6  | 2      | 3      | 8      | 0.003906    | 1110      | False     |
| 7  | 1      | 0      | 7      | 0.003418    | 0001      | False     |
| 8  | 2      | 2      | 7      | 0.003418    | 1010      | False     |
| 9  | 3      | 2      | 7      | 0.003418    | 1011      | False     |
| 10 | 0      | 3      | 7      | 0.003418    | 1100      | False     |
| 11 | 1      | 1      | 5      | 0.002441    | 0101      | False     |
| 12 | 1      | 3      | 5      | 0.002441    | 1101      | False     |
| 13 | 0      | 0      | 4      | 0.001953    | 0000      | False     |
| 14 | 3      | 0      | 4      | 0.001953    | 0011      | False     |
| 15 | 3      | 3      | 3      | 0.001465    | 1111      | False     |

## References

<a name="1">\[1]</a> 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.