  The hope of the quantum computing field is that quantum architectures are
able to scale up and realize fault-tolerant quantum computing. Due to
engineering challenges, such "cheap" error correction may be decades away. In
the meantime, we anticipate an era of "costly" error correction, or early
fault-tolerant quantum computing. Costly error correction might warrant
settling for error-prone quantum computations. This motivates the development
of quantum algorithms which are robust to some degree of error as well as
methods to analyze their performance in the presence of error. We introduce a
randomized algorithm for the task of phase estimation and give an analysis of
its performance under two simple noise models. In both cases the analysis leads
to a noise threshold, below which arbitrarily high accuracy can be achieved by
increasing the number of samples used in the algorithm. As an application of
this general analysis, we compute the maximum ratio of the largest circuit
depth and the dephasing scale such that performance guarantees hold. We
calculate that the randomized algorithm can succeed with arbitrarily high
probability as long as the required circuit depth is less than 0.916 times the
dephasing scale.
