{"id":"arxiv/2603.05920","url":"https://arxiv.org/abs/2603.05920","tags":["quant-ph","cs.CC"],"score":0,"title":"Classical simulability of quantum circuits followed by sparse classical post-processing","domain":"quant-ph","source":"arxiv","authors":["Yasuhiro Takahashi","Masayuki Miyamoto","Noboru Kunihiro"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-06","reactions":{}}