Grover's Algorithm

View on GitHub Experiment in the IDE

This notebook demonstrates how to use the construct_grover_model function, which constructs a Grover search model. For more comprehensive explanation on the algorithm see 3SAT Grover notebook.

1. Defining a Specific Example

Start with specifying a specific search problem: the arithmetic variables and the arithmetic predicate.

from classiq import RegisterUserInput

definitions = [
    ("a", RegisterUserInput(size=2)),
    ("b", RegisterUserInput(size=2)),
    ("c", RegisterUserInput(size=3)),
]
expression = "(a + b + (c & 6)) % 4 | 4 & c == 4"

2. Constructing and Synthesizing a Grover Model

We now call the construct_grover_model for the specific case. We pass the number of grover operator repetitions in the model (which is based on the frequency of solutions in the search space).

from classiq import construct_grover_model, write_qmod

qmod = construct_grover_model(
    num_reps=1, expression=expression, definitions=definitions
)

write_qmod(qmod, "grover")

We synthesize and visualize the circuit

from classiq import show, synthesize

qprog = synthesize(qmod)

show(qprog)

Opening: https://platform.classiq.io/circuit/c727208c-a6f1-4cf0-974d-fc1c279605b3?version=0.41.0.dev39%2B79c8fd0855

3. Executing to Find the Result

Lastly, we execute the resulting quantum program

from classiq import execute, set_quantum_program_execution_preferences
from classiq.execution import (
    ClassiqBackendPreferences,
    ClassiqSimulatorBackendNames,
    ExecutionPreferences,
)

backend_preferences = ExecutionPreferences(
    backend_preferences=ClassiqBackendPreferences(
        backend_name=ClassiqSimulatorBackendNames.SIMULATOR
    )
)

qprog = set_quantum_program_execution_preferences(qprog, backend_preferences)
optimization_result = execute(qprog).result()

res = optimization_result[0].value

We can define a classical predicate to verify the result

def classical_predicate(a, b, c):
    return (a + b + (c & 6)) % 4 | 4 & c == 4

We can take the three-most probable results (the parsed_counts variable of the results is ordered according to the probability of the corresponding state)

NUM_SOLUTIONS = 3

for k in range(NUM_SOLUTIONS):
    parsed_res = res.parsed_counts[k].state
    a, b, c = int(parsed_res["a"]), int(parsed_res["b"]), int(parsed_res["c"])
    print("a =", a, ", b =", b, ", c =", c, ":", classical_predicate(a, b, c))

a = 1 , b = 3 , c = 5 : True
a = 2 , b = 0 , c = 7 : True
a = 0 , b = 0 , c = 5 : True