Discrete Quantum Walk on a Circle

View on GitHub

This notebook demonstrates the capabilities of the synthesis engine for a walk operator on a circle. The walk operator acts on two quantum variables: a coin qubit and a position quantum number. The core part of the walk operator is the increment quantum function, which is implemented here via a series of multi-controlled X operation.

import time

import numpy as np

from classiq import *

transpilation_options = {"classiq": "custom", "qiskit": 3}
NUM_QUBITS_MIN = 5
NUM_QUBITS_MAX = 12

@qfunc
def my_mcx(x: QNum, y: QBit):
    control(x == 2**x.size - 1, lambda: X(y))


@qfunc
def increment(x: QArray[QBit]):
    repeat(x.len - 1, lambda i: my_mcx(x[0 : x.len - 1 - i], x[x.len - 1 - i]))
    X(x[0])


@qfunc
def single_step_walk(
    x: QNum,  # position
):
    coin = QNum("coin")
    allocate(1, coin)
    H(coin)
    control(coin == 0, lambda: increment(x)),
    control(coin == 1, lambda: invert(lambda: increment(x)))

preferences = Preferences(
    custom_hardware_settings=CustomHardwareSettings(basis_gates=["cx", "u"]),
    transpilation_option=transpilation_options["classiq"],
)

Synthesizing with two Different Optimization Scenarios

def get_width_depth_cx_count(qprog):
    circuit = QuantumProgram.from_qprog(qprog)

    width = circuit.data.width
    depth = circuit.transpiled_circuit.depth
    cx_count = circuit.transpiled_circuit.count_ops["cx"]

    return width, depth, cx_count

classiq_depths_opt_width = []
classiq_cx_counts_opt_width = []
classiq_widths_opt_width = []
classiq_times_opt_width = []

classiq_cx_counts_opt_cx = []
classiq_depths_opt_cx = []
classiq_widths_opt_cx = []
classiq_times_opt_cx = []

qmods = []
qmods_width = []
qmods_cx = []
qprogs_width = []
qprogs_cx = []

for num_qubits in range(NUM_QUBITS_MIN, NUM_QUBITS_MAX):
    print(num_qubits, "======")
    start_time = time.time()

    @qfunc
    def main(x: Output[QNum]):
        allocate_num(num_qubits, False, 0, x)
        single_step_walk(x)

    qmod = create_model(main)
    qmod = set_preferences(qmod, preferences=preferences)
    qmods.append(qmod)

    # width optimization
    qmod_width = set_constraints(
        qmod, optimization_parameter=OptimizationParameter.WIDTH
    )
    qmods_width.append(qmod_width)

    qprog_width = synthesize(qmod_width)
    qprogs_width.append(qprog_width)

    end_time = time.time() - start_time
    width, depth, cx_count = get_width_depth_cx_count(qprog_width)
    classiq_widths_opt_width.append(width)
    classiq_depths_opt_width.append(depth)
    classiq_cx_counts_opt_width.append(cx_count)
    classiq_times_opt_width.append(end_time)
    print("time:", end_time)

    # CX Optimization with a Constrained Width
    qmod_cx = set_constraints(
        qmod,
        optimization_parameter="cx",
        max_width=2 * num_qubits,  # setting some bound
    )
    qmods_cx.append(qmod_cx)

    start_time = time.time()
    qprog_cx = synthesize(qmod_cx)
    qprogs_cx.append(qprog_cx)

    end_time = time.time() - start_time
    width, depth, cx_count = get_width_depth_cx_count(qprog_cx)
    classiq_widths_opt_cx.append(width)
    classiq_depths_opt_cx.append(depth)
    classiq_cx_counts_opt_cx.append(cx_count)
    classiq_times_opt_cx.append(end_time)
    print("time", end_time)

5 ======
time: 3.6095149517059326
time 2.083699941635132
6 ======
time: 4.189702272415161
time 2.097536087036133
7 ======
time: 7.209691762924194
time 3.0989890098571777
8 ======
time: 10.247850179672241
time 4.106258869171143
9 ======
time: 20.30021905899048
time 5.183635234832764
10 ======
time: 44.32120895385742
time 7.1332621574401855
11 ======
time: 77.35208916664124
time 9.147570848464966

print("classiq depths:", classiq_depths_opt_width)
print("classiq cx_counts:", classiq_cx_counts_opt_width)
print("classiq widths:", classiq_widths_opt_width)
print(classiq_times_opt_width)

print("classiq depths:", classiq_depths_opt_cx)
print("classiq cx_counts:", classiq_cx_counts_opt_cx)
print("classiq widths:", classiq_widths_opt_cx)
print(classiq_times_opt_cx)

