# Minimizing computational time for a quantum walk problem

Any suggestions as to how to speed up the computational time for this quantum walk problem which is coded using a normalized SparseArray coin operator as follows:

ClearAll["Global*"]

(*Define number of sites*)
n = 10;

init = SparseArray[{{1, 1} -> 1, {i_, 1} /; i != 1 -> 0}, {n, 1}];
init = Normalize[init, Norm[#, 1] &];

(*Coin operator*)
SparseArray[{{i_, j_} /; i == j ->
1/Sqrt[2], {i_, j_} /; j == i + 1 || j == i - 1 ->
1/Sqrt[2]}, {n, n}];

Shift = SparseArray[{{i_, i_} -> 0, {i_, j_} /; j == i + 1 ->
1, {i_, j_} /; j == i - 1 -> 1}, {n, n}];

steps = 5;

(* Quantum walk *)
state = Nest[(Shift . Hadamardg . #) &, init, steps];

ListPlot[Transpose[Abs[state]^2][[1]], PlotRange -> All,
AxesLabel -> {"Position", "Probability"}]

• Use numeric computation instead of symbolic in MatrixPower as Hadamardg = MatrixPower[Hadamardg // N, 1/2]; Commented Mar 19, 2023 at 5:50
• Also dotting A = Shift . Hadamardg only once and then doing state = Nest[(A.#) &, init, steps]; might pay off. Commented Mar 19, 2023 at 6:30
• These comments are useful for sure, trying to amend the code so that the output is normalized and does not yield large values if number of sites or steps are inccreased Commented Mar 19, 2023 at 6:57
• Moreover, for small n and large steps, you might want to consider also to diagonalize A. Then each iteration (i.e., multiplying with the diagonal) costs n instead of n^2. Diagonalization costs O(n^3), so this should be faster only if steps * n^2 is much greater than n^3 + steps * n . Commented Mar 19, 2023 at 10:00
• Btw. I don't know much about quantum something something; I too only the first class is quantum mechanics. But since you interpret the squared modulus of state: shouldn't it be init = Normalize[init, Norm[#, 2] &]; (or init = Normalize[init], which is shorter), and shoudn't the matriz you apply recursively be unitrary? Like $\mathrm{e}^{\mathrm{i} \,\Delta t \, H}$? with a self-adjoint matrix H? Commented Mar 19, 2023 at 10:12

With inclusion of changes based on earlier comments, and Normalization of state, and few changes, rapid computational time is noted. The amended code is as follows:

ClearAll["Global*"]

(* No. of sites*)
n = 30;

(* Initial state*)
init = SparseArray[{{1, 1} -> 1, {i_, 1} /; i != 1 -> 0}, {n, 1}];
init = Normalize[init, Norm[#, 2] &];

(* Coin operator*)
SparseArray[{{i_, j_} /; i == j ->
1/Sqrt[2], {i_, j_} /; j == i + 1 || j == i - 1 ->
1/Sqrt[2]}, {n, n}];

(* Shift operator*)
Shift = SparseArray[{{i_, i_} -> 0, {i_, j_} /; j == i + 1 ->
1, {i_, j_} /; j == i - 1 -> 1}, {n, n}];

(* No. of steps*)
steps = 30;

(* Quantum walk & store probability distribution for each
step*)

• NestList would be much better than AppendTo here. Commented Mar 19, 2023 at 10:50