Limits of quantum run-time advantage