We investigate the problem of bounding the quantum process fidelity given bounds on the fidelities between target states and the action of a process on a set of pure input states. We formulate the problem as a semidefinite program and prove convexity of the minimum process fidelity as a function of the errors on the output states. We characterize the conditions required to uniquely determine a process in the case of no errors, and derive a lower bound on its fidelity in the limit of small errors for any set of input states satisfying these conditions. We then consider sets of input states whose one-dimensional projectors form a symmetric positive operator-valued measure (POVM). We prove that for such sets the minimum fidelity is bounded by a linear function of the average output state error. The minimal non-orthogonal symmetric POVM contains $d+1$ states, where $d$ is the Hilbert space dimension. Our bounds applied to these states provide an efficient method for estimating the process fidelity without the use of full process tomography.