Skip to content

A Large 3-SAT Grover search Example

EXPRESSION = """
((x2) or (x3) or (x4)) and
((not x1) or ( x2) or ( x3)) and
((not x1) or ( x2) or (not x3)) and
((not x1) or (not x2) or ( x3)) and
(( x1) or (not x2) or (not x3)) and
(( x1) or (not x2) or ( x3)) and
((not x1) or (not x2) or (not x4)) and
((not x1) or (not x2) or ( x4)) and
((not x2) or (not x3) or (not x4)) and
(( x2) or (not x3) or ( x4)) and
(( x1) or (not x3) or ( x4)) and
(( x1) or (not x2) or (not x4)) and
((not x1) or (not x2) or (not x3))
"""
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")
Please import 'truth-table-generator' in order to print the truth table

Loading the model

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 write_qmod

write_qmod(qmod, "3_sat_grover_large")

Synthesizing the Circuit

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

from classiq import QuantumProgram, 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:

circuit = QuantumProgram.from_qprog(qprog)
circuit.show()
Opening: https://platform.classiq.io/circuit/dba01c4b-bf9c-49cb-baaf-b726d72d3039?version=0.41.0.dev39%2B79c8fd0855
print(circuit.transpiled_circuit.depth)
1188

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 - Classiq's default simulator):

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

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:

res.counts_of_multiple_outputs(("x1", "x2", "x3", "x4"))
{('1', '1', '0', '1'): 20,
 ('1', '1', '0', '0'): 14,
 ('1', '1', '1', '0'): 15,
 ('0', '0', '1', '1'): 361,
 ('1', '1', '1', '1'): 18,
 ('1', '0', '0', '0'): 13,
 ('0', '1', '0', '0'): 11,
 ('0', '0', '0', '0'): 13,
 ('0', '0', '1', '0'): 18,
 ('0', '1', '1', '1'): 15,
 ('1', '0', '0', '1'): 20,
 ('1', '0', '1', '0'): 22,
 ('0', '0', '0', '1'): 411,
 ('0', '1', '1', '0'): 21,
 ('1', '0', '1', '1'): 18,
 ('0', '1', '0', '1'): 10}