Discrete Quantum Walks

View on GitHub

Open this notebook in GitHub to run it yourself

“Quantum Walk” is an approach for developing and designing quantum algorithms. Consider it as a quantum analogy to the classical random walk. This generic technique underlies many quantum algorithms. In particular, the Grover’s search algorithm can be viewed as a quantum walk. Similarly to classical random walks, quantum walks are divided into the discrete and continuous cases. This notebook focuses on discrete quantum walks, and is organized as follows:

One to one compares classical random walks with quantum walks via a specific example: a walk on a circle.
A general quantum model studies quantum walks and subsequently applies it to the circle case and to a hypercube graph.
An appendix returns to the circle walk to demonstrate the synthesis engine’s optimization capabilities, comparing CX counts of two increment implementations under a width constraint.

This tutorial demonstrates the following concepts of Classiq:

The resemblance between classical and quantum programming with Classiq.
Classiq’s built-in constructs:
control: general controlled-logic
power: “parametric power”, specified as execution parameter.
numeric quantum types: working with signed and unsigned integers.
Passing a list of QCallables (quantum functions).
Parsed execution results, according to quantum variable types.
The synthesis engine’s optimization capabilities, by comparing the CX-counts of two increment implementations under a width constraint (see the appendix).

Classical Random Walks Versus Quantum Walks

Specify and implement a simple example: a discrete walk on a circle, or more precisely, on a regular polygon with

2^N

nodes (see Figure 1). The idea behind the random/quantum walk:

Start at some initial point, e.g., the zeroth node.
Flip a coin.

Heads moves one step clockwise; tails moves counterclockwise.

Repeat steps 1-2 for a given total number of steps $T$ .

Figure

A graph for a random walk on a circle.

import matplotlib.pyplot as plt
import numpy as np

from classiq import *

Code a classical random walk and a discrete quantum walk side by side: Define a function to flip a coin:

Classical: the coin is either 0 or

To flip the coin, draw a random number from the set $\{0,1\}$ .

Quantum: the coin is represented by a qubit and a “flip” is defined by some unitary operation on it.

Choose the Hadamard gate, which sends the

|0\rangle

state into an equal superposition of

|0\rangle

and

|1\rangle

def classical_coin_flip(coin):
    return np.random.randint(2)


@qfunc
def quantum_coin_flip(coin: QBit):
    H(coin)

Next, define a function for moving clockwise and counterclockwise. This operation is a modular addition by

\pm 1

Classical: the position is an integer in $[-2^{N-1}, 2^{N-1}-1]$ .

Use basic arithmetic operations.

Quantum: the position is an $N$ -qubits state.

Call in-place modular addition by

Note that since quantum operations are reversible, you can define a counterclockwise step as the inverse of the clockwise step.

from classiq.qmod.symbolic import pi


# classical
def classical_step_clockwise(x, circle_size):
    return (x + 1) % circle_size


def classical_step_counterclockwise(x, circle_size):
    return (x - 1) % circle_size


# quantum
@qperm
def quantum_step_clockwise(x: QNum):
    x += 1

Finally, construct a function for the full walk, iterating between flipping a coin and a single walking step based on the coin’s state. Note the difference between the classical and quantum function declarations. For the quantum part you do not need to pass the circle size, as it is given by the size of the position state

x

# classical


def random_walk_circle(
    time,  # total time
    x,  # position
    circle_size,  # the size of the circle
):
    coin = 0
    for step in range(time):
        coin = classical_coin_flip(coin)
        if coin == 0:
            x = classical_step_clockwise(x, CIRCLE_SIZE)
        if coin == 1:
            x = classical_step_counterclockwise(x, CIRCLE_SIZE)
    return x


# quantum
@qfunc
def discrete_quantum_walk_circle(
    time: CInt,  # total time
    coin: QBit,  # coin
    x: QArray,  # position
):
    power(
        time,
        lambda: (
            quantum_coin_flip(coin),
            control(
                coin == 0,
                lambda: quantum_step_clockwise(x),
                lambda: invert(lambda: quantum_step_clockwise(x)),
            ),
        ),
    )

