arXiv:2610.27768
Bidirectional Path Integral Monte Carlo Simulation of Quantum Circuits
Luis Paulo Santos, Thomas Bashford-Rogers
Abstract
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.
AI Summary
The paper studies whether bidirectional Monte Carlo sampling can improve classical estimation of circuit transition amplitudes $\langle\Psi_f|U|\Psi_0\rangle$ while retaining the $\mathcal{O}(nL)$ memory cost of Feynman-path methods. It adapts bidirectional path tracing from computer graphics: random walks start at both computational-basis endpoints, and their segments are connected across each circuit layer. Multiple importance sampling combines the probabilities of generating a path through different connection choices, aiming to reduce variance from rare contributing paths. Experiments compare this estimator with forward-only importance sampling on IQP kernel circuits with 5–25 qubits and random Clifford+T circuits with 8–12 qubits, using five runs per configuration. Reported variance reductions at equal execution time range from one to six orders of magnitude. Additional tests estimate known transition amplitudes of classically tractable hidden-shift circuits with 256, 1024, and 4096 qubits, all of depth 43. With $2^{24}$ bidirectional samples, the 4096-qubit case takes about 29.5 minutes on 16 nodes with 128 cores each and has reported variance $4\times10^{-3}$; forward sampling finds no nonzero paths within $2^{26}$ samples. Tests on 500 eight-qubit random circuits examine dependence on sparsity and phase cancellation. The stated benefit is improved discovery and weighting of nonzero paths, not resolution of the numerical sign problem: destructive interference can still require exponentially many samples. The study treats ideal noiseless circuits; extension to noisy evolution, including the role of reversibility, remains future work.
Central claim may not hold: Equation BS_estimator and Algorithm BS divide by NL instead of N, so even with otherwise correct amplitudes and MIS probabilities their expectation is the desired transition amplitude divided by circuit depth L. Equation ISPT_f defines a path's amplitude using squared magnitudes of gate matrix elements, eliminating the phases needed to estimate a complex transition amplitude. Equation BD-amps uses backward adjoint matrix elements without conjugating them back, producing incorrect path amplitudes for general complex-valued gates. Algorithm BS computes alternative-strategy probabilities from the original sampled segments rather than evaluating them on each recombined path, which is required for the stated MIS estimator.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.