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

• URL: http://arxiv.org/abs/2603.05920v1
• Date: Fri, 06 Mar 2026 05:18:14 GMT
• Title: Classical simulability of quantum circuits followed by sparse classical post-processing
• Abstract summary: We study the simulability of a Fourier-size quantum circuit $C_n$ on $n$ qubits followed by sparse classical post-processing on $m$ bits.<n>We show that it is simulable by a probabilistic algorithm with access to commuting quantum circuits on $n+1$ qubits.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• Practical framework for simulating permutation-equivariant quantum circuits [0.0]
  We introduce a practical algorithm for $S_n$-equivariant circuits under the assumption that the gate generators are at most $k$-local, with $kin O(1)$.<n>The resulting method runs in $O(n+1)$ time for constant depth, where $$ is the matrix multiplication exponent, significantly lowering the degree compared to existing techniques.
  arXiv  Detail & Related papers  (2026-03-13T15:18:18Z)
• Linear-Size QAC0 Channels: Learning, Testing and Hardness [13.101369903953804]
  Current noisy quantum hardware can only perform faithful quantum computation for a short amount of time.<n>We present the first algorithm for $mathbfQAC0$ channels using subexponential running time and queries.<n>We also establish exponential lower bounds on the query complexity of learning $mathbfQAC0$ channels under both the spectral norm distance of the Choi matrix and the diamond norm distance.
  arXiv  Detail & Related papers  (2025-10-01T07:19:38Z)
• Strong random unitaries and fast scrambling [37.03163411089211]
  We show that strong unitary designs can form in circuit depth $O(log2 n)$ in circuits composed of independent two-qubit Haar-random gates.<n>Our results provide an operational proof of the fast scrambling conjecture from black hole physics.
  arXiv  Detail & Related papers  (2025-09-30T14:23:46Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  We present a classical algorithm for estimating expectation values of arbitrary observables on random unstructured quantum circuits.<n>Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.
  arXiv  Detail & Related papers  (2024-09-03T08:44:33Z)
• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. We prove new separations between classical and quantum constant-depth circuits. In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
  arXiv  Detail & Related papers  (2024-04-28T07:44:27Z)
• Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach [0.0]
  A good candidate for demonstrating quantum supremacy with random circuit sampling is to use emphIQP circuits. We introduce improved techniques for classically simulating random IQP circuits. We estimate that 70-qubit circuits are within reach for a large computing cluster.
  arXiv  Detail & Related papers  (2022-12-16T17:38:42Z)
• Towards Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry [12.724648200604134]
  We introduce a framework of equi convolutional quantum algorithms which is tailored for a number of machine-learning tasks.<n>It allows us to enhance a natural model of quantum computation -- permutational quantum computing (PQC) -- and define a more powerful model: PQC+.
  arXiv  Detail & Related papers  (2022-07-15T01:41:53Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
  arXiv  Detail & Related papers  (2021-12-25T20:01:54Z)
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans\"atze [13.651587339535961]
  We develop a framework for convolutional quantum circuits with SU$(d)$symmetry. We prove Harrow's statement on equivalence between $nameSU(d)$ and $S_n$ irrep bases.
  arXiv  Detail & Related papers  (2021-12-14T18:03:43Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Quantum Chaos is Quantum [1.2008527035019914]
  We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that $k=O(N)$. This result implies the impossibility of simulating quantum chaos on a classical computer.
  arXiv  Detail & Related papers  (2021-02-16T19:00:06Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  We show a strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. A key component of this reduction is showing average-case hardness for the classical simulation tasks. We show that is true even for quantum tasks which are $oplus$L-hard to simulate.
  arXiv  Detail & Related papers  (2021-02-13T00:54:45Z)
• Topological obstructions to quantum computation with unitary oracles [0.0]
  Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. We show limitations of process tomography, oracle neutralization, and $sqrt[dim U]U$, $UT$, and $Udagger$ algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements.
  arXiv  Detail & Related papers  (2020-11-19T18:52:38Z)
• Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
  Google's noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24pm0.21)times10-3$. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of quantum circuit.
  arXiv  Detail & Related papers  (2020-05-05T18:01:48Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.