Half the Interference, Most of the Answer: Approximate Quantum Simulation via Path-Sum Pruning
Abstract
Classical simulation of quantum circuits is expensive for two distinct reasons. The obvious one is state-space size: an n-qubit system requires exponentially many amplitudes. The less obvious one is interference: useful output distributions emerge only after many computational histories have been coherently combined at common endpoints, and this aggregation step is itself a substantial source of cost. We introduce statistical interference sampling, a framework that makes this second bottleneck explicit by treating endpoint interference as a separately schedulable computation. Using the Chemical Abstract Machine (ChAM) as our model, weighted path contributions evolve as concurrent molecular species, and interference reactions combine contributions that share a common output state. A threshold rule terminates the process once an endpoint accumulates sufficient amplitude, discarding the remaining reactions. The method does not improve worst-case complexity and is not intended as a general-purpose simulator. Its purpose is to ask a more targeted question: how much of the interference calculation can be skipped while still recovering a useful output distribution? On benchmark circuits for Deutsch-Jozsa, Grover search, Simon's problem, and small Shor period-finding instances, we find that nearly 50% of endpoint interference reactions can be omitted while maintaining over 90% output accuracy for most algorithms tested. These results suggest that interference arithmetic is a structured resource that admits meaningful approximation, and that exposing it explicitly opens new opportunities for pruning strategies across path-sum, Pauli-path, and tensor-network simulation methods.
Versions
Related
- Simulation-free approximate Bayesian computation for stochastic reaction networks
- Novel Mixed Approximate Deconvolution Large-Eddy Simulation Models for Two-Phase Flows
- Localized Decoherence as a Constructive Tool: An Optical Simulation of Matter-Wave Interference
- Quantum Circuit Pruning: From NISQ Architectures to Fault-Tolerant Operations
- ConQUESTA: Topology-Aware Post-Training Structural Pruning of Quantum Neural Networks
BibTeX
@misc{pehlivanoglu2026half,
title = {{Half the Interference, Most of the Answer: Approximate Quantum Simulation via Path-Sum Pruning}},
author = {Sinan Pehlivanoglu and Srinivasan Iyengar and Amr Sabry},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.01922},
eprint = {2606.01922},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.01922},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Half the Interference, Most of the Answer: Approximate Quantum Simulation via Path-Sum Pruning
AU - Sinan Pehlivanoglu
AU - Srinivasan Iyengar
AU - Amr Sabry
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2606.01922
UR - https://arxiv.org/abs/2606.01922
AB - Classical simulation of quantum circuits is expensive for two distinct reasons. The obvious one is state-space size: an n-qubit system requires exponentially many amplitudes. The less obvious one is interference: useful output distributions emerge only after many computational histories have been coherently combined at common endpoints, and this aggregation step is itself a substantial source of cost. We introduce statistical interference sampling, a framework that makes this second bottleneck explicit by treating endpoint interference as a separately schedulable computation. Using the Chemical Abstract Machine (ChAM) as our model, weighted path contributions evolve as concurrent molecular species, and interference reactions combine contributions that share a common output state. A threshold rule terminates the process once an endpoint accumulates sufficient amplitude, discarding the remaining reactions. The method does not improve worst-case complexity and is not intended as a general-purpose simulator. Its purpose is to ask a more targeted question: how much of the interference calculation can be skipped while still recovering a useful output distribution? On benchmark circuits for Deutsch-Jozsa, Grover search, Simon's problem, and small Shor period-finding instances, we find that nearly 50% of endpoint interference reactions can be omitted while maintaining over 90% output accuracy for most algorithms tested. These results suggest that interference arithmetic is a structured resource that admits meaningful approximation, and that exposing it explicitly opens new opportunities for pruning strategies across path-sum, Pauli-path, and tensor-network simulation methods.
ER -