classiq depths: [419, 749, 1195, 1773, 2499, 3389, 4099]
classiq cx_counts: [274, 514, 850, 1298, 1874, 2594, 3194]
classiq widths: [6, 7, 8, 9, 10, 11, 13]
[3.6095149517059326, 4.189702272415161, 7.209691762924194, 10.247850179672241, 20.30021905899048, 44.32120895385742, 77.35208916664124]
classiq depths: [193, 245, 335, 419, 509, 602, 704]
classiq cx_counts: [120, 152, 200, 260, 352, 436, 552]
classiq widths: [8, 9, 11, 12, 14, 15, 17]
[2.083699941635132, 2.097536087036133, 3.0989890098571777, 4.106258869171143, 5.183635234832764, 7.1332621574401855, 9.147570848464966]

Comparing to Qiskit Implementation

The qiskit data was generated using qiskit version 1.0.0. To run the qiskit code uncomment the commented cells below.

qiskit_cx_counts = [900, 2376, 5388, 11472, 23700, 48216]
qiskit_depths = [1645, 4222, 9485, 20122, 41509, 84398]
qiskit_widths = [6, 7, 8, 9, 10, 11]
qiskit_times = [
    0.43783092498779297,
    3.743027925491333,
    17.858744144439697,
    73.1058611869812,
    293.51222825050354,
    1222.052798986435,
]

# from qiskit import QuantumCircuit, QuantumRegister, transpile

# def get_incerement_circuit(num_qubits):

#     incerement_circuit= QuantumCircuit(num_qubits)
#     for j in range(num_qubits - 1):
#         incerement_circuit.mcx([k for k in range(num_qubits - 1-j)], num_qubits-1-j)
#     incerement_circuit.x(0)

#     return incerement_circuit

# # building the q_walk_step, the first qubit is the coin
# qiskit_cx_counts = []
# qiskit_depths = []
# qiskit_widths = []
# qiskit_times = []


# for num_qubits in range(NUM_QUBITS_MIN,NUM_QUBITS_MAX):

#     start_time = time.time()
#     q_walk_step = QuantumCircuit(num_qubits+1)
#     q_walk_step.h(0)
#     q_walk_step.append(get_incerement_circuit(num_qubits).control(1, ctrl_state=1),
#                              [k for k in range(num_qubits+1)])
#     q_walk_step.append(get_incerement_circuit(num_qubits).inverse().control(1, ctrl_state=0),
#                              [k for k in range(num_qubits+1)])
#     transpiled_cir = transpile(
#             q_walk_step,
#             basis_gates=["u", "cx"],
#             optimization_level=transpilation_options["qiskit"],
#     )
#     print(time.time()-start_time, ",  ",num_qubits)
#     print(transpiled_cir.depth())
#     qiskit_depths.append(transpiled_cir.depth())
#     qiskit_cx_counts.append(transpiled_cir.count_ops()["cx"])
#     qiskit_widths.append(transpiled_cir.width())
#     qiskit_times.append(time.time()-start_time)


# print(qiskit_cx_counts)
# print(qiskit_depths)
# print(qiskit_widths)
# print(qiskit_times)

num_qubits_classiq = range(NUM_QUBITS_MIN, NUM_QUBITS_MAX)
num_qubits_qiskit = num_qubits_classiq[0 : len(qiskit_cx_counts)]

import matplotlib.pyplot as plt

classiq_color = "#119DA4"
classiq_color_1 = "#F43764"
qiskit_color = "#bb8bff"
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

(qiskit1,) = plt.semilogy(
    num_qubits_qiskit,
    qiskit_cx_counts,
    "-s",
    label="qiskit",
    markerfacecolor=qiskit_color,
    markeredgecolor="k",
    markersize=6,
    markeredgewidth=1.5,
    color=qiskit_color,
)

(classiq1,) = plt.semilogy(
    num_qubits_classiq,
    classiq_cx_counts_opt_width,
    "-D",
    label="classiq width opt.",
    markerfacecolor=classiq_color,
    markeredgecolor="k",
    markersize=6.5,
    markeredgewidth=1.5,
    color=classiq_color,
)

(classiq2,) = plt.semilogy(
    num_qubits_classiq,
    classiq_cx_counts_opt_cx,
    "-o",
    label="classiq cx opt.",
    markerfacecolor=classiq_color_1,
    markeredgecolor="k",
    markersize=7,
    markeredgewidth=1.5,
    linewidth=1.5,
    color=classiq_color_1,
)


