Grover's Algorithm¶
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/ee9bd1d2-02ba-491a-a61c-0b7150441e62?version=0.38.0.dev42%2Bfd36e2c41c
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 = 2 , b = 2 , c = 5 : True a = 3 , b = 1 , c = 5 : True a = 3 , b = 1 , c = 4 : True