With the help from Stephen Luttrell in stackexchange, I can give an intuitive expression of quantum walk, as shown in the Mathematica codes below.

Needs["Notation`"]
Notation[ParsedBoxWrapper[
RowBox[{
RowBox[{
RowBox[{
RowBox[{"\[LeftBracketingBar]", "spin_"}], "\[RightAngleBracket]"}], 
   "\[CircleTimes]", 
RowBox[{"\[LeftBracketingBar]", "index_"}]}], 
 "\[RightAngleBracket]"}]] \[DoubleLongLeftRightArrow] 
ParsedBoxWrapper[
RowBox[{"state", "[", 
RowBox[{"spin_", ",", "index_"}], "]"}]]]
H[state[spin : ("\[UpArrow]" | "\[DownArrow]"), index_]] := 
1/Sqrt[2] state["\[UpArrow]", index] + 
1/Sqrt[2] If[spin == "\[UpArrow]", 1, -1] state["\[DownArrow]", 
 index];
S[state[spin : ("\[UpArrow]" | "\[DownArrow]"), index_]] := 
state[spin, index + If[spin == "\[UpArrow]", 1, -1]];
H[u_ + v_] := H[u] + H[v];
S[u_ + v_] := S[u] + S[v];
H[u_?(FreeQ[#, state] &) v_] := u H[v];
S[u_?(FreeQ[#, state] &) v_] := u S[v];
state["\[DownArrow]", 0]
H[%];
S[%];
H[%];
S[%];
H[%];
S[%];
H[%];
S[%] // Simplify

The result (the fourth step in quantum walk) is Based on the previous codes, now I have a new problem :

First, I need to merge the elements with the same \[LeftBracketingBar]index\[RightAngleBracket], and rearrange the elements in an increasing order of \[LeftBracketingBar]index\[RightAngleBracket]. For example, in the fourth step, should be merged and rearranged as

Second, I need to summarize the coefficient and calculate the intensity for each \[LeftBracketingBar]index\[RightAngleBracket]. The intensity is square of the coefficient of \[LeftBracketingBar]"\[DownArrow]"\[RightAngleBracket], puls the square of the coefficient of \[LeftBracketingBar]"\[UpArrow]"\[RightAngleBracket]. For example, in the fourth step, the intensity is

1/16 (1; 9 + 1; 1 + 1; 1 + 1; 1)=(1/16; 5/8; 1/8; 1/8; 1/16)

My final goal is to make the following table, which is the famous quantum walk table. The x axis is the position, and the y axis is the step number.

My question is how to summarize the coefficient in Notation using Mathematica codes? Any help or suggestion is highly appreciated.

With the help from Stephen Luttrell in stackexchange, I can give an intuitive expression of quantum walk, as shown in the Mathematica codes below.

Needs["Notation`"]
Notation[ParsedBoxWrapper[
RowBox[{
RowBox[{
RowBox[{
RowBox[{"\[LeftBracketingBar]", "spin_"}], "\[RightAngleBracket]"}], 
   "\[CircleTimes]", 
RowBox[{"\[LeftBracketingBar]", "index_"}]}], 
 "\[RightAngleBracket]"}]] \[DoubleLongLeftRightArrow] 
ParsedBoxWrapper[
RowBox[{"state", "[", 
RowBox[{"spin_", ",", "index_"}], "]"}]]]
H[state[spin : ("\[UpArrow]" | "\[DownArrow]"), index_]] := 
1/Sqrt[2] state["\[UpArrow]", index] + 
1/Sqrt[2] If[spin == "\[UpArrow]", 1, -1] state["\[DownArrow]", 
 index];
S[state[spin : ("\[UpArrow]" | "\[DownArrow]"), index_]] := 
state[spin, index + If[spin == "\[UpArrow]", 1, -1]];
H[u_ + v_] := H[u] + H[v];
S[u_ + v_] := S[u] + S[v];
H[u_?(FreeQ[#, state] &) v_] := u H[v];
S[u_?(FreeQ[#, state] &) v_] := u S[v];
state["\[DownArrow]", 0]
H[%];
S[%];
H[%];
S[%];
H[%];
S[%];
H[%];
S[%] // Simplify

The result (the fourth step in quantum walk) is Based on the previous codes, now I have a new problem :

First, I need to merge the elements with the same \[LeftBracketingBar]index\[RightAngleBracket], and rearrange the elements in an increasing order of \[LeftBracketingBar]index\[RightAngleBracket]. For example, in the fourth step, should be merged and rearranged as

Second, I need to summarize the coefficient and calculate the intensity for each \[LeftBracketingBar]index\[RightAngleBracket]. The intensity is square of the coefficient of \[LeftBracketingBar]"\[DownArrow]"\[RightAngleBracket], puls the square of the coefficient of \[LeftBracketingBar]"\[UpArrow]"\[RightAngleBracket]. For example, in the fourth step, the intensity is

1/16 (1; 9 + 1; 1 + 1; 1 + 1; 1)=(1/16; 5/8; 1/8; 1/8; 1/16)

My final goal is to make the following table, which is the famous quantum walk table. The x axis is the position, and the y axis is the step number.

My question is how to summarize the coefficient in Notation using Mathematica codes? Any help or suggestion is highly appreciated.