Pauli path simulations of noisy quantum circuits beyond average case

For random quantum circuits on n qubits of depth (logn) with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method Aharonov2023ₚaulipaths. This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.