Define and run a specific example, taking a circle of size

2^7

, a total time of 50 steps, and 10,000 samples.

CIRCLE_SIZE = 2**7
TOTAL_TIME = 50
NUM_SAMPLES = 10000

from classiq.qmod.symbolic import floor, log

# classical
final_pos = np.zeros(CIRCLE_SIZE)
for trial in range(NUM_SAMPLES):
    x = random_walk_circle(time=TOTAL_TIME, x=0, circle_size=CIRCLE_SIZE)
    final_pos[x] += 1


# quantum
@qfunc
def main(
    t: CInt, x: Output[QNum[floor(log(CIRCLE_SIZE, 2)), SIGNED, 0]], coin: Output[QBit]
):
    allocate(x)
    allocate(coin)
    discrete_quantum_walk_circle(t, coin, x)


qmod_1 = create_model(main)

qprog_1 = synthesize(qmod_1)
show(qprog_1)

df_1 = sample(qprog_1, parameters={"t": 50}, num_shots=NUM_SAMPLES)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IIyjxuISNlcyfyHpwzM1wLMrWl
  

Output:

Submitting job to simulator
  Job: https://platform.classiq.io/jobs/66224316-3277-40e0-9d4d-8469a9937fad
  

Figure

The circuit for a quantum walk on a circle with $2^7$ nodes.

The last three blocks repeat t times.

Plot the probabilities of ending at each position along the circle. In both the classical and quantum cases, consider the probability of the final position after time

T=50

