A Large 3-SAT Grover search Example¶

In [ ]:

EXPRESSION = """
((x2) or (x3) or (x4)) and
((~x1) or ( x2) or ( x3)) and
((~x1) or ( x2) or (~x3)) and
((~x1) or (~x2) or ( x3)) and
(( x1) or (~x2) or (~x3)) and
(( x1) or (~x2) or ( x3)) and
((~x1) or (~x2) or (~x4)) and
((~x1) or (~x2) or ( x4)) and
((~x2) or (~x3) or (~x4)) and
(( x2) or (~x3) or ( x4)) and
(( x1) or (~x3) or ( x4)) and
(( x1) or (~x2) or (~x4)) and
((~x1) or (~x2) or (~x3))
"""

EXPRESSION = """ ((x2) or (x3) or (x4)) and ((~x1) or ( x2) or ( x3)) and ((~x1) or ( x2) or (~x3)) and ((~x1) or (~x2) or ( x3)) and (( x1) or (~x2) or (~x3)) and (( x1) or (~x2) or ( x3)) and ((~x1) or (~x2) or (~x4)) and ((~x1) or (~x2) or ( x4)) and ((~x2) or (~x3) or (~x4)) and (( x2) or (~x3) or ( x4)) and (( x1) or (~x3) or ( x4)) and (( x1) or (~x2) or (~x4)) and ((~x1) or (~x2) or (~x3)) """

In [ ]:

try:
    import ttg

    print(
        ttg.Truths(
            ["x1", "x2", "x3", "x4"],
            [EXPRESSION[1:-1]],
        )
    )
except:
    print("Please import 'truth-table-generator' in order to print the truth table")

try: import ttg print( ttg.Truths( ["x1", "x2", "x3", "x4"], [EXPRESSION[1:-1]], ) ) except: print("Please import 'truth-table-generator' in order to print the truth table")

Loading the model¶

In [ ]:

from classiq import RegisterUserInput, construct_grover_model

register_size = RegisterUserInput(size=1)

qmod = construct_grover_model(
    num_reps=1,
    expression="(" + EXPRESSION + ")",
    definitions=[
        ("x1", register_size),
        ("x2", register_size),
        ("x3", register_size),
        ("x4", register_size),
    ],
)

from classiq import RegisterUserInput, construct_grover_model register_size = RegisterUserInput(size=1) qmod = construct_grover_model( num_reps=1, expression="(" + EXPRESSION + ")", definitions=[ ("x1", register_size), ("x2", register_size), ("x3", register_size), ("x4", register_size), ], )

In [ ]:

with open("3_sat_grover_large.qmod", "w") as f:
    f.write(qmod)

with open("3_sat_grover_large.qmod", "w") as f: f.write(qmod)

Synthesizing the Circuit¶

We proceed by synthesizing the circuit using Classiq's synthesis engine. The synthesis should take approximately several seconds:

In [ ]:

from classiq import GeneratedCircuit, synthesize

qprog = synthesize(qmod)

from classiq import GeneratedCircuit, synthesize qprog = synthesize(qmod)

Showing the Resulting Circuit¶

After Classiq's synthesis engine has finished the job, we can show the resulting circuit in the interactive GUI:

In [ ]:

circuit = GeneratedCircuit.from_qprog(qprog)
circuit.show()

circuit = GeneratedCircuit.from_qprog(qprog) circuit.show()

In [ ]:

print(circuit.transpiled_circuit.depth)

print(circuit.transpiled_circuit.depth)

Executing the circuit¶

Lastly, we can execute the resulting circuit with Classiq's execute interface, using the execute function. We select the number of iterations we wish to run (in this case - 1), and the execution backend (in this case - the IBM Aer simulator):

In [ ]:

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

backend_preferences = ExecutionPreferences(
    backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator")
)

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

from classiq import execute, set_quantum_program_execution_preferences from classiq.execution import ( ClassiqBackendPreferences, ExecutionDetails, ExecutionPreferences, ) backend_preferences = ExecutionPreferences( backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator") ) qprog = set_quantum_program_execution_preferences(qprog, backend_preferences) optimization_result = execute(qprog).result()

In [ ]:

res = optimization_result[0].value

res = optimization_result[0].value

Printing out the result, we see that our execution of Grover's algorithm successfully found the satisfying assignments for the input formula with a high probability:

In [ ]:

res.counts_of_multiple_outputs(("x1", "x2", "x3", "x4"))

res.counts_of_multiple_outputs(("x1", "x2", "x3", "x4"))