Grover Operator
The Grover operator is a unitary used in amplitude estimation and amplitude amplification algorithms [1]. The Grover operator is given by
where \(A\) is a state preparation operator,
\(S_\chi\) marks good states and is called an oracle,
and \(S_0\) is a reflection about the zero state.
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 *
from classiq.qmod.symbolic import logical_and
VAR_SIZE = 2
class GroverVars(QStruct):
x: QNum[VAR_SIZE]
y: QNum[VAR_SIZE]
@qfunc
def my_predicate(vars: Const[GroverVars], res: Permutable[QBit]) -> None:
res ^= logical_and((vars.x + vars.y < 9), ((vars.x * vars.y) % 4 == 1))
@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,
),
)
qmod_grover = create_model(
main, constraints=Constraints(max_width=15), out_file="grover_operator"
)
qprog = synthesize(qmod_grover)
And the next is a verification of the amplification of the solutions to the oracle:
result = execute(qprog).result_value()
result.parsed_counts
[{'vars': {'x': 3, 'y': 3}}: 981,
{'vars': {'x': 1, 'y': 1}}: 959,
{'vars': {'x': 1, 'y': 2}}: 12,
{'vars': {'x': 1, 'y': 0}}: 10,
{'vars': {'x': 3, 'y': 0}}: 10,
{'vars': {'x': 3, 'y': 1}}: 10,
{'vars': {'x': 0, 'y': 3}}: 10,
{'vars': {'x': 0, 'y': 0}}: 9,
{'vars': {'x': 3, 'y': 2}}: 8,
{'vars': {'x': 2, 'y': 0}}: 8,
{'vars': {'x': 2, 'y': 1}}: 7,
{'vars': {'x': 0, 'y': 1}}: 6,
{'vars': {'x': 1, 'y': 3}}: 5,
{'vars': {'x': 2, 'y': 2}}: 5,
{'vars': {'x': 2, 'y': 3}}: 4,
{'vars': {'x': 0, 'y': 2}}: 4]
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.