Cumulative hybrid distance for a T-query algorithm

If $T=0$, both inputs give the same circuit and hence the final vectors agree, so the inequality holds with empty sum. Suppose $T\ge 1$. For each $r=0,\dots ,T$, define $h_r$ as the final state of the circuit that uses the zero oracle in its first $r$ query slots and the $e_i$ oracle in its remaining $T-r$ slots. Then $h_0={\psi }_T^i$ and $h_T={\psi }_T^0$.

For each $1\le r\le T$, the circuits defining $h_{r-1}$ and $h_r$ have the same state immediately before query slot $r$: they have used the zero oracle for the first $r-1$ calls. This pre-query state is ${\psi }_{r-1}^0$. At slot $r$ the oracle changes from $O_{e_i}$ to $O_{0^N}$; after that slot both circuits use the same suffix, whose unitaries preserve norm. By [F2], $\mathrm{\parallel }{h}_{r-1}-h_r\mathrm{\parallel }\le 2\sqrt{q_{r-1,i}}$.

The triangle inequality gives $\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0\mathrm{\parallel }=\mathrm{\parallel }{h}_0-h_T\mathrm{\parallel }\le {\sum }_{r=1}^T\mathrm{\parallel }{h}_{r-1}-h_r\mathrm{\parallel }\le 2{\sum }_{t=0}^{T-1}\sqrt{q_{t,i}}$. The normal form [F1] preserves the output distribution, so this bound applies to the original algorithm's pure-state realization.