Oracle generation for 3-SAT problems
This notebook demonstrates Classiq's capabilities in the framework of phase oracles. The focus is 3-SAT problems on a growing number of variables. To highlight the advantage of generation times, we skip transpilation for the synthesis output.
The following utility functions generate random 3-SAT problems for \(N\) boolean variables, consisting of \(N\) clauses.
import numpy as np
from classiq.qmod.symbolic import logical_and, logical_not, logical_or
def generate_permutation_for_3sat_expression(num_qubits, max_samples=1000):
"""
A function that generates two permutations on a list of num_qubits variables,
for introducing a random and valid 3-SAT problem
"""
direct_arr = np.array([k for k in range(num_qubits)])
for k in range(max_samples):
permut1 = np.random.permutation(num_qubits)
permut2 = np.random.permutation(num_qubits)
if (
(0 not in permut2 - direct_arr)
and (0 not in permut1 - direct_arr)
and (0 not in permut1 - permut2)
):
break
assert (
k < max_samples
), "Could not find a random 3-SAT problem, try to increase max_samples"
return direct_arr, permut1, permut2
def generate_3sat_qbit_expression(vars, s0, s1, s2):
"""
A function that generates a 3-SAT problem on a list of QBit variables.
The returned expression contains num_qubits=len(vars) clauses and contains
triplets of the form (x_k or ~x_s1(k) or x_s2(k)), where s1, s2 are permutations.
"""
num_qubits = len(vars)
k = 0
y = logical_or(logical_or(vars[s0[k]], logical_not(vars[s1[k]])), vars[s2[k]])
for k in range(1, num_qubits):
temp = logical_or(
logical_or(vars[s0[k]], logical_not(vars[s1[k]])), vars[s2[k]]
)
y = logical_and(y, temp)
return y
1. Generating Phase Oracles
For each 3-SAT problem we generate an oracle with Classiq and save the generation time, as well as the circuits' width.
from classiq import (
Constraints,
H,
OptimizationParameter,
Output,
Preferences,
QNum,
QuantumProgram,
X,
allocate,
create_model,
qfunc,
set_constraints,
set_preferences,
synthesize,
within_apply,
)
def get_generation_time_classiq(s0, s1, s2, num_qubits):
start_cl = time.time()
@qfunc
def main():
def inner_call(aux: QNum):
aux ^= generate_3sat_qbit_expression(
[dict_of_qnums[f"x{k}"] for k in range(num_qubits)], s0, s1, s2
)
dict_of_qnums = {f"x{k}": QNum(f"x{k}") for k in range(num_qubits)}
for k in range(num_qubits):
allocate(1, dict_of_qnums[f"x{k}"])
aux = QNum("aux")
allocate(1, aux)
within_apply(
lambda: (X(aux), H(aux)),
lambda: inner_call(aux),
)
qmod = create_model(main)
qmod = set_preferences(qmod, preferences=Preferences(transpilation_option="none"))
qprog = synthesize(qmod)
cir = QuantumProgram.from_qprog(qprog)
return cir.data.width, time.time() - start_cl
The following function generates a phase oracle with qiskit.
def get_generation_time_qiskit(s0, s1, s2, num_qubits):
start_qs = time.time()
dict_of_qnums = {f"x{k}": QNum(f"x{k}") for k in range(num_qubits)}
expression = str(
generate_3sat_qbit_expression(
[dict_of_qnums[f"x{k}"] for k in range(num_qubits)], s0, s1, s2
)
)
expression = expression.replace("or", "|")
expression = expression.replace("not", "~")
expression = expression.replace("and", "&")
oracle = PhaseOracle(expression, var_order=None)
q = QuantumRegister(num_qubits)
qc = QuantumCircuit(q)
qc.append(oracle, q[:])
return time.time() - start_qs
For generating the same data with Qiskit please uncomment the commented lines (including the pip install command). We work with qiskit version 1.0.0.
import time
from qiskit import QuantumCircuit, QuantumRegister, transpile
from qiskit.circuit.library import PhaseOracle
from classiq import CustomHardwareSettings, Preferences, RegisterUserInput, synthesize
We skip generating data with Qiskit for \(N>23\), as generation times exponentially diverge with the number of variables.
np.random.seed(128)
cl_times = []
num_qubits_list = [k for k in range(10, 23)] + [
int(l) for l in np.logspace(np.log2(24), np.log2(68), 10, base=2)
]
# from importlib.metadata import version
# try:
# import qiskit
# if version('qiskit') != "1.0.0":
# !pip uninstall qiskit -y
# !pip install qiskit==1.0.0
# except ImportError:
# !pip install qiskit==1.0.0
# ! pip install tweedledum
# qs_times = []
for l in num_qubits_list:
num_qubits = l
print("num_qubits:", num_qubits)
s0, s1, s2 = generate_permutation_for_3sat_expression(num_qubits)
cl_width, classiq_generation_time = get_generation_time_classiq(
s0, s1, s2, num_qubits
)
cl_times.append(classiq_generation_time)
print("classiq_width:", cl_width, ", classiq_time:", classiq_generation_time)
# if l<23:
# qiskit_generation_time = get_generation_time_qiskit(s0, s1, s2, num_qubits)
# qs_times.append(qiskit_generation_time)
# print("qiskit_time:", qiskit_generation_time)
num_qubits: 10
classiq_width: 21 , classiq_time: 2.2342519760131836
num_qubits: 11
classiq_width: 24 , classiq_time: 2.1264989376068115
num_qubits: 12
classiq_width: 26 , classiq_time: 2.1227452754974365
num_qubits: 13
classiq_width: 28 , classiq_time: 2.1253809928894043
num_qubits: 14
classiq_width: 30 , classiq_time: 2.1289098262786865
num_qubits: 15
classiq_width: 32 , classiq_time: 2.14056396484375
num_qubits: 16
classiq_width: 34 , classiq_time: 2.1414260864257812
num_qubits: 17
classiq_width: 36 , classiq_time: 2.218695878982544
num_qubits: 18
classiq_width: 38 , classiq_time: 2.173229694366455
num_qubits: 19
classiq_width: 40 , classiq_time: 2.148393154144287
num_qubits: 20
classiq_width: 42 , classiq_time: 2.153247833251953
num_qubits: 21
classiq_width: 44 , classiq_time: 2.158281087875366
num_qubits: 22
classiq_width: 46 , classiq_time: 2.3974831104278564
num_qubits: 24
classiq_width: 50 , classiq_time: 3.242741107940674
num_qubits: 26
classiq_width: 54 , classiq_time: 3.197925090789795
num_qubits: 30
classiq_width: 62 , classiq_time: 4.215781211853027
num_qubits: 33
classiq_width: 68 , classiq_time: 4.2895119190216064
num_qubits: 38
classiq_width: 78 , classiq_time: 5.261475086212158
num_qubits: 42
classiq_width: 86 , classiq_time: 6.337763071060181
num_qubits: 48
classiq_width: 98 , classiq_time: 8.315266847610474
num_qubits: 53
classiq_width: 108 , classiq_time: 10.428596019744873
num_qubits: 60
classiq_width: 122 , classiq_time: 13.609048128128052
num_qubits: 67
classiq_width: 136 , classiq_time: 17.594478130340576
2. Plotting the Data
Since generating the data takes time we hard-coded the Qiskit results in the notebook. If you run this notebook by yourself please comment out the following cell.
qs_times = [
0.23147010803222656,
0.2850170135498047,
2.6256730556488037,
0.75693678855896,
5.783859968185425,
3.3723957538604736,
3.9280269145965576,
39.92809295654297,
60.67643904685974,
16.551968097686768,
31.536834955215454,
31.086618900299072,
794.9081449508667,
]
import matplotlib.pyplot as plt
classiq_color = "#D7F75B"
qiskit_color = "#6FA4FF"
plt.rcParams["font.family"] = "serif"
plt.rc("savefig", dpi=300)
plt.rcParams["axes.linewidth"] = 1
plt.rcParams["xtick.major.size"] = 5
plt.rcParams["xtick.minor.size"] = 5
plt.rcParams["ytick.major.size"] = 5
plt.rcParams["ytick.minor.size"] = 5
plt.loglog(
[n for n in num_qubits_list if n < 23],
qs_times,
"s",
label="qiskit",
markerfacecolor=qiskit_color,
markeredgecolor="k",
markersize=7,
markeredgewidth=1.5,
linewidth=1.5,
color=qiskit_color,
)
plt.loglog(
num_qubits_list,
cl_times,
"o",
label="classiq",
markerfacecolor=classiq_color,
markeredgecolor="k",
markersize=8.5,
markeredgewidth=1.5,
linewidth=1.5,
color=classiq_color,
)
plt.legend(fontsize=16, loc="upper right")
plt.ylabel("generation time [sec]", fontsize=16)
plt.xlabel("number of variables", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
(array([1.e-01, 1.e+00, 1.e+01, 1.e+02, 1.e+03]),
[Text(0.1, 0, '$\\mathdefault{10^{-1}}$'),
Text(1.0, 0, '$\\mathdefault{10^{0}}$'),
Text(10.0, 0, '$\\mathdefault{10^{1}}$'),
Text(100.0, 0, '$\\mathdefault{10^{2}}$'),
Text(1000.0, 0, '$\\mathdefault{10^{3}}$')])
