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.
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.
We present a distributed method for exact sparse-output quantum circuit simulation based on the pure Feynman sum-over-histories formulation. The method computes selected computational-basis amplitudes exactly and addresses the exponential growth of the path sum through a reduced history formulation based on internal-wire assignments, determinism propagation, artificial sources, pruning, and checkpointed reuse. Boundary constraints are propagated through deterministic and wire-preserving gates, and explicit branching variables are introduced only where residual ambiguity remains. Shared work across related histories is captured via an autotuned checkpointed partition. The parallel execution model combines decomposition over requested outputs with concurrent history evaluation, while a dynamic server-worker architecture mitigates load imbalance from irregular branching and pruning. Across the circuit families studied, the method adapts to different structural regimes of the reduced history space: zero artificial sources for QFT under backward analysis, substantial speedups from checkpointing and autotuning for amplitude amplification, and a runtime-fidelity tradeoff from threshold pruning for QAOA. On quantum walk circuits, it reconstructs exact selected-output distributions up to 100 qubits and achieves 85% parallel efficiency on 8,192 CPU cores of a supercomputer.
Introduction: We introduce a novel quantum-inspired simulator that approximates the Feynman path integral within a discrete, graph-theoretic framework, mapping logical qubits to graph vertices. Materials and methods: The entire pathfinding process is driven by gate operations, forming the core of our unique, three-tier search: (1) classical path probability boosting to identify primary routes, (2) Feynman-inspired vertex amplification to weight critical nodes, and (3) complex amplitude calculations, based on logical qubit interactions (edge-weighted), which are crucial for reproducing quantum interference. Results: While methods (1) and (2) identify the shortest classical paths, only the third tier successfully approximates superposition and interference effects through complex amplitude summation, where distinct phase contributions lead to either amplification or suppression. We show that interference patterns align with pairwise Pauli-Z correlations that effectively emulate entanglement phenomena. High gate dynamism, especially 4-qubit gate operations, are essential for the broad search of optimal routes, while boundary conditions may limit continuous exploration and refinement of pathways, emphasizing the need for fine parameter tuning. Simulations achieve convergence, with entropy plateaus confirming stability given a sufficient tolerance threshold for systems up to 8 vertices. The temporal evolution of vertex occurrence counts exhibits Gamma–Poisson (Cox process) statistics, with variance-to-mean ratios increasing over time, indicating non-Poissonian dynamics. A key finding is that quantum pathfinding, driven by destructive interference, effectively reveals dominant paths that may not be classically apparent. The observed destructive interference directly results from the summation of complex amplitudes where the phase differences equal approximately π radians (180), revealing complementary path and “anti-path” structures. Conclusions: The novelty of our simulator lies in its dual vertex-wave nature that provides new insights for quantum algorithm design and the study of quantum dynamics. Beyond the core framework, structural and mathematical analogies emerging from Simulation H—including a correlation structure consistent with a light-cone pattern—are reported as posthoc observations of the simulation output. These are not physical derivations, but suggest directions for further investigation at the intersection of graph-theoretic quantum simulation and relativistic quantum mechanics.
We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩, based on Monte Carlo sums over bidirectionally sampled Feynman paths. The algorithm generates Feynman paths, i.e., sequences of intermediate computational basis states, by combining information from random walks initiated at both the input and output states, Ψ0 and Ψf, respectively. It further combines this bidirectional approach with Multiple Importance Sampling, a powerful variance reduction technique that avoids variance peaks caused by divisions by the very low sampling probabilities associated with hard to reach paths. Empirical data demonstrate the superior convergence rate exhibited by the bidirectional algorithm over a unidirectional, forward-only sampling approach. This superiority is due to the effectiveness of the proposed algorithm in finding and weighting paths with non-zero amplitude in an extremely sparse path space. Sum of paths algorithms exhibit very favourable space complexity. Monte Carlo replaces exhaustive enumeration of the exponentially large path space by stochastic sampling, the computational cost being determined by the variance of the estimator. This work demonstrates these two features by presenting results on very large quantum circuits, with up to 4096 qubits.
We study the separation of geometric effects from quantum interference in quantum optimization algorithms. Constrained optimization problems such as routing, assignment, and scheduling are often encoded as product spaces of local variables, together with global feasibility penalties. The central algorithmic question we address is how a constraint-preserving mixing operator transports quantum amplitude across an exponential search space in the presence of local and global constraints. We develop a framework that separates three effects that are usually intermixed: amplitude transport, coherent interference among transported amplitudes, and problem-dependent classical postprocessing. We show that the mixing operator alone does not have a target-seeking ability. Concretely, the normalized distribution induced by its amplitude transport moves toward the distance profile of a uniformly random configuration. Thus, quantum sampling advantage may only arise when the phases of the many computational paths reaching a target configuration are sufficiently aligned for their amplitudes to reinforce. We show that, when the cost phases are engineered so that these paths add coherently, a number of circuit alternations growing only logarithmically with problem size suffices to convert the sum of their absolute contributions into a lower bound on the target amplitude, yielding a certified success probability independent of the ambient Hilbert-space dimension, the search-space size, or the feasible-set cardinality. We develop applications to problem-specific transpilation diagnostics, scalable hardware probes, constraint-induced classical maps of quantum-generated samples, the attribution of solution quality between the quantum distribution and classical post-processing in hybrid quantum-classical workflows and connections to distance-partitioned product spaces from classical coding theory.
We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩, based on Monte Carlo sums over bidirectionally sampled Feynman paths. The algorithm generates Feynman paths, i.e., sequences of intermediate computational basis states, by combining information from random walks initiated at both the input and output states, Ψ0 and Ψf, respectively. It further combines this bidirectional approach with Multiple Importance Sampling, a powerful variance reduction technique that avoids variance peaks caused by divisions by the very low sampling probabilities associated with hard to reach paths. Empirical data demonstrate the superior convergence rate exhibited by the bidirectional algorithm over a unidirectional, forward-only sampling approach. This superiority is due to the effectiveness of the proposed algorithm in finding and weighting paths with non-zero amplitude in an extremely sparse path space. Sum of paths algorithms exhibit very favourable space complexity. Monte Carlo replaces exhaustive enumeration of the exponentially large path space by stochastic sampling, the computational cost being determined by the variance of the estimator. This work demonstrates these two features by presenting results on very large quantum circuits, with up to 4096 qubits.
Quantum circuit simulators running on classical computers offer a vital platform for designing, testing, and optimizing quantum algorithms, driving innovation despite limited access to real quantum hardware. However, their scalability is inherently constrained by exponential memory and computational overhead, which restricts accurate simulation of large-scale quantum circuits and often results in approximate output distributions. Here, we propose an exact sampling algorithm that integrates tensor network contraction techniques with a Markov process, wherein a classical state evolves according to the local structure of the quantum circuit. As a demonstration, we target the challenge of generating samples from ideal and noisy QAOA circuits with up to 476 qubits, incorporating both depolarizing and amplitude damping noise models. These results enable further validation of several assumptions and conjectures at a scale previously out of reach, significantly expanding the scope of classical simulation in quantum algorithm research.