Classical simulability of quantum circuits followed by sparse classical post-processing

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 \leq n \leq {\rm 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.