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:2610.21000

monoprop: Scaling Pauli and Majorana propagation via Anticommutation Indices

Aaron Miller

quant-phcond-mat.str-elSubmitted Oct 14, 2026• Announced Oct 16, 2026• 1 citation
arXivHTMLPDF

Abstract

We introduce monoprop, an open-source, massively parallel operator-propagation framework for fermion and qubit bases. For $N$ qubits or modes, existing codes represent each of the $K$ tracked operator terms (Pauli strings or products of Majorana operators) as a $2N$-bit string, testing each for anticommutation with the gate at $O(KN)$ cost per gate. Here, we introduce the anticommutation index which rapidly looks up the terms anticommuting with a gate. A local gate changes only the terms that touch its sites, and when terms are truncated to act on few sites, only a fraction $\sim1/N$ touch any given qubit or mode, and we use this to prove the time per gate scales as $O(K/N)$. This counterintuitive result tells us that for a fixed number of terms, increasing the number of sites can make things faster. We demonstrate this numerically, and show monoprop scales almost ideally to 8192 cores, tracking $9.5\times10^{10}$ terms. Beyond propagation, we present memory-efficient surrogate graphs, which record one propagation and replay it at new angles, for fast energy re-estimation and parameter gradients, and an efficient method for finding energy-minimising gates and optimal angles for simulating adaptive quantum-chemistry circuits.

AI Summary

Operator propagation approximates circuit expectation values by evolving sparse Pauli or Majorana expansions. This paper addresses the cost of finding and updating terms that anticommute with each gate, introducing `monoprop`, an open-source C++/Python framework with MPI parallelisation. Its central data structure is an anticommutation index: lists of tracked terms occupying each operator position. Taking the symmetric difference of the lists selected by a gate identifies anticommuting terms without scanning the entire expansion. For $K$ terms of bounded degree and local Pauli or even-Majorana gates, the proved per-gate cost is $O(K/N)$ when position occupancies remain balanced, and $O(K)$ in the worst case, versus the paper’s $O(KN)$ dense-bitstring baseline. Sparse term storage requires $O(d)$ rather than $O(N)$ memory per term. Single-core kicked-Ising and Hubbard benchmarks exhibit approximately inverse-system-size cost per tracked term, with reported speedups of $24$–$149\times$ at selected sizes. Distributed Hubbard benchmarks track $9.47\times10^{10}$ terms on 8192 cores, retaining 94% weak-scaling efficiency for the largest workload. Recorded surrogate graphs evaluate energies and all-parameter gradients in roughly 0.1 and 0.2 times propagation time. A separate Fock-reference gate-selection algorithm reduces exhaustive scoring from $O(N^{d+g})$ to expected $O(N^{(d+g)/2})$, supported by enumeration proofs and timing fits. The inverse-size bound requires bounded support and balanced occupancies, which are not guaranteed dynamically. The study benchmarks performance rather than physical accuracy or optimisation outcomes. Diagonal-term cutoff exemptions qualify degree-based bounds; gate-selection functionality is not yet included in the public release.

No sign of AI-generated textAI use disclosedStrong assumptions
The author used Claude to improve clarity and to simplify long-winded proofs and for presentation.

Central claim may not hold: The abstract's O(K/N) per-gate claim requires an additional occupancy condition, such as the theorem's evenly supported operator assumption; bounded-degree terms and local gates alone permit Ω(K) work. The introduction incorrectly describes lookup time as proportional to the anticommuting output size, whereas commuting terms occurring in multiple selected lists can require substantial work even when that output is empty.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
9 pages, 6 figures

Related papers

Practical gates by Majorana fermion motion

Yuri D. Lensky, Bryce Kobrin, Kostyantyn Kechedzhi +1 more

