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}