Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.01467

Fewer Histories, Faster Paths: Distributed Quantum Circuit Feynman Simulation via History Reduction, Checkpointing, and Pruning

Frej Larssen, Luca Pennati, Erik M. Åsgrim, Ivy Bo Peng, Stefano Markidis

Published Aug 2, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2608.01467

Related papers

Half the Interference, Most of the Answer: Approximate Quantum Simulation via Path-Sum Pruning

Sinan Pehlivanoglu, Srinivasan Iyengar, Amr Sabry

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.

quant-pharXiv:2606.01922•Quantum Science and Technology•Jun 2, 2026•0 citations

GraFeyn: Efficient Parallel Sparse Simulation of Quantum Circuits

Sam Westrick, Pengyu Liu, Byeongjee Kang +6 more

Many circuit simulators use either a Schrodinger-based or Feynman-based approach, which have complementary strengths. Schrödinger-based simulators maintain a state vector by synchronously updating it after each gate (or group of gates), ensuring time efficiency at the cost of exponential space. In contrast, Feynman-based simulators use low space but require high time to compute the sum of exponentially many independent Feynman paths. Because they treat paths as independent, Feynman-based simulators miss opportunities to take advantage of sparsity from destructive interference. In this paper, we present a hybrid Schrödinger-Feynman technique which takes advantage of sparsity by selectively synchronizing Feynman paths. Our hybrid technique partitions the circuit into kernels (groups of gates) and uses Feynman simulation within each kernel. It then synchronizes across the kernels by using Schrödinger-style simulation. We parallelize our approach by representing the simulation as a graph, leveraging state-of-the-art parallel graph algorithms. By selecting kernels carefully, we show that our approach can simulate hundreds of qubits efficiently (in both time and space) on just a single multicore node. In certain “sparse” circuits, we are able to improve running times by multiple orders of magnitude.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•7 citations

Quantum Circuit Pruning: From NISQ Architectures to Fault-Tolerant Operations

Pau Escofet, Carmen G. Almudéver, Sergi Abadal +1 more

We present a routing-aware pruning strategy for quantum circuits that selectively removes parametric two-qubit gates whose computational contribution is outweighed by the fidelity cost of their execution, and assess it across both Noisy Intermediate-Scale Quantum (NISQ) and fault-tolerant quantum computing (FTQC) architectures. Each two-qubit gate of a circuit is evaluated by comparing an architecture-independent lower bound on the fidelity cost of omitting the gate against a hardware-specific model for the routing execution cost in each setting. We additionally provide an analytical characterization of the pruning boundary as a function of rotation angle, qubit distance, and hardware noise. Simulations on benchmark circuits demonstrate gate count reductions of up to 48.6% and fidelity improvements of up to 47.7% in the NISQ regime, while a feasibility analysis on FT hardware indicates that pruning is expected to remain relevant across a range of code distances and physical error rates. These results establish routing-aware pruning as a practical and unified compilation strategy across the quantum computing stack.

quant-pharXiv:2610.00669•IEEE Transactions on Circuits & Systems II Express Briefs•Oct 2, 2026•0 citations

Bidirectional Path Integral Monte Carlo Simulation of Quantum Circuits

Luis Paulo Santos, Thomas Bashford-Rogers

We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, $\langle Ψ_f | \hat{U} | Ψ_0 \rangle$, 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.

quant-pharXiv:2610.27768•Oct 21, 2026•0 citations

Bidirectional Path Integral Monte Carlo Simulation of Quantum Circuits

Luis Paulo Santos, Thomas Bashford‐Rogers

We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, $\langle Ψ_f | \hat{U} | Ψ_0 \rangle$, 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.

•Oct 22, 2026•0 citations

Adaptive Multi-Backend Simulation of Near-Clifford Quantum Circuits via Spatial Stabilizer-Frame Partitioning

Héctor J. García

We present an exact amplitude simulator for Clifford+T quantum circuits that combines a Feynman path sum across a balanced qubit bipartition with stabilizer-frame simulation on each half. The construction extends prior stabilizer-based Schrödinger-Feynman methods in three directions: recursive multilevel bipartition into a binary tree, automatic fallback to dense state-vector simulation when a leaf's stabilizer frame would exceed its memory ceiling, and a cost-model-driven partition selector that replaces the standard cut-count minimization heuristic. We show cut-count minimization is an unreliable proxy in practice: a globally cleaner partition can reduce cross-cut count yet increase wall-clock time, because it imbalances T-gate density across halves and inflates per-half stabilizer-frame size. Our cost model substitutes the stabilizer-frame bound 2w for the dense 2n ceiling per side and explicitly models per-amplitude readout cost; isolating that term uncovered a quadratic-asymptotic inefficiency in the leaf simulator's end-of-path amplitude extraction, fixed by replacing it with an existing O(F * s * n) single-amplitude inner product. On a structured hierarchical n=16 benchmark the recursive simulator beats monolithic stabilizer-frame simulation by 92x to 17,645x, wins by 79x per path against a dense half-state-vector baseline under an identical cut, and beats a production state-vector simulator end to end by up to 47.9x (median ~5x). On adversarial random Clifford+T circuits the dense state vector wins past a crossover near n/2 cross-cut gates -- the regime the cost model identifies. The dominant cost, the cross-cut Feynman sum, is embarrassingly parallel with constant inter-worker communication, unlike recent matrix-product-state stabilizer-tensor methods whose inner contraction loop is sequential.

