  Assessment of practical quantum information processing (QIP) remains partial
without understanding limits imposed by noise. Unfortunately, mere description
of noise grows exponentially with system size, becoming cumbersome even for
modest sized systems of imminent practical interest. We fulfill the need for
estimates on performing noisy quantum state preparation, verification, and
observation. To do the estimation we propose fast numerical algorithms to
maximize the expectation value of any $d$-dimensional observable over states of
bounded purity. This bound on purity factors in noise in a measurable way. Our
fastest algorithm takes $O(d)$ steps if the eigendecomposition of the
observable is known, otherwise takes $O(d^3)$ steps at worst. The algorithms
also solve maximum likelihood estimation for quantum state tomography with
convex and even non-convex purity constraints. Numerics show performance of our
key sub-routine (it finds in linear time a probability vector with bounded norm
that most overlaps with a fixed vector) can be several orders of magnitude
faster than a common state-of-the-art convex optimization solver. Our work
fosters a practical way forward to asses limitations on QIP imposed by quantum
noise. Along the way, we also give a simple but fundamental insight, noisy
systems (equivalently noisy Hamiltonians) always give higher ground-state
energy than their noiseless counterparts.
