Random Quantum Circuits and Their Simulation Complexity: an Analysis with Statistical Mechanics

Random circuit simulation, the task of replicating the output of a randomly chosen noiseless quantum computation, has been proposed as a path toward achieving quantum advantage: it is believed to be easy for quantum devices, but hard for classical ones. This thesis scrutinizes both sides of this belief. On the one hand, we investigate whether the task is classically hard—we find that, in certain non-trivial cases, it can actually be easy, complicating a potential general proof of hardness. On the other hand, we investigate whether the task can be easily accomplished on realistic quantum devices, which are subject to substantial noise rates—we find that, indeed, a version of the circuit simulation task can be salvaged even on a noisy quantum device performing the computation with low fidelity, as long as the noise meets certain conditions. Thus, this thesis emphasizes that, to construct a strong argument of quantum advantage via random circuit simulation on noisy quantum hardware, the core theoretical challenge remains proving lower bounds on the classical complexity of the task; doing so will require new ideas to circumvent the barriers presented by our work. A key analytical technique we utilize for each of our results is the statistical mechanics method for random quantum circuits, which maps random quantum circuits made from local Haar-random gates to partition functions of classical statistical mechanical systems. This thesis demonstrates the utility of this method by applying it in several new ways. In some cases, we use it for heuristic reasoning about the behavior of random quantum circuits. In others, we go further and perform rigorous calculations of the resulting partition function, leading to precise technical conclusions about random quantum circuits, such as sharp bounds on the number of random gates needed to achieve the anti-concentration property.