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 one chooses a user-defined, its name should be passed in the state_preparation field. The oracle may is given by any of the possible oracle types. Note that the arguments of the oracle and state-preparation operations should match 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. An explanation of Grover Operator execution can be found in the Amplitude Amplification section.

{
  "function_library": {
    "functions": [
      {
        "name": "main",
        "logic_flow": [
          {
            "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

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)

model = Model()
model.GroverOperator(grover_params)

circuit = model.synthesize()

zoom out circuit

Example 2:

The following example shows how to use a custom state preparation. For more information on user-defined functions, see User-defined Functions.

{
  "function_library": {
    "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",
        "logic_flow": [
          {
            "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


@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"),
)

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

circuit = model.synthesize()

Grover in the IDE

In the screenshot below the IDE view when the Grover option is selected form the application suite is shown.

grover-ide

Details on executing a Grover model with Amplitude Amplification can be found in the Amplitude Amplification 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.