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.

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

with a, b, c unsinged integers of size 3.

2. Constructing and Synthesizing a Grover Model

We now call the grover_search 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 *

NUM_VARIABLES = 3


class PredicateVars(QStruct):
    a: QNum[2, False, 0]
    b: QNum[2, False, 0]
    c: QNum[3, False, 0]


@qfunc
def quantum_predicate(vars: PredicateVars, res: QBit):
    res ^= classical_predicate(vars.a, vars.b, vars.c)


@qfunc
def main(vars: Output[PredicateVars]):
    allocate(vars.size, vars)

    grover_search(
        reps=1,
        oracle=lambda vars: phase_oracle(quantum_predicate, vars),
        packed_vars=vars,
    )


qmod = create_model(main, out_file="grover")

We synthesize and visualize the circuit

qprog = synthesize(qmod)

show(qprog)

3. Executing to Find the Result

Lastly, we execute the resulting quantum program

result = execute(qprog).result_value()

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)

result.parsed_counts[0].state["vars"]

{'a': 1, 'b': 3, 'c': 5}

NUM_SOLUTIONS = 3

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

a = 1 , b = 3 , c = 5 : True
a = 1 , b = 1 , c = 6 : True
a = 2 , b = 2 , c = 5 : True