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.
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.
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.
Classical computer simulations of quantum systems are not efficient-well-known examples range from the Hubbard model to lattice QCD-and Feynman argued that quantum simulations would do far better [1].The essence of the argument is that quantum simulations sum multiple evolutionary paths (in superposition) contributing to a quantum process at one go, while classical simulations evaluate these paths one by one.Formalisation of this advantage for simulating physical Hamiltonians, in terms of computational complexity, has improved over the years step by step [2,3,4,5,6].Here, treating Grover's quantum search algorithm as a Hamiltonian evolution problem, we expose the physical reasons behind the improvement in computational complexity.Computational complexity of a problem is a measure of the resources needed to solve it.Conventionally, the computational complexity of a decision problem is specified in terms of the size of its input, noting that the size of its output is only one bit.Problems with different output requirements are reduced to a sequence of decision problems, with gradually narrowing bounds on the output adding one bit of precision for every decision made.In such a scenario, the number of decision problems solved equals the number of output bits, and it is appropriate to specify the complexity of the original problem in terms of the size of its input as well as its output.Generalising the conventional classification, the computational algorithm then can be labeled efficient if the required resources are polynomial in terms of the size of both its input and its output.Popular importance sampling methods are not efficient according to our criterion, because the number of iterations needed in the computational effort has a negative power-law dependence on the precision ε (i.e.N iter ∝ ε -2 as per the central limit theorem).On the other hand, finding zeroes of a function by bisection is efficient (i.e.N iter ∝ log ε), and finding them by Newton's method is super-efficient (i.e.N iter ∝ log log ε). PoS(LATTICE2014)324 Optimisation of Quantum Evolution AlgorithmsApoorva Patel
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.