quantum walk search algorithm we define the new step operator $U''=DU'$, and write the final state of the system after $t$ steps as $$\begin{gathered}
  (U'')^t {\left|\psi_0\right>} = \\
\eta^t \cos(\omega'_0t) {\left|\psi_0\right>}- \eta^t
  \sin(\omega'_0t){\left|\psi_1\right>} 
  + \eta^t O\left(\frac{n^{3/4}}{\sqrt{2^n}}\right)
  {\left|\tilde{r}\right>}. \end{gathered}$$ Adopting the notation of Ref. [@shenvi:052307], the probability of measuring the target state ${\left|x=0\right>}$ at the output after $t$ steps can be expressed as $$\begin{gathered}
p_n(\eta,t) = \sum_{d=0}^{n-1} \left|\left< d,0 \left| (U'')^t \psi_0
    \right.\right> \right|^2 \\ 
= \eta^{2t} \sin^2 (\omega'_0 t)
    \left|\left<\left. R,0 \right| \psi_1\right> \right|^2 + 2^{-n}
    \eta^{2t} \cos^2 (\omega'_0t) \\
+ O(1/2^n).
\label{eq:prob_uniform}\end{gathered}$$ We know from Ref. [@shenvi:052307] that $\left|\left<\left.
R,0\right| \psi_1 \right>\right|^2 = 1/2 - O(1/n)$. Since an overall exponential drop of the success probability is expected due to the $\eta^{2t}$ factor, we search for the maximum $t_f$ be before the ideal time-point $|\omega'_0|t=\pi/2$. This guarantees that $\sin^2
(\omega'_0 t_f)$ is finite, therefore due to the $2^{-n}$ factor for large $n$ the second term can be omitted, and it is sufficient to maximize the function $$p_n(\eta,t) = \eta^{2t} \sin^2 (\omega'_0t) \left( 1/2 - O(1/n) \right),
\label{eq:prob_uniform_approx}$$ with respect to $t$. After substituting the result $|\omega'_0| =
1/\sqrt{2^{n-1}}[ 1 - O(1/n) ] \pm O(n^{3/2}/2^n)$ from Ref. [@shenvi:052307], these considerations yield 