A Large 3-SAT Grover search Example¶
In [1]:
Copied!
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))
"""
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))
"""
In [2]:
Copied!
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")
Please import 'truth-table-generator' in order to print the truth table
Loading the model¶
In [3]:
Copied!
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 [4]:
Copied!
from classiq import write_qmod
write_qmod(qmod, "3_sat_grover_large")
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:
In [5]:
Copied!
from classiq import QuantumProgram, synthesize
qprog = synthesize(qmod)
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:
In [6]:
Copied!
circuit = QuantumProgram.from_qprog(qprog)
circuit.show()
circuit = QuantumProgram.from_qprog(qprog)
circuit.show()
Opening: https://platform.classiq.io/circuit/f9d4259b-1b7b-429f-95a3-31139f1c36b2?version=0.38.0.dev42%2Bfd36e2c41c
In [7]:
Copied!
print(circuit.transpiled_circuit.depth)
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):
In [8]:
Copied!
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()
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()
In [9]:
Copied!
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 [10]:
Copied!
res.counts_of_multiple_outputs(("x1", "x2", "x3", "x4"))
res.counts_of_multiple_outputs(("x1", "x2", "x3", "x4"))
Out[10]:
{('0', '1', '0', '0'): 15, ('0', '0', '0', '0'): 17, ('0', '0', '1', '1'): 365, ('1', '0', '1', '0'): 21, ('1', '0', '0', '1'): 15, ('0', '1', '1', '1'): 23, ('1', '0', '1', '1'): 22, ('0', '0', '0', '1'): 412, ('0', '1', '1', '0'): 13, ('1', '1', '1', '1'): 8, ('1', '0', '0', '0'): 13, ('0', '1', '0', '1'): 19, ('1', '1', '0', '1'): 15, ('1', '1', '0', '0'): 13, ('1', '1', '1', '0'): 14, ('0', '0', '1', '0'): 15}