I read the paper by Ambianis on variable time amplitude amplification to improve the $\kappa$ (condition number) dependency for the Quantum linear system algorithm by Childs et al..
I can see VTAA perform well compared to AA as it relies on the fact that a probabilistic algorithm can take different completion times for the same input (due to different lengths of different computational branches).
I am unable to understand how VTAA exploits this fact to improve the runtime from $O(1/\sqrt{\epsilon})T_{max}$ to $\tilde{O}(1/\sqrt{\epsilon})T_{avg}$, where, $T_{avg} = \sqrt{\sum_i{p_iT_i^2}}$.
I feel an ancillary qubit is kept (as a flag) to condition the further execution of the amplification process. Thus computation stops before the worst case of $O(\sqrt{n})$ steps/time.
Is there some criteria where VAA is better choice over AA?
