Grover Operator¶
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_example")
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': 1.0, 'y': 1.0}: 478, {'x': 3.0, 'y': 3.0}: 475, {'x': 2.0, 'y': 2.0}: 7, {'x': 3.0, 'y': 0.0}: 6, {'x': 2.0, 'y': 0.0}: 6, {'x': 0.0, 'y': 2.0}: 5, {'x': 0.0, 'y': 1.0}: 5, {'x': 1.0, 'y': 0.0}: 4, {'x': 0.0, 'y': 3.0}: 4, {'x': 3.0, 'y': 1.0}: 4, {'x': 1.0, 'y': 2.0}: 2, {'x': 3.0, 'y': 2.0}: 1, {'x': 0.0, 'y': 0.0}: 1, {'x': 2.0, 'y': 3.0}: 1, {'x': 1.0, 'y': 3.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