Classical heuristics for out-of-time-ordered correlators in random circuits

The out-of-time-ordered correlator exhibits the hallmarks of a potentially useful observable that is only accessible to quantum computers: the signal is large in large quantum circuits and is sensitive to the details of the dynamics. Seemingly, random circuits are a natural first step for demonstrating quantum advantage in computing OTOCs, as the rapid growth of entanglement thwarts standard tensor network techniques. In this talk, we detail a new class of classical heuristic algorithms which outperforms other classical techniques for computing OTOCs in random circuits, and explain the principle underlying their success — namely, a lack of interference between Pauli trajectories. In addition, we use the statistical model that results from exact averages over the random gate choices to quantitatively predict the accuracy of these approximate algorithms.