Stochastic Pauli-path simulator for large-scale quantum optimization

Technical Summary: Stochastic Pauli-path Simulator for Large-scale Quantum Optimization

Problem Statement
Classical simulation of quantum circuits is essential for developing quantum algorithms, particularly in the "low-magic" regime where Pauli-based simulation (PBS) methods have shown promise. However, existing PBS approaches, specifically truncation-based PBS (Tb-PBS) methods like Pauli propagation simulators, are primarily designed for forward simulation (estimating expectation values) rather than optimization-driven tasks. In variational quantum algorithms (VQAs), such as Variational Quantum Eigensolvers (VQEs) and Quantum Neural Networks (QNNs), parameters are updated via gradient-based optimizers.

The paper identifies a fundamental limitation in Tb-PBS methods: while they can approximate expectation values with arbitrary precision by truncating the Pauli path space, the resulting gradients are often systematically biased. Theoretical analysis demonstrates that paths negligible for the expectation value can still dominate the gradient, leading to optimization trajectories that deviate significantly from the exact gradient descent path. This bias accumulates, causing macroscopic optimization errors and preventing faithful simulation of large-scale quantum optimization.

Methodology: Stochastic Pauli-path Simulator (SPPS)
To address the gradient bias inherent in truncation methods, the authors propose the Stochastic Pauli-path Simulator (SPPS). Unlike Tb-PBS, which constructs a reduced subset of paths, SPPS operates by sampling propagation paths from the full path space during Heisenberg evolution and correcting for sampling probabilities via importance reweighting.

The SPPS framework consists of three core procedures:

1. Hierarchical Path Sampling: Instead of constructing the full propagation tree, SPPS samples paths hierarchically. At each step of the circuit evolution, if a Pauli operator commutes with the current gate, the path is deterministic. Otherwise, branches are sampled with probabilities designed to ensure non-zero sampling for all branches, including those with small coefficients but potentially significant gradient contributions. A regularization parameter $a > 0$ ensures that derivative-sensitive branches are not overlooked.
2. Importance Reweighting: To convert sampled paths into an unbiased estimator of the expectation value, each sampled path's contribution is divided by its sampling probability. This yields an unbiased estimator for the objective function.
3. Path Automatic Differentiation (PAD): To obtain unbiased stochastic gradients, the authors introduce PAD. By exploiting the trigonometric structure of the path coefficients, PAD computes gradient samples simultaneously for all parameters without differentiating through the full tree or using parameter-shift rules for each entry. The gradient estimator is a weighted sum of the path contributions, where weights are derived from the cotangent and tangent of the rotation angles.

Theoretical Contributions
The paper provides rigorous theoretical guarantees for SPPS:

• Unbiasedness: Theorem 2 proves that SPPS yields unbiased gradient estimates. In contrast, Theorem 1 formally establishes that Tb-PBS methods can achieve arbitrary accuracy in function value estimation while retaining non-negligible gradient bias.
• Sample Complexity: The sample complexity of SPPS is bounded by $\tilde{O}((1 + 2a)L\kappa(\theta)L/(a\epsilon^2))$, where $\kappa(\theta)$ is an effective branching factor dependent on circuit parameters. This indicates that when $\kappa(\theta)$ remains moderate (polynomial in system size), a polynomial sampling budget suffices.
• Convergence: Corollary 2 provides the first convergence guarantee for quantum optimization driven by a classical simulator beyond the exact regime. It shows that SPPS-driven gradient descent finds an approximate stationary point with iteration complexity polynomial in the circuit depth and observable norm.

Experimental Results
The authors evaluated SPPS on two primary benchmarks: pre-training VQEs for the Transverse-Field Ising Model (TFIM) and pre-training QNNs for supervised learning tasks.

• VQE Benchmarks: Experiments were conducted on systems ranging from 15 to 100 qubits. SPPS faithfully tracked the optimization dynamics of exact gradient descent, converging to low energy errors (e.g., $\epsilon_0 \approx 2^{-8}$ for 15 qubits) within minutes. In contrast, Tb-PBS methods (CT, FT, WT) exhibited biased trajectories, often plateauing at higher error levels or showing non-monotonic behavior. SPPS demonstrated superior accuracy-runtime trade-offs, being up to eight times faster than CT-PBS at 100 qubits while achieving significantly lower energy errors.
• QNN Benchmarks: On a 40-qubit supervised learning task, SPPS achieved a training Mean Squared Error (MSE) below $2^{-7}$ and a test $R^2$ score of approximately 0.8. Reference Tb-PBS methods saturated at higher MSE levels ($\approx 2^{-6}$) with lower $R^2$ scores ($\approx 0.4$). SPPS completed these tasks in under 30 seconds, whereas Tb-PBS methods required over $2^{11}$ seconds.
• Scalability: The performance advantage of SPPS increased with system size and problem hardness (e.g., varying magnetic field strengths in TFIM), where Tb-PBS errors doubled while SPPS errors decreased.

Significance and Claims
The paper claims that SPPS redefines the classical boundary for utility-scale quantum experiments by extending Pauli-based simulation from forward estimation to large-scale quantum optimization. Its primary significance lies in:

1. Solving the Gradient Bias Dilemma: It resolves the trade-off between accurate mean-value estimation and faithful gradient estimation, a limitation previously inherent to truncation-based methods.
2. Enabling Classical-First Optimization: By providing unbiased gradients with provable convergence, SPPS offers a practical route for "classical-first" optimization. This allows for the pre-training of variational algorithms and the initialization of parameters on classical hardware, substantially reducing the quantum resources required for deployment on real devices.
3. Scalability: The method successfully scales to 100-qubit systems, demonstrating that faithful classical simulation of gradient-driven quantum optimization is feasible when the trajectory-dependent path complexity is moderate.

The authors conclude that SPPS provides a reliable, scalable, and efficient framework for simulating large-scale quantum optimization, bridging the gap between classical simulation capabilities and the needs of variational quantum algorithms.