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). enter image description here

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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.