# classical
prob_classical = final_pos / NUM_SAMPLES
grid = (np.linspace(0, CIRCLE_SIZE - 1, CIRCLE_SIZE)).astype(int)
flipped_grid = np.append(
    grid[CIRCLE_SIZE // 2 : CIRCLE_SIZE] 

- CIRCLE_SIZE, grid[0 : CIRCLE_SIZE // 2]
)
flipped_prob_classical = np.append(
    prob_classical[CIRCLE_SIZE // 2 : CIRCLE_SIZE], prob_classical[0 : CIRCLE_SIZE // 2]
)

# quantum: sum over the coin state, keeping only the position
quantum_probs = df_1.groupby("x")["probability"].sum().to_dict()
sorted_quantum_probs = dict(sorted(quantum_probs.items()))


plt.plot(flipped_grid, flipped_prob_classical, ".-")
plt.plot(sorted_quantum_probs.keys(), sorted_quantum_probs.values(), ".-")
plt.xlabel("position", fontsize=16)
plt.ylabel("probability", fontsize=16)

Output:


Text(0, 0.5, 'probability')

There is a clear difference between the two distributions: the classical distribution is symmetric around the zero position, whereas the quantum example is asymmetric with a peak far from

This is a small example of the different behaviors of classical random walks and quantum walks.

More details and examples are in Ref. [1].

Building a General Quantum Walk with Classiq

Define a quantum function for a discrete quantum walk. The arguments of the function:

time: an integer for the number of walking steps.
coin_flip_qfunc: the quantum function for “flipping” the coin.
walks_qfuncs: a list of quantum functions for all possible transitions at a given point.
coin_state: the quantum state of the coin.

from classiq.qmod.symbolic import pi


@qfunc
def discrete_quantum_walk(
    time: CInt,
    coin_flip_qfunc: QCallable[QNum],
    walks_qfuncs: QCallableList,
    coin_state: QNum,
):
    power(
        time,
        lambda: (
            coin_flip_qfunc(coin_state),
            repeat(
                walks_qfuncs.len,
                lambda i: control(coin_state == i, lambda: walks_qfuncs[i]()),
            ),
        ),
    )

Example: Symmetric Quantum Walk on a Circle

As a first example, consider the circle geometry above, implemented with the generic definition but with a different initial condition for the coin. Take

\frac{1}{\sqrt{2}}(|0\rangle +i |1\rangle)

instead of

|0\rangle

. This state is a balanced initial condition for the coin (see Ref. [1]) and can be prepared by applying an H gate followed by an S gate.

CIRCLE_SIZE = 2**7
NUM_SHOTS = 1e4


@qfunc
def main(
    t: CInt, x: Output[QNum[floor(log(CIRCLE_SIZE, 2)), SIGNED, 0]], coin: Output[QBit]
):
    allocate(x)
    allocate(coin)
    H(coin)
    S(coin)
    discrete_quantum_walk(
        t,
        lambda coin: H(coin),
        [
            lambda: quantum_step_clockwise(x),
            lambda: invert(lambda: quantum_step_clockwise(x)),
        ],
        coin,
    )


qmod_2 = create_model(main)

Now that the model is defined, you can synthesize, execute, and plot the outcome probability:

qprog_2 = synthesize(qmod_2)
show(qprog_2)
df_2 = sample(qprog_2, parameters={"t": 50}, num_shots=NUM_SHOTS)

# sum over the coin state, keeping only the position
quantum_probs = df_2.groupby("x")["probability"].sum().to_dict()
sorted_quantum_probs = dict(sorted(quantum_probs.items()))

plt.plot(sorted_quantum_probs.keys(), sorted_quantum_probs.values(), ".-")
plt.xlabel("position", fontsize=16)
plt.ylabel("probability", fontsize=16)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IIylSjDHJ52pDUxz1XfjrVylrz
  

Output:

Submitting job to simulator
  Job: https://platform.classiq.io/jobs/2f56088e-48f3-480a-b99c-a6ca1e023d4f
  

Output:


Text(0, 0.5, 'probability')

The distribution is symmetric. Clearly, the distribution of a quantum walk on a circle depends on the initial condition for the coin. This is another example of the peculiar behavior of quantum walks compared to classical random walks.

Example: 4D Hypercube with a Grover Coin

Next, consider a hypercube graph (see Figure 3). The quantum walk on a hypercube shows completely different behavior compared to its classical counterpart. One striking difference refers to the hitting time, which is the time it takes to reach node

v

starting from an initial node

u

. In particular, an interesting question is the hitting time between one corner of the hypercube “000..0” to the opposite one “111…1”. Ref. [2]) shows that the hitting time for the hypercube in quantum walks is exponentially faster than the analog quantity in classical random walks. The rigorous definition of the “hitting time” in the quantum case is nontrivial, and different definitions are relevant. This notebook does not use the exact definition, but simply demonstrates a specific result, highlighting the result of Ref. [2]. Define

P_{\rm corner}(T)

as the probability of measuring the walker at the opposite corner

|2^{N}-1\rangle

after

T

steps, starting at position

|0\rangle

at time

Examine this quantity for the quantum and the classical case.

Figure

A graph for a random walk on a 3D hypercube.

Define a model for quantum walk on a hypercube. Two nodes in the hypercube are connected to each other if their Hamming distance is

Thus, a step along a hypercube is given by moving “1 Hamming distance away”.

For a

d

-dimensional hypercube, at each node there are

d

possible directions to move. Each of them is given by applying a bit flip on one of the bits. In the quantum case, this is obtained by applying an X gate on one of the

N

qubits. For the coin operator, take the “Grover diffuser” function. This choice refers to a symmetric quantum walk [1]. The Grover diffuser operator is a reflection around a given state

|\psi\rangle

G = I-2 |\psi\rangle\langle\psi|,

where I is the identity matrix. In the

N

-dimensional hypercube each node is connected to

N

nodes, thus, the coin state should include

N

different states. Therefore, the coin is represented by a quantum variable of size

\lceil \log_2(N)\rceil

, and the Grover diffuser is defined with

|\psi\rangle = \frac{1}{\sqrt{N}}\sum^{N-1}_{i=0} |i\rangle.

Build the model using the grover_diffuser function from the Classiq open library.

@qperm
def moving_one_hamming_dist(pos: CInt, x: QArray):
    X(x[pos])

from classiq.qmod.symbolic import ceiling

SPACE_SIZE = 4
NUM_SHOTS = 1e4


@qfunc
def main(t: CInt, x: Output[QArray[QBit, SPACE_SIZE]], coin: Output[QArray]):
    # start at the zero state location
    allocate(x)

    # start with equal superposition for the relevant states.
    allocate(SPACE_SIZE.bit_length() - 1, coin)
    prepare_uniform_trimmed_state(SPACE_SIZE, coin)
    discrete_quantum_walk(
        t,
        lambda coin: grover_diffuser(
            lambda coin: prepare_uniform_trimmed_state(SPACE_SIZE, coin), coin
        ),
        [
            lambda: moving_one_hamming_dist(0, x),
            lambda: moving_one_hamming_dist(1, x),
            lambda: moving_one_hamming_dist(2, x),
            lambda: moving_one_hamming_dist(3, x),
        ],
        coin,
    )


qmod_3 = create_model(
    main,
    constraints=Constraints(optimization_parameter="width"),
)

qprog_3 = synthesize(qmod_3)
show(qprog_3)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IIymtMvQJ8NkGrWqTZEomJwne5
  

Figure

The circuit for a quantum walk on a 4D cube with a Grover coin.

The last five blocks repeat t times.

df_3 = sample(qprog_3, parameters={"t": 4}, num_shots=NUM_SHOTS)

Output:

Submitting job to simulator
  Job: https://platform.classiq.io/jobs/28854848-43ed-430b-86f8-3c941fec5421
  

corner_state = [1] * SPACE_SIZE
is_corner = df_3["x"].apply(lambda state: list(state) == corner_state)
prob_corner = df_3.loc[is_corner, "probability"].sum()
print("The probability to reach the opposite corner:", prob_corner)

Output:


The probability to reach the opposite corner: 0.5619

T=4

, the probability to measure the walker at the opposite corner is larger than

1/2

. Check an analogous question in the classical random walk, where the distribution is taken over an ensemble of independent experiments:

initial_point = 0
final_point = dict()

for trial in range(NUM_SAMPLES):
    coin_state = np.random.randint(SPACE_SIZE)
    for k in range(SPACE_SIZE):
        if coin_state == k:
            temp_point = initial_point ^ 2**k
            initial_point = temp_point
    final_point[initial_point] = final_point.get(initial_point, 0) + 1

prob_corner_classical = final_point.get(2**SPACE_SIZE - 1, 0) / NUM_SAMPLES
print(
    "The probability to reach the opposite corner in the classical case:",
    prob_corner_classical,
)

Output:


The probability to reach the opposite corner in the classical case: 0.0658

For the classical analogous case, the probability is much lower. This is a manifestation of the fact that the hitting time in a hypercube is exponentially shorter in quantum walks, in comparison to classical random walks. [1]: Kempe, J. “Quantum random walks: An introductory overview.” Contemporary Physics 44, 307 (2003). [2]: Kempe, J. “Discrete quantum walks hit exponentially faster.” Probability theory and related fields 133, 215 (2005).

Appendix: CX-Count Comparison for the Circle Increment

Return to the circle walk of the first section and examine the synthesis engine’s optimization capabilities. The core building block of a single walk step is the increment function that moves the position one step clockwise or counterclockwise. Compare two implementations of this increment:

Built-in increment: the high-level x += 1 used earlier via quantum_step_clockwise.
Naive increment: a manual cascade of multi-controlled-X (MCX) gates, as used in the Discrete Quantum Walk on a Circle notebook.

For a fixed circle size of

2^{10}

nodes, synthesize a single walk step with CX-count optimization under increasing width constraints, and compare the resulting CX counts for the two increment implementations.

POSITION_SIZE = 10  # circle size = 2**10
WIDTHS = list(range(12, 21))  # 12, 13, ..., 20

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


@qfunc
def single_step_walk_builtin(coin: QBit, x: QNum):
    H(coin)
    control(coin == 0, lambda: quantum_step_clockwise(x))
    control(coin == 1, lambda: invert(lambda: quantum_step_clockwise(x)))


# naive increment: a cascade of multi-controlled X gates
@qfunc
def naive_increment(x: QArray):
    repeat(
        x.len - 1, lambda i: control(x[0 : x.len - 1 - i], lambda: X(x[x.len - 1 - i]))
    )
    X(x[0])


@qfunc
def single_step_walk_naive(coin: QBit, x: QNum):
    H(coin)
    control(coin == 0, lambda: naive_increment(x))
    control(coin == 1, lambda: invert(lambda: naive_increment(x)))

cx_counts_builtin = []
cx_counts_naive = []

for max_width in WIDTHS:
    print(max_width, "======")
    constraints = Constraints(optimization_parameter="cx", max_width=max_width)

    @qfunc
    def main(x: Output[QNum[POSITION_SIZE]], coin: Output[QBit]):
        allocate(x)
        allocate(coin)
        single_step_walk_builtin(coin, x)

    qprog = synthesize(main, preferences=preferences, constraints=constraints)
    metrics = get_transpiled_circuit_metrics(qprog)
    cx_counts_builtin.append(metrics.count_ops["cx"])

    @qfunc
    def main(x: Output[QNum[POSITION_SIZE]], coin: Output[QBit]):
        allocate(x)
        allocate(coin)
        single_step_walk_naive(coin, x)

    qprog = synthesize(main, preferences=preferences, constraints=constraints)
    metrics = get_transpiled_circuit_metrics(qprog)
    cx_counts_naive.append(metrics.count_ops["cx"])

print("built-in cx counts:", cx_counts_builtin)
print("naive cx counts:", cx_counts_naive)

Output:

======
======
======
======
======
======
======
======
======
  built-in cx counts: [440, 440, 184, 174, 164, 154, 146, 124, 124]
  naive cx counts: [648, 610, 562, 542, 542, 542, 542, 542, 542]
  

Plot the CX counts as a function of the width constraint, for the fixed circle size of

2^{10}

nodes:

classiq_color = "#119DA4"
classiq_color_1 = "#F43764"

(builtin_line,) = plt.plot(
    WIDTHS,
    cx_counts_builtin,
    "-D",
    label="built-in increment",
    markerfacecolor=classiq_color,
    markeredgecolor="k",
    markersize=6.5,
    markeredgewidth=1.5,
    color=classiq_color,
)

(naive_line,) = plt.plot(
    WIDTHS,
    cx_counts_naive,
    "-o",
    label="naive increment (MCX cascade)",
    markerfacecolor=classiq_color_1,
    markeredgecolor="k",
    markersize=7,
    markeredgewidth=1.5,
    color=classiq_color_1,
)

plt.legend(handles=[builtin_line, naive_line], fontsize=13)
plt.xlabel("width constraint", fontsize=16)
plt.ylabel("CX-counts", fontsize=16)
plt.xticks(WIDTHS)
plt.title(r"Circle size $2^{10}$: CX-optimized synthesis under a width constraint")

Output:

Text(0.5, 1.0, 'Circle size $2^{10}$: CX-optimized synthesis under a width constraint')
  

The built-in increment’s CX-count keeps dropping as more width is allowed, since the synthesis engine can trade the extra qubits for a cheaper implementation. The naive MCX cascade improves too, but with higher counts and only up to a point (width 15): past that, the engine has no further use for the additional qubits. This illustrates the benefit of using high-level constructs, such as x += 1, over a manually chosen circuit - the former gives the synthesis engine more room to optimize.

Algorithms

Applications

Tutorials

View on GitHub

Classical Random Walks Versus Quantum Walks

Building a General Quantum Walk with Classiq

Example: Symmetric Quantum Walk on a Circle

Example: 4D Hypercube with a Grover Coin

Appendix: CX-Count Comparison for the Circle Increment

View on GitHub

​Classical Random Walks Versus Quantum Walks

​Building a General Quantum Walk with Classiq

​Example: Symmetric Quantum Walk on a Circle

​Example: 4D Hypercube with a Grover Coin

​Appendix: CX-Count Comparison for the Circle Increment

Classical Random Walks Versus Quantum Walks

Building a General Quantum Walk with Classiq

Example: Symmetric Quantum Walk on a Circle

Example: 4D Hypercube with a Grover Coin

Appendix: CX-Count Comparison for the Circle Increment