quant-pharXiv:2607.27075•Jul 30, 2026•0 citations
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.
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.
Many circuit simulators use either a Schrodinger-based or Feynman-based approach, which have complementary strengths. Schrödinger-based simulators maintain a state vector by synchronously updating it after each gate (or group of gates), ensuring time efficiency at the cost of exponential space. In contrast, Feynman-based simulators use low space but require high time to compute the sum of exponentially many independent Feynman paths. Because they treat paths as independent, Feynman-based simulators miss opportunities to take advantage of sparsity from destructive interference. In this paper, we present a hybrid Schrödinger-Feynman technique which takes advantage of sparsity by selectively synchronizing Feynman paths. Our hybrid technique partitions the circuit into kernels (groups of gates) and uses Feynman simulation within each kernel. It then synchronizes across the kernels by using Schrödinger-style simulation. We parallelize our approach by representing the simulation as a graph, leveraging state-of-the-art parallel graph algorithms. By selecting kernels carefully, we show that our approach can simulate hundreds of qubits efficiently (in both time and space) on just a single multicore node. In certain “sparse” circuits, we are able to improve running times by multiple orders of magnitude.
We present a routing-aware pruning strategy for quantum circuits that selectively removes parametric two-qubit gates whose computational contribution is outweighed by the fidelity cost of their execution, and assess it across both Noisy Intermediate-Scale Quantum (NISQ) and fault-tolerant quantum computing (FTQC) architectures. Each two-qubit gate of a circuit is evaluated by comparing an architecture-independent lower bound on the fidelity cost of omitting the gate against a hardware-specific model for the routing execution cost in each setting. We additionally provide an analytical characterization of the pruning boundary as a function of rotation angle, qubit distance, and hardware noise. Simulations on benchmark circuits demonstrate gate count reductions of up to 48.6% and fidelity improvements of up to 47.7% in the NISQ regime, while a feasibility analysis on FT hardware indicates that pruning is expected to remain relevant across a range of code distances and physical error rates. These results establish routing-aware pruning as a practical and unified compilation strategy across the quantum computing stack.
We propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩\langle Ψ_f | \hat{U} | Ψ_0 \rangle⟨Ψ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Ψ_0Ψ0​ and ΨfΨ_fΨ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 propose an approximate classical algorithm for estimating quantum circuits' transition amplitudes, ⟨Ψf∣U^∣Ψ0⟩\langle Ψ_f | \hat{U} | Ψ_0 \rangle⟨Ψ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Ψ_0Ψ0​ and ΨfΨ_fΨ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 present an exact amplitude simulator for Clifford+T quantum circuits that combines a Feynman path sum across a balanced qubit bipartition with stabilizer-frame simulation on each half. The construction extends prior stabilizer-based Schrödinger-Feynman methods in three directions: recursive multilevel bipartition into a binary tree, automatic fallback to dense state-vector simulation when a leaf's stabilizer frame would exceed its memory ceiling, and a cost-model-driven partition selector that replaces the standard cut-count minimization heuristic. We show cut-count minimization is an unreliable proxy in practice: a globally cleaner partition can reduce cross-cut count yet increase wall-clock time, because it imbalances T-gate density across halves and inflates per-half stabilizer-frame size. Our cost model substitutes the stabilizer-frame bound 2w for the dense 2n ceiling per side and explicitly models per-amplitude readout cost; isolating that term uncovered a quadratic-asymptotic inefficiency in the leaf simulator's end-of-path amplitude extraction, fixed by replacing it with an existing O(F * s * n) single-amplitude inner product. On a structured hierarchical n=16 benchmark the recursive simulator beats monolithic stabilizer-frame simulation by 92x to 17,645x, wins by 79x per path against a dense half-state-vector baseline under an identical cut, and beats a production state-vector simulator end to end by up to 47.9x (median ~5x). On adversarial random Clifford+T circuits the dense state vector wins past a crossover near n/2 cross-cut gates -- the regime the cost model identifies. The dominant cost, the cross-cut Feynman sum, is embarrassingly parallel with constant inter-worker communication, unlike recent matrix-product-state stabilizer-tensor methods whose inner contraction loop is sequential.