6
$\begingroup$

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*)
Hadamardg = 
  SparseArray[{{i_, j_} /; i == j -> 
     1/Sqrt[2], {i_, j_} /; j == i + 1 || j == i - 1 -> 
     1/Sqrt[2]}, {n, n}];
Hadamardg = MatrixPower[Hadamardg, 1/2];
Hadamardg = Normalize[Hadamardg, Norm[#, 1] &];

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"}]
Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Use numeric computation instead of symbolic in MatrixPower as Hadamardg = MatrixPower[Hadamardg // N, 1/2]; $\endgroup$
    – Alex Trounev
    Mar 19 at 5:50
  • 3
    $\begingroup$ Also dotting A = Shift . Hadamardg only once and then doing state = Nest[(A.#) &, init, steps]; might pay off. $\endgroup$
    – Henrik Schumacher
    Mar 19 at 6:30
  • $\begingroup$ 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 $\endgroup$
    – thils
    Mar 19 at 6:57
  • 2
    $\begingroup$ 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 . $\endgroup$
    – Henrik Schumacher
    Mar 19 at 10:00
  • 1
    $\begingroup$ 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? $\endgroup$
    – Henrik Schumacher
    Mar 19 at 10:12

1 Answer 1

Reset to default
4
$\begingroup$

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*)
Hadamardg = 
  SparseArray[{{i_, j_} /; i == j -> 
     1/Sqrt[2], {i_, j_} /; j == i + 1 || j == i - 1 -> 
     1/Sqrt[2]}, {n, n}];
Hadamardg = MatrixPower[Hadamardg // N, 1/2];
Hadamardg = Normalize[Hadamardg, Norm[#, 2] &];

(* 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*)
Aqw = Shift . Hadamardg;
state = init;
probDist = {};
Do[state = Normalize[Aqw . state, Norm[#, 2] &];
  AppendTo[probDist, Transpose[Abs[state]^2][[1]]];, {i, 1, steps}];

(*Plot probability distribution for each step in a 3D plot*)
probDist3D = 
 ListPlot3D[probDist, DataRange -> {{1, steps}, {1, n}}, 
  PlotRange -> All, 
  AxesLabel -> {"Steps", "Position", "Probability"}]

enter image description here

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ NestList would be much better than AppendTo here. $\endgroup$
    – Roman
    Mar 19 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.