Grover Operator

View on GitHub Experiment in the IDE

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 (
    Constraints,
    Output,
    QArray,
    QBit,
    QCallable,
    QNum,
    allocate,
    bind,
    create_model,
    grover_operator,
    hadamard_transform,
    phase_oracle,
    power,
    qfunc,
)
from classiq.qmod.symbolic import logical_and

VAR_SIZE = 2


@qfunc
def my_predicate(x: QNum, y: QNum, res: QBit) -> None:
    res ^= logical_and((x + y < 9), ((x * y) % 4 == 1))


@qfunc
def main(x: Output[QNum[VAR_SIZE, False, 0]], y: Output[QNum[VAR_SIZE, False, 0]]):
    packed_vars = QArray("packed_vars")
    allocate(2 * VAR_SIZE, packed_vars)

    hadamard_transform(packed_vars)

    power(
        2,
        lambda: grover_operator(
            lambda vars: phase_oracle(
                predicate=lambda _vars, _res: my_predicate(
                    _vars[0:VAR_SIZE], _vars[VAR_SIZE : _vars.len], _res
                ),
                target=vars,
            ),
            lambda vars: hadamard_transform(vars),
            packed_vars,
        ),
    )
    bind(packed_vars, [x, y])


constraints = Constraints(max_width=15)
qmod_grover = create_model(main, constraints=constraints)

from classiq import synthesize, write_qmod

write_qmod(qmod_grover, "grover_operator")
qprog = synthesize(qmod_grover)

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

from classiq import execute

res = execute(qprog).result()[0].value
res.parsed_counts

[{'x': 3.0, 'y': 3.0}: 479,
 {'x': 1.0, 'y': 1.0}: 473,
 {'x': 1.0, 'y': 0.0}: 5,
 {'x': 1.0, 'y': 3.0}: 5,
 {'x': 2.0, 'y': 1.0}: 5,
 {'x': 3.0, 'y': 2.0}: 5,
 {'x': 2.0, 'y': 0.0}: 4,
 {'x': 0.0, 'y': 2.0}: 4,
 {'x': 3.0, 'y': 1.0}: 4,
 {'x': 0.0, 'y': 0.0}: 4,
 {'x': 0.0, 'y': 3.0}: 3,
 {'x': 1.0, 'y': 2.0}: 3,
 {'x': 2.0, 'y': 3.0}: 2,
 {'x': 0.0, 'y': 1.0}: 2,
 {'x': 2.0, 'y': 2.0}: 1,
 {'x': 3.0, 'y': 0.0}: 1]

from itertools import product

for x, y in product(range(2**VAR_SIZE), range(2**VAR_SIZE)):
    print(x, y, (x + y < 9) and ((x * y) % 4 == 1))

0 0 False
0 1 False
0 2 False
0 3 False
1 0 False
1 1 True
1 2 False
1 3 False
2 0 False
2 1 False
2 2 False
2 3 False
3 0 False
3 1 False
3 2 False
3 3 True

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.