by $t$ ideal steps as $${\left|\psi'(t)\right>} = \eta^t{\left|\psi(t)\right>} + {\left|r\right>}.$$ The expression of the residual vector ${\left|r\right>}$ reads $${\left|r\right>} = \sum_{k=1}^t (DU')^{t-k} D' \eta^{k-1} {\left|\psi(k)\right>}.$$ To obtain the probability of measuring the target state ${\left|x=0\right>}$ we have to evaluate the formula $$p_n(\{\eta\},t) = \sum_{d=0}^{n-1} \left| \eta^t {\left< \left. d,0\vphantom{\psi(t)} \right| \psi(t) \right>} +
{\left< \left. d,0\vphantom{r} \right| r \right>} \right|^2.
\label{eq:inhomo-prob-def}$$ Due to the symmetry of the graph and the coins, we use e.g.Eq. (\[eq:prob\_uniform\_approx\]) and obtain ${\left< \left. d,0\vphantom{\psi(t)} \right| \psi(t) \right>}
\approx -\sin(\omega'_0t)/\sqrt{2n}$. To obtain a lower bound on $p_n(\{\eta\},t)$ we note that the sum is minimal if ${\left< \left. d,0\vphantom{r} \right| r \right>}=\textrm{const}=K$ for every $d$ (we consider a worst case scenario when all ${\left< \left. d,0\vphantom{r} \right| r \right>}$ are negative). Now we assume that the second term is a correction with an absolute value smaller than that of the first term. For the upper bound on $K$, we use the inequality $$\sum_{d=0}^{n-1} \left| {\left< \left. d,0\vphantom{r} \right| r \right>} \right|^2 \le {\left< \left. r\vphantom{r} \right| r \right>}.$$ The norm of ${\left|r\right>}$ can be bound using the eigenvalues of $U$, $D$, and $D'$. Let $\etamax = \max {\left\lbrace \eta_d |
d=0,\ldots,n-1 \right\rbrace}$ and $\delta_{\mathrm{max}} = \max
