We demonstrate that a system's rate of fidelity decay under repeated perturbations may be measured efficiently on a quantum information processor, and analyze the conditions under which this indicator is a reliable probe of quantum chaos. The type and rate of the decay are not dependent on the eigenvalue statistics of the unperturbed system, but depend on the system's eigenvector statistics in the eigenbasis of the perturbation. For random eigenvector statistics, the decay is exponential with a rate fixed by the variance of the perturbation's energy spectrum. Hence, even classically regular models can exhibit an exponential fidelity decay under generic quantum perturbations. These results clarify which perturbations can distinguish classically regular and chaotic quantum systems.