first_legend = plt.legend(
    handles=[qiskit1, classiq1, classiq2], fontsize=16, loc="upper left"
)


plt.ylabel("CX-counts", fontsize=16)
plt.xlabel(r"$\log_2$(Circle size)", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
plt.axis(ymin=0.7e2, ymax=4e5, xmin=4, xmax=12)


for x, y, num_qubits in zip(
    num_qubits_classiq, classiq_cx_counts_opt_width, classiq_widths_opt_width
):
    plt.text(x * 0.94, y * 1.25, str(num_qubits), fontsize=16, color=classiq_color)

for x, y, num_qubits in zip(
    num_qubits_classiq,
    classiq_cx_counts_opt_cx,
    classiq_widths_opt_cx,
):
    plt.text(x * 0.96, y * 1.25, str(num_qubits), fontsize=16, color=classiq_color_1)
for x, y, num_qubits in zip(num_qubits_qiskit, qiskit_cx_counts, qiskit_widths):
    plt.text(x * 0.96, y * 1.2, str(num_qubits), fontsize=16, color=qiskit_color)

import matplotlib.pyplot as plt

classiq_color = "#119DA4"
classiq_color_1 = "#F43764"
qiskit_color = "#bb8bff"
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

(qiskit1,) = plt.semilogy(
    num_qubits_qiskit,
    qiskit_times,
    "-s",
    label="qiskit",
    markerfacecolor=qiskit_color,
    markeredgecolor="k",
    markersize=6,
    markeredgewidth=1.5,
    color=qiskit_color,
)

(classiq1,) = plt.semilogy(
    num_qubits_classiq,
    classiq_times_opt_width,
    "-D",
    label="classiq width opt.",
    markerfacecolor=classiq_color,
    markeredgecolor="k",
    markersize=6.5,
    markeredgewidth=1.5,
    color=classiq_color,
)

(classiq2,) = plt.semilogy(
    num_qubits_classiq,
    classiq_times_opt_cx,
    "-o",
    label="classiq cx opt.",
    markerfacecolor=classiq_color_1,
    markeredgecolor="k",
    markersize=7,
    markeredgewidth=1.5,
    linewidth=1.5,
    color=classiq_color_1,
)

first_legend = plt.legend(
    handles=[qiskit1, classiq1, classiq2], fontsize=16, loc="upper left"
)


plt.ylabel("Generation time", fontsize=16)
plt.xlabel(r"$\log_2$(Circle size)", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
plt.axis(ymin=2e-1, ymax=2.5e4, xmin=4, xmax=12)


for x, y, num_qubits in zip(
    num_qubits_classiq, classiq_times_opt_width, classiq_widths_opt_width
):
    plt.text(x * 0.98, y * 1.4, str(num_qubits), fontsize=16, color=classiq_color)

for x, y, num_qubits in zip(
    num_qubits_classiq,
    classiq_times_opt_cx,
    classiq_widths_opt_cx,
):
    plt.text(x * 0.96, y * 0.5, str(num_qubits), fontsize=16, color=classiq_color_1)
for x, y, num_qubits in zip(num_qubits_qiskit, qiskit_times, qiskit_widths):
    plt.text(x * 0.94, y * 1.2, str(num_qubits), fontsize=16, color=qiskit_color)

Synthesizing large-scale examples

We have extended the above model to larger and larger circle sizes. The results are saved in a csv file.

ind_for_plot = [0, 5, 10, 12, 14] + [k for k in range(15, 23)]

import pathlib

from pandas import *

path = (
    pathlib.Path(__file__).parent.resolve()
    if "__file__" in locals()
    else pathlib.Path(".")
)
input_file = path / "results.csv"

# reading CSV file
data = read_csv(input_file)  # this data is with cx optimization and max_width=100

# converting column data to list
num_qubits_cx_opt = [data["log2_circle_size_cx_opt"].tolist()[k] for k in ind_for_plot]
cx_cx_opt = [data["cx_cx_opt"].tolist()[k] for k in ind_for_plot]
time_cx_opt = [data["time_cx_opt"].tolist()[k] for k in ind_for_plot]
width_cx_opt = [data["width_cx_opt"].tolist()[k] for k in ind_for_plot]

# converting column data to list
num_qubits_width_opt = [
    data["log2_circle_size_width_opt"].tolist()[k] for k in ind_for_plot
]
cx_width_opt = [data["cx_width_opt"].tolist()[k] for k in ind_for_plot]
time_width_opt = [data["time_width_opt"].tolist()[k] for k in ind_for_plot]
width_width_opt = [data["width_width_opt"].tolist()[k] for k in ind_for_plot]

import matplotlib.pyplot as plt

classiq_color = "#119DA4"
classiq_color_1 = "#F43764"
qiskit_color = "#bb8bff"
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.figure(figsize=(8, 5))

(qiskit1,) = plt.semilogy(
    num_qubits_qiskit,
    qiskit_cx_counts,
    "-s",
    label="qiskit",
    markerfacecolor=qiskit_color,
    markeredgecolor="k",
    markersize=6,
    markeredgewidth=1.5,
    color=qiskit_color,
)

(classiq1,) = plt.semilogy(
    num_qubits_width_opt,
    cx_width_opt,
    "-D",
    label="classiq width optimization",
    markerfacecolor=classiq_color,
    markeredgecolor="k",
    markersize=6.5,
    markeredgewidth=1.5,
    color=classiq_color,
)

(classiq2,) = plt.semilogy(
    num_qubits_cx_opt,
    cx_cx_opt,
    "-o",
    label="classiq cx optimization",
    markerfacecolor=classiq_color_1,
    markeredgecolor="k",
    markersize=7,
    markeredgewidth=1.5,
    linewidth=1.5,
    color=classiq_color_1,
)


first_legend = plt.legend(
    handles=[qiskit1, classiq1, classiq2], fontsize=16, loc="lower right"
)


plt.ylabel("CX-counts", fontsize=16)
plt.xlabel(r"$\log_2$(Circle size)", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
plt.axis(ymin=0.5e2, ymax=1e6, xmin=3, xmax=63)
# plt.xticks(num_qubits_opt_cx_max_width)


for x, y, num_qubits in zip(num_qubits_width_opt, cx_width_opt, width_width_opt):
    plt.text(x * 1.01, y * 0.6, str(num_qubits), fontsize=15, color=classiq_color)

for x, y, num_qubits in zip(
    num_qubits_cx_opt,
    cx_cx_opt,
    width_cx_opt,
):
    plt.text(x * 0.99, y * 0.45, str(num_qubits), fontsize=15, color=classiq_color_1)
for x, y, num_qubits in zip(num_qubits_qiskit, qiskit_cx_counts, qiskit_widths):
    plt.text(x * 0.77, y * 1.2, str(num_qubits), fontsize=15, color=qiskit_color)

import matplotlib.pyplot as plt

classiq_color = "#119DA4"
classiq_color_1 = "#F43764"
qiskit_color = "#bb8bff"
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.figure(figsize=(8, 5))


(qiskit1,) = plt.semilogy(
    num_qubits_qiskit,
    qiskit_times,
    "-s",
    label="qiskit",
    markerfacecolor=qiskit_color,
    markeredgecolor="k",
    markersize=6,
    markeredgewidth=1.5,
    color=qiskit_color,
)

(classiq1,) = plt.semilogy(
    num_qubits_width_opt,
    time_width_opt,
    "-D",
    label="classiq width optimization",
    markerfacecolor=classiq_color,
    markeredgecolor="k",
    markersize=6.5,
    markeredgewidth=1.5,
    color=classiq_color,
)

(classiq2,) = plt.semilogy(
    num_qubits_cx_opt,
    time_cx_opt,
    "-o",
    label="classiq cx optimization",
    markerfacecolor=classiq_color_1,
    markeredgecolor="k",
    markersize=7,
    markeredgewidth=1.5,
    linewidth=1.5,
    color=classiq_color_1,
)


first_legend = plt.legend(
    handles=[qiskit1, classiq1, classiq2], fontsize=16, loc="lower right"
)


plt.ylabel("Generation time [sec]", fontsize=16)
plt.xlabel(r"$\log_2$(Circle size)", fontsize=16)
plt.yticks(fontsize=16)
plt.xticks(fontsize=16)
plt.axis(ymin=0.2, ymax=8e3, xmin=3, xmax=63)


for x, y, num_qubits in zip(num_qubits_width_opt, time_width_opt, width_width_opt):
    if num_qubits < 19:
        plt.text(x * 0.8, y * 1.3, str(num_qubits), fontsize=15, color=classiq_color)
    else:
        plt.text(x * 0.95, y * 1.3, str(num_qubits), fontsize=15, color=classiq_color)

for x, y, num_qubits in zip(
    num_qubits_cx_opt,
    time_cx_opt,
    width_cx_opt,
):
    plt.text(x * 1.0, y * 0.45, str(num_qubits), fontsize=15, color=classiq_color_1)
for x, y, num_qubits in zip(num_qubits_qiskit, qiskit_times, qiskit_widths):
    plt.text(x * 0.72, y * 1.2, str(num_qubits), fontsize=15, color=qiskit_color)