Skip to main content

View on GitHub

Open this notebook in GitHub to run it yourself
The Grover operator is a unitary used in amplitude estimation and amplitude amplification algorithms [1]. The Grover operator is given by Q=Q(A,χ)=−AS0A−1SχQ = Q(A,\chi) = -AS_0A^{-1}S_\chi where AA is a state preparation operator, A∣0⟩=∣ψ⟩A|0 \rangle= |\psi \rangle SχS_\chi marks good states and is called an oracle, Sχ∣x⟩={−∣x⟩if χ(x)=1−∣x⟩if χ(x)=0S_\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 S0S_0 is a reflection about the zero state. S0=I−2∣0⟩⟨0∣S_0 = I - 2|0\rangle\langle0| Function: grover_operator Arguments:
  • oracle: QCallable[QArray[QBit]]
  • Oracle representing SχS_{\chi}, accepting quantum state to apply on.
  • space_transform: QCallable[QArray[QBit]]
  • State preparation operator AA, 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))
Output:

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.xvars.ycountsprobabilitybitstringpredicate
0129890.4829101001True
1219560.4667970110True
201130.0063480100False
331130.0063480111False
420110.0053710010False
50290.0043951000False
62380.0039061110False
71070.0034180001False
82270.0034181010False
93270.0034181011False
100370.0034181100False
111150.0024410101False
121350.0024411101False
130040.0019530000False
143040.0019530011False
153330.0014651111False

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