Pauli path simulations of noisy quantum circuits beyond average case

For random quantum circuits on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> qubits of depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&amp;#x0398;</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method \cite{Aharonov2023_paulipaths} . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>&amp;#x2013;</mml:mtext></mml:math> 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.