# 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


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}