Quantum error correction protocols protect against local errors by storing logical information non-locally. This poses a challenge: how to design efficient logical gates on the non-local ``hidden'' logical information, and how to implement these gates using the local physical operations. We develop a general description of planar Pauli stabilizer codes and protocols for logical operations in terms of point-like particles called Majorana fermions. Information is stored in the pairwise fermion parities of spatially separated Majorana fermions. The description in terms of Majorana fermions captures not only large distance asymptotics, but also all scales down to the lattice constants. We exploit this locality to densely pack logical information in spacetime. The simplest application is to a static case: dense memory. More importantly, we implement fault-tolerant Majorana motion and leverage this primitive to design braiding-based logical gates. This approach reduces space overhead of logical operations resulting in an improved logical error rate given fixed number of physical qubits. We illustrate a practical use of our approach by designing and benchmarking of 2-qubit Clifford gates. We find numerically that our protocol outperforms lattice surgery in this setting for near-term error rates and realistic device constraints. More generally, introduction of compact motion of Majorana fermions as an efficient computational primitive opens a promising new route for the design of low overhead error correction protocols.

quant-pharXiv:2606.03916•Jun 3, 2026•1 citation

Scalable Pauli propagation through $\mathbb{F}_2$-linear partitioning

Alev Orfi, Andrew Kille, J. Clayton Peacock +2 more

Pauli propagation simulates quantum circuits and many-body dynamics by evolving observables in the Heisenberg picture as sparse sums of Pauli strings. As Pauli-string operations reduce to bit manipulations, its performance is limited by memory bandwidth and capacity rather than computational throughput. Pooling the memory of many cores and nodes is hindered by the deduplication step after every gate, which can require global synchronization. We avoid this bottleneck by partitioning the strings with an $\mathbb{F}_2$-linear hash function, which guarantees that a $k$-qubit channel couples each partition to at most $4^k$ partitions fixed by the gate, decomposing gate application into independent tasks with bounded communication. Benchmarks of our open-source implementation demonstrate efficient parallel scaling within and across compute nodes, enabling simulations with over $10^{11}$ Pauli strings and extending the accessible timescales of quantum many-body dynamics.

arXiv:2611.17262•Nov 12, 2026•0 citations

PADO-Pauli: A GPU-Accelerated Implementation of Pauli Propagation

Hyunwoo Kim, Youngseok Lee

Variational quantum algorithms utilize parameterized circuits many times during training, at new parameter values, over batches of data, and with gradients. Pauli propagation approximates the expectation values of such circuits classically by evolving the observable in the Heisenberg picture as a truncated sum of Pauli strings. We present PADO-Pauli, a GPU engine for Pauli propagation that compiles a circuit and its observables once into sparse matrices in which each rotation angle contributes only a cosine and a sine factor, so every later evaluation reuses the compiled program. It evaluates batches of parameters and data inputs embedded as rotation angles. By default its gradients come from a vector-Jacobian product registered with PyTorch's automatic differentiation, so they flow through the angles to any classical layer that produces them. PADO-Pauli also provides truncation by Pauli weight and coefficient size, and noise channels. Zero-filtering removes terms that do not contribute to an expectation value in the all-zero reference state and makes the batched forward pass about 1.5 times faster. Compared to cuPauliProp on an NVIDIA A100, PADO-Pauli evaluates up to 10 times faster on 4 to 12 qubits and uses up to 3.1 times less memory on 16 qubits. We check its accuracy against exact statevector simulation up to 28 qubits. These features make PADO-Pauli a practical toolkit for training variational quantum algorithms, including quantum machine learning models.

quant-pharXiv:2610.17755•Oct 14, 2026•0 citations

Thermal State Simulation with Pauli and Majorana Propagation

Manuel S. Rudolph, Armando Angrisani, Andrew Wright +3 more

