Skip to content

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,

alt text

and \(S_0\) flips around the zero state and is called the diffuser,

\[ S_0 = I - 2|0\rangle\langle0| \]

By default, the state preparation used is the uniform superposition by applying Hadamard on all inputs (\(A = H^{\bigotimes n}\)). The state_preparation_params may be either the built-in state preparation or any user-defined function. If you choose user-defined, pass its name in the state_preparation field. The oracle may is given by any of the possible oracle types. Make sure to match the arguments of the oracle and state-preparation operations in sizes and names. Alternatively, if the state preparation operation has a single argument, it will connect to the oracles argument by some given order, even if the names do not match (but assuming the total number of qubits does).

Syntax

Function: GroverOperator

Parameters:

Example 1

The following example generates a Grover operator for a specific oracle, with the default state preparation. The functional blocks include an arithmetic oracle, state preparation, a diffuser, and finally the global phase, as can be seen in the image below.

{
  "functions": [
    {
      "name": "main",
      "body": [
        {
          "function": "GroverOperator",
          "function_params": {
            "oracle_params": {
              "expression": "(a + b + (c & 6)) % 4 | 4 & c  == 4",
              "definitions": {
                "a": { "size": 2 },
                "b": { "size": 2 },
                "c": { "size": 3 }
              },
              "uncomputation_method": "optimized",
              "qubit_count": 16
            },
            "state_preparation_params": null
          }
        }
      ]
    }
  ]
}

from classiq import Model, RegisterUserInput
from classiq.builtin_functions import ArithmeticOracle, GroverOperator
from classiq import synthesize, show

oracle_params = ArithmeticOracle(
    expression="(a + b + (c & 6)) % 4 | 4 & c  == 4",
    definitions=dict(
        a=RegisterUserInput(size=2),
        b=RegisterUserInput(size=2),
        c=RegisterUserInput(size=3),
    ),
    uncomputation_method="optimized",
    qubit_count=16,
)
grover_params = GroverOperator(oracle_params=oracle_params)

m = Model()
m.GroverOperator(grover_params)
model = m.get_model()

qprog = synthesize(model)
show(qprog)

zoom out circuit

Example 2

The following example shows how to use custom state preparation. See User-defined Functions.

{
  "functions": [
    {
      "name": "my_state_preparation",
      "implementations": [{
        "serialized_circuit": "OPENQASM 2.0;\ninclude \"qelib1.inc\";\nqreg q[3];\nx q[0];\nh q[1];\nh q[2];"
      }],
      "register_mapping": {
        "input_registers": [{"name": "IN", "qubits": [0, 1, 2]}],
        "output_registers": [{"name": "OUT", "qubits": [0, 1, 2]}]
      }
    },
    {
      "name": "main",
      "body": [
        {
          "function": "GroverOperator",
          "function_params": {
            "oracle_params": {
              "expression": "a + b + c == 1",
              "definitions": {
                "a": { "size": 1 },
                "b": { "size": 1 },
                "c": { "size": 1 }
              },
              "uncomputation_method": "naive"
            },
            "state_preparation": "my_state_preparation",
            "state_preparation_params": {
              "input_decls": {"IN": {"size": 3}},
              "output_decls": {"OUT": {"size": 3}}
            }
          }
        }
      ]
    }
  ]
}

from classiq import (
    Model,
    RegisterUserInput,
    FunctionLibrary,
    FunctionGenerator,
    QASM_INTRO,
    qfunc,
    QReg,
)
from classiq.builtin_functions import ArithmeticOracle, GroverOperator
from classiq import synthesize, show


@qfunc
def my_state_preparation(input: QReg[3]) -> QReg[3]:
    return QASM_INTRO + "qreg q[3];\nx q[0];\nh q[1];\nh q[2];"


library = FunctionLibrary(my_state_preparation)

oracle_params = ArithmeticOracle(
    expression="a + b + c == 1",
    definitions=dict(
        a=RegisterUserInput(size=1),
        b=RegisterUserInput(size=1),
        c=RegisterUserInput(size=1),
    ),
    uncomputation_method="naive",
)
grover_params = GroverOperator(
    oracle_params=oracle_params,
    state_preparation="my_state_preparation",
    state_preparation_params=library.get_function("my_state_preparation"),
)

m = Model()
m.include_library(library)
m.GroverOperator(grover_params)
model = m.get_model()

qprog = synthesize(model)
show(qprog)

Grover in the IDE

The screenshot below shows the IDE view when you select the Grover option in the application suite.

grover-ide

See how to construct a full Grover model with execution logic, and how to synthesize and execute it in Grover Search Algorithm section.

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.