Out-of-time-ordered correlators (OTOC) are a quantifier of quantum information scrambling and are useful in characterizing quantum chaos. We propose an efficient quantum algorithm to measure OTOCs that provides an exponential speed-up over the best known classical algorithm provided the OTOC operator to be estimated admits an efficient gate decomposition. We also discuss a scheme to obtain information about the eigenvalue spectrum and the spectral density of OTOCs as well as an efficient algorithm to estimate gate fidelities. © 2021 Elsevier B.V.