We introduce a propagation-based approach to thermal state simulation by adapting Pauli and Majorana propagation to imaginary-time evolution in the Schrödinger picture. Our key observation is that high-temperature states can be sparse in the Pauli or Majorana bases, approaching the identity at infinite temperature. By formulating imaginary-time evolution directly in these operator bases and evolving from the maximally mixed state, we access a continuum of temperatures where the state remains efficiently representable. We provide analytic guarantees for small-coefficient truncation and Pauli-weight (Majorana-length) truncation strategies by quantifying the error growth and the impact of backflow. Large-scale numerics on the 1D J1-J2 model (energies) and the triangular-lattice Hubbard model (static correlations) validate efficiency at high temperatures.

quant-pharXiv:2602.04878•Feb 5, 2026•11 citations

Backpropagating Pauli Propagation

Sheng-Hsuan Lin, Etienne Granet, Kevin Hémery +1 more

We develop a backpropagation algorithm for evaluating parameter gradients in quantum circuits using Pauli propagation simulation. The method has computational complexity comparable to that of standard sparse Pauli simulation techniques, while producing gradients whose accuracy is of the same order as the corresponding observable expectation values. By exploiting the reversibility of quantum circuits, the algorithm reduces the memory cost by a factor of $\mathcal{O}(n_\text{param})$ compared with conventional reverse-mode automatic differentiation, where $n_\text{param}$ denotes the number of parameters in the circuit. Compared with finite difference methods, the algorithm is $\mathcal{O}(n_\text{param})$ more efficient in function evaluations. These features enable efficient and accurate classical optimization of quantum circuits for applications such as state preparation and time-evolution compression, while also allowing operator-complexity measures such as the operator stabilizer Rényi entropy to be monitored and regularized during optimization. We demonstrate the method by optimizing low-energy state-preparation circuits for transverse-field Ising models in one, two, and three dimensions and for the three-dimensional Heisenberg model, and by compressing two-dimensional time-evolution circuits.

quant-pharXiv:2607.15184•Jul 17, 2026•5 citations

Pauli propagation in adaptive local frames

Jonnathan Pineda-Jiménez, Mario Collura

The cost of Pauli propagation depends on the local basis in which the evolving operator is expanded. We show that its Pauli complexity splits into an occupation part, invariant under local rotations and bounded from below by the operator mass and length distributions, and a flavour part that a suitable basis can remove. We introduce frame-adaptive Pauli propagation (FAPP), which rotates the basis of every qubit, gate by gate, to the principal axes of the operator's local polarisation, exactly and within the memory structure of Pauli propagation. This simple rule achieves most of what the best local frame can, and the polarisation predicts how much any local frame can gain. In the Ising chain in transverse and longitudinal fields, FAPP lowers the truncation error at fixed memory by up to an order of magnitude and the memory by a size-independent factor of three; on the infinite two-dimensional lattice it needs up to seven times fewer strings for a given certified accuracy, and in Clifford circuits doped with T gates two to eight times fewer.

arXiv:2611.11647•Nov 8, 2026•0 citations
We introduce monoprop, an open-source, massively parallel operator-propagation framework for fermion and qubit bases. For NNN qubits or modes, existing codes represent each of the KKK tracked operator terms (Pauli strings or products of Majorana operators) as a 2N2N2N-bit string, testing each for anticommutation with the gate at O(KN)O(KN)O(KN) cost per gate. Here, we introduce the anticommutation index which rapidly looks up the terms anticommuting with a gate. A local gate changes only the terms that touch its sites, and when terms are truncated to act on few sites, only a fraction ∼1/N\sim1/N∼1/N touch any given qubit or mode, and we use this to prove the time per gate scales as O(K/N)O(K/N)O(K/N). This counterintuitive result tells us that for a fixed number of terms, increasing the number of sites can make things faster. We demonstrate this numerically, and show monoprop scales almost ideally to 8192 cores, tracking 9.5×10109.5\times10^{10}9.5×1010 terms. Beyond propagation, we present memory-efficient surrogate graphs, which record one propagation and replay it at new angles, for fast energy re-estimation and parameter gradients, and an efficient method for finding energy-minimising gates and optimal angles for simulating adaptive quantum-chemistry circuits.
Operator propagation approximates circuit expectation values by evolving sparse Pauli or Majorana expansions. This paper addresses the cost of finding and updating terms that anticommute with each gate, introducing monoprop, an open-source C++/Python framework with MPI parallelisation.
Its central data structure is an anticommutation index: lists of tracked terms occupying each operator position. Taking the symmetric difference of the lists selected by a gate identifies anticommuting terms without scanning the entire expansion. For KKK terms of bounded degree and local Pauli or even-Majorana gates, the proved per-gate cost is O(K/N)O(K/N)O(K/N) when position occupancies remain balanced, and O(K)O(K)O(K) in the worst case, versus the paper’s O(KN)O(KN)O(KN) dense-bitstring baseline. Sparse term storage requires O(d)O(d)O(d) rather than O(N)O(N)O(N) memory per term.
Single-core kicked-Ising and Hubbard benchmarks exhibit approximately inverse-system-size cost per tracked term, with reported speedups of 242424–149×149\times149× at selected sizes. Distributed Hubbard benchmarks track 9.47×10109.47\times10^{10}9.47×1010 terms on 8192 cores, retaining 94% weak-scaling efficiency for the largest workload. Recorded surrogate graphs evaluate energies and all-parameter gradients in roughly 0.1 and 0.2 times propagation time. A separate Fock-reference gate-selection algorithm reduces exhaustive scoring from O(Nd+g)O(N^{d+g})O(Nd+g) to expected O(N(d+g)/2)O(N^{(d+g)/2})O(N(d+g)/2), supported by enumeration proofs and timing fits.
The inverse-size bound requires bounded support and balanced occupancies, which are not guaranteed dynamically. The study benchmarks performance rather than physical accuracy or optimisation outcomes. Diagonal-term cutoff exemptions qualify degree-based bounds; gate-selection functionality is not yet included in the public release.
Quantum error correction protocols protect against local errors by storing logical information non-locally. This poses a challenge: how to design efficient logical gates on the non-local ``hidden'' logical information, and how to implement these gates using the local physical operations. We develop a general description of planar Pauli stabilizer codes and protocols for logical operations in terms of point-like particles called Majorana fermions. Information is stored in the pairwise fermion parities of spatially separated Majorana fermions. The description in terms of Majorana fermions captures not only large distance asymptotics, but also all scales down to the lattice constants. We exploit this locality to densely pack logical information in spacetime. The simplest application is to a static case: dense memory. More importantly, we implement fault-tolerant Majorana motion and leverage this primitive to design braiding-based logical gates. This approach reduces space overhead of logical operations resulting in an improved logical error rate given fixed number of physical qubits. We illustrate a practical use of our approach by designing and benchmarking of 2-qubit Clifford gates. We find numerically that our protocol outperforms lattice surgery in this setting for near-term error rates and realistic device constraints. More generally, introduction of compact motion of Majorana fermions as an efficient computational primitive opens a promising new route for the design of low overhead error correction protocols.
Scalable Pauli propagation through F2\mathbb{F}_2F2​-linear partitioning
Pauli propagation simulates quantum circuits and many-body dynamics by evolving observables in the Heisenberg picture as sparse sums of Pauli strings. As Pauli-string operations reduce to bit manipulations, its performance is limited by memory bandwidth and capacity rather than computational throughput. Pooling the memory of many cores and nodes is hindered by the deduplication step after every gate, which can require global synchronization. We avoid this bottleneck by partitioning the strings with an F2\mathbb{F}_2F2​-linear hash function, which guarantees that a kkk-qubit channel couples each partition to at most 4k4^k4k partitions fixed by the gate, decomposing gate application into independent tasks with bounded communication. Benchmarks of our open-source implementation demonstrate efficient parallel scaling within and across compute nodes, enabling simulations with over 101110^{11}1011 Pauli strings and extending the accessible timescales of quantum many-body dynamics.
Variational quantum algorithms utilize parameterized circuits many times during training, at new parameter values, over batches of data, and with gradients. Pauli propagation approximates the expectation values of such circuits classically by evolving the observable in the Heisenberg picture as a truncated sum of Pauli strings. We present PADO-Pauli, a GPU engine for Pauli propagation that compiles a circuit and its observables once into sparse matrices in which each rotation angle contributes only a cosine and a sine factor, so every later evaluation reuses the compiled program. It evaluates batches of parameters and data inputs embedded as rotation angles. By default its gradients come from a vector-Jacobian product registered with PyTorch's automatic differentiation, so they flow through the angles to any classical layer that produces them. PADO-Pauli also provides truncation by Pauli weight and coefficient size, and noise channels. Zero-filtering removes terms that do not contribute to an expectation value in the all-zero reference state and makes the batched forward pass about 1.5 times faster. Compared to cuPauliProp on an NVIDIA A100, PADO-Pauli evaluates up to 10 times faster on 4 to 12 qubits and uses up to 3.1 times less memory on 16 qubits. We check its accuracy against exact statevector simulation up to 28 qubits. These features make PADO-Pauli a practical toolkit for training variational quantum algorithms, including quantum machine learning models.
We introduce a propagation-based approach to thermal state simulation by adapting Pauli and Majorana propagation to imaginary-time evolution in the Schrödinger picture. Our key observation is that high-temperature states can be sparse in the Pauli or Majorana bases, approaching the identity at infinite temperature. By formulating imaginary-time evolution directly in these operator bases and evolving from the maximally mixed state, we access a continuum of temperatures where the state remains efficiently representable. We provide analytic guarantees for small-coefficient truncation and Pauli-weight (Majorana-length) truncation strategies by quantifying the error growth and the impact of backflow. Large-scale numerics on the 1D J1-J2 model (energies) and the triangular-lattice Hubbard model (static correlations) validate efficiency at high temperatures.
We develop a backpropagation algorithm for evaluating parameter gradients in quantum circuits using Pauli propagation simulation. The method has computational complexity comparable to that of standard sparse Pauli simulation techniques, while producing gradients whose accuracy is of the same order as the corresponding observable expectation values. By exploiting the reversibility of quantum circuits, the algorithm reduces the memory cost by a factor of O(nparam)\mathcal{O}(n_\text{param})O(nparam​) compared with conventional reverse-mode automatic differentiation, where nparamn_\text{param}nparam​ denotes the number of parameters in the circuit. Compared with finite difference methods, the algorithm is O(nparam)\mathcal{O}(n_\text{param})O(nparam​) more efficient in function evaluations. These features enable efficient and accurate classical optimization of quantum circuits for applications such as state preparation and time-evolution compression, while also allowing operator-complexity measures such as the operator stabilizer Rényi entropy to be monitored and regularized during optimization. We demonstrate the method by optimizing low-energy state-preparation circuits for transverse-field Ising models in one, two, and three dimensions and for the three-dimensional Heisenberg model, and by compressing two-dimensional time-evolution circuits.
The cost of Pauli propagation depends on the local basis in which the evolving operator is expanded. We show that its Pauli complexity splits into an occupation part, invariant under local rotations and bounded from below by the operator mass and length distributions, and a flavour part that a suitable basis can remove. We introduce frame-adaptive Pauli propagation (FAPP), which rotates the basis of every qubit, gate by gate, to the principal axes of the operator's local polarisation, exactly and within the memory structure of Pauli propagation. This simple rule achieves most of what the best local frame can, and the polarisation predicts how much any local frame can gain. In the Ising chain in transverse and longitudinal fields, FAPP lowers the truncation error at fixed memory by up to an order of magnitude and the memory by a size-independent factor of three; on the infinite two-dimensional lattice it needs up to seven times fewer strings for a given certified accuracy, and in Clifford circuits doped with T gates two to eight times fewer.