Motivated by black hole physics, we study the relationship between quantum chaos, holographic complexity, and pseudo randomness. First, we develop a diagnostic of quantum chaos by directly considering the time evolution of a simple local operator. This leads us to out-of-time-order correlation functions as a natural measure of quantum chaos. We explain how such correlators are natural probes of the black hole interior in holography. Using tools from quantum information, we use a generalization of these correlators to develop a lower bound on the computational complexity of an ensemble of unitary operators. Finally, we introduce a conjecture that the quantum complexity of a holographic state is dual to the space-time action of the black hole interior.