Abstract
We study the classical simulability of a polynomial-size quantum circuit C_n on n qubits followed by sparse classical post-processing (SCP) on m bits, where m ≤ n ≤ poly(m). The SCP is described by a non-zero Boolean function f_m that is classically computable in polynomial time and is sparse, i.e., has a peaked Fourier spectrum. First, we provide a necessary and sufficient condition on C_n such that, for any SCP f_m, C_n followed by f_m is classically simulable. This characterization extends the result of Van den Nest and implies that various quantum circuits followed by SCP are classically simulable. Examples include IQP circuits, Clifford Magic circuits, and the quantum part of Simon's algorithm, even though these circuits alone are hard to simulate classically. Then, we consider the case where C_n has constant depth d. While it is unlikely that, for any SCP f_m, C_n followed by f_m is classically simulable, we show that it is simulable by a polynomial-time probabilistic algorithm with access to commuting quantum circuits on n+1 qubits. Each such circuit consists of at most deg(f_m) commuting gates and each commuting gate acts on at most 2^d+1 qubits, where deg(f_m) is the Fourier degree of f_m. This provides a better understanding of the hardness of simulating constant-depth quantum circuits followed by SCP.