Grover Operator

View on GitHub

The Grover operator is a unitary used in amplitude estimation and amplitude amplification algorithms [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.

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))

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

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

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

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