arxiv: 2605.11016 · v1 · submitted 2026-05-10 · 🪐 quant-ph

Counting anticommuting Pauli pairs in linear time

Hyunho Cha , Jungwoo Lee This is my paper

Pith reviewed 2026-05-13 06:56 UTC · model grok-4.3

classification 🪐 quant-ph

keywords Pauli stringsanticommuting pairslinear time algorithmquantum computingsubset zeta identitybounded weight

0 comments

The pith

A linear-time algorithm counts anticommuting pairs among constant-weight Pauli strings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that m Pauli strings of bounded weight can be processed to count their anticommuting unordered pairs in total O(m) time. It keeps running counts of every labeled subpattern from strings seen so far and resolves each new string against the collection by evaluating a subset zeta identity. This replaces the standard quadratic-time pairwise symplectic check that is normally used in quantum workflows. A reader would care because many quantum computing tasks manipulate large lists of low-weight Paulis and would gain from avoiding quadratic scaling.

Core claim

We provide an O(m) algorithm for the bounded locality regime. It maintains counts of all labeled subpatterns of previously inserted strings and answers each new string query by a subset zeta identity.

What carries the argument

Counts of labeled subpatterns of Pauli strings, queried via a subset zeta identity to determine anticommuting pairs.

If this is right

Large collections of low-weight Pauli strings can be checked for pairwise commutation in linear time.
Counterexamples to commutation can be reported without examining every pair explicitly.
Quantum simulation and compilation routines that rely on Pauli-string lists become scalable for constant-locality operators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same subpattern counting approach could be adapted to track other algebraic relations among Pauli operators.
Similar techniques may accelerate checks in related algebraic structures such as Clifford groups or stabilizer codes.
Empirical timing tests on realistic quantum-circuit Pauli lists would quantify the practical crossover point versus quadratic methods.

Load-bearing premise

Each Pauli string has weight bounded by a fixed constant.

What would settle it

A collection of constant-weight strings whose anticommuting-pair count from the new algorithm differs from the count obtained by exhaustive quadratic enumeration.

read the original abstract

Many quantum computing workflows manipulate long lists of Pauli strings. A basic classical subroutine involves taking $m$ Pauli strings on $n$ qubits, each of weight bounded by a constant, to determine if they are pairwise commuting, identify any counterexamples, or calculate the exact number of anticommuting unordered pairs. The standard general-purpose route represents Pauli strings in binary symplectic form and checks pairs in $O(m^2)$ time. Here, we provide an $O(m)$ algorithm for the bounded locality regime. It maintains counts of all labeled subpatterns of previously inserted strings and answers each new string query by a subset zeta identity. Our algorithm is particularly useful for processing large collections of Pauli strings within the bounded locality regime.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Linear-time counting of anticommuting Pauli pairs via subpattern counts and subset zeta works for constant weight and removes the quadratic bottleneck.

read the letter

The paper gives a linear-time algorithm for counting anticommuting pairs among bounded-weight Pauli strings. If the details hold, it removes a real bottleneck in quantum computing workflows that deal with large lists of these operators. They maintain counts of labeled subpatterns from the strings inserted so far. Each new string is handled by summing over the relevant subsets using a zeta identity, which lets them compute the anticommuting count without checking every previous string. Since the weight is bounded by a constant, the work per string stays constant, leading to overall linear time in m. This is a clear improvement over the standard O(m squared) pairwise method. The approach is combinatorial and avoids any dependence on the number of qubits n in the per-string cost, which is good. The logic checks out at a high level because the subpattern space is finite for fixed weight. No hidden quadratic terms or parameter fitting appear in the construction. A minor soft spot is the lack of a worked example or pseudocode in the provided text, which makes it a bit harder to verify the exact implementation of the counts. But the central claim does not seem to have internal contradictions. This paper is for researchers and engineers working on classical post-processing for variational algorithms or stabilizer simulations. Anyone who regularly handles thousands of low-weight Pauli strings would benefit from the speedup. It deserves serious peer review because the result is specific, the technique is novel relative to the cited baseline, and the potential impact is practical. I would recommend sending it to referees.

Referee Report

1 major / 1 minor

Summary. The paper claims an O(m) algorithm for counting anticommuting unordered pairs (or identifying counterexamples) among m Pauli strings on n qubits where each string has weight bounded by a fixed constant. The approach maintains a data structure of counts for all labeled subpatterns of inserted strings and resolves each new query via a subset zeta identity, replacing the standard O(m²) pairwise symplectic-form checks.

Significance. If the claimed linear-time bound holds, the result is significant for quantum workflows that manipulate large collections of low-weight Pauli operators (e.g., stabilizer codes, simulation, or compilation). The construction is parameter-free, uses only direct combinatorial counting, and incurs O(1) work per string once the weight bound is fixed, which is a clear improvement over quadratic methods in the bounded-locality regime.

major comments (1)

[Abstract and main algorithm description] Abstract and main algorithm description: the O(m) claim rests on the assertion that each insertion and query touches only O(3^w) entries for constant w. The manuscript supplies neither the explicit derivation of the subset-zeta summation that realizes this bound nor the precise hash-map representation of labeled subpatterns, so the central complexity statement cannot be verified from the given text.

minor comments (1)

The manuscript would benefit from a short pseudocode listing for the insertion and query routines and from one fully worked numerical example on a small set of strings.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our result and for the constructive comment on the presentation of the complexity analysis. We address the major comment point by point below.

read point-by-point responses

Referee: Abstract and main algorithm description: the O(m) claim rests on the assertion that each insertion and query touches only O(3^w) entries for constant w. The manuscript supplies neither the explicit derivation of the subset-zeta summation that realizes this bound nor the precise hash-map representation of labeled subpatterns, so the central complexity statement cannot be verified from the given text.

Authors: We agree that the main text did not contain a self-contained derivation of the O(3^w) per-operation bound or an explicit description of the hash-map keys. The algorithm description states that we maintain counts of labeled subpatterns and apply a subset zeta identity, but it omits the intermediate counting argument. In the revised manuscript we will add a short subsection that (i) enumerates the at most 3^w labeled subpatterns of a weight-w string (each of the w non-identity positions can be labeled by one of three Pauli matrices, with the support recorded), (ii) shows that the fast subset-sum zeta transform over the power set of these labels can be performed in O(3^w) arithmetic operations, and (iii) specifies that the data structure is a hash map whose keys are sorted tuples of (qubit index, Pauli label) pairs. With these additions the linear-time claim becomes directly verifiable from the text. We thank the referee for identifying this gap. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a direct combinatorial algorithm that maintains counts of labeled subpatterns of inserted Pauli strings and answers queries via subset zeta inversion. For constant weight w the per-string work is bounded by O(3^w) operations independent of m and n, yielding the stated O(m) total time by explicit construction. No equation reduces the running-time claim to a fitted parameter, no self-citation is load-bearing for the central result, and the algorithm is self-contained against external benchmarks without renaming known results or smuggling ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The algorithm rests on the standard subset zeta transform identity for counting and on the assumption that weight is bounded by a fixed constant so that the number of labeled subpatterns remains O(1) per string.

axioms (1)

standard math Subset zeta identity correctly aggregates the anticommuting count from subpattern tallies
Invoked to answer each insertion query in constant time once subpattern counts are maintained

pith-pipeline@v0.9.0 · 5407 in / 1012 out tokens · 49564 ms · 2026-05-13T06:56:51.024798+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

maintains counts of all labeled subpatterns ... answers each new string query by a subset zeta identity
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

ZG(P) = sum_{A subset supp(P)} (-2)^|A| FG(P,A)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · 1 internal anchor

[1]

Improved simulation of stabilizer circuits.Physical Review A, 70(5):052328, 2004

Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits.Physical Review A, 70(5):052328, 2004

work page 2004
[2]

Cambridge University Press, 2010

Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum information. Cambridge University Press, 2010

work page 2010
[3]

Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T Chong.O(N 3)Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians.IEEE Transactions on Quantum Engineering, 1:1–24, 2020

work page 2020
[4]

Efficient evaluation of quantum observables using entangled measurements.npj Quantum Information, 6(1):56, 2020

Ikko Hamamura and Takashi Imamichi. Efficient evaluation of quantum observables using entangled measurements.npj Quantum Information, 6(1):56, 2020

work page 2020
[5]

Measurement optimization in the variational quantum eigensolver using a minimum clique cover.The Journal of Chemical Physics, 152(12), 2020

Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F Izmaylov. Measurement optimization in the variational quantum eigensolver using a minimum clique cover.The Journal of Chemical Physics, 152(12), 2020

work page 2020
[6]

Measuring all compatible operators in one series of single-qubit measurements using unitary transformations.Journal of Chemical Theory and Computation, 16(4):2400–2409, 2020

Tzu-Ching Yen, Vladyslav Verteletskyi, and Artur F Izmaylov. Measuring all compatible operators in one series of single-qubit measurements using unitary transformations.Journal of Chemical Theory and Computation, 16(4):2400–2409, 2020

work page 2020
[7]

Fast partitioning of Pauli strings into commuting families for optimal expectation value measurements of dense operators.Physical Review A, 110(2):022606, 2024

Ben Reggio, Nouman Butt, Andrew Lytle, and Patrick Draper. Fast partitioning of Pauli strings into commuting families for optimal expectation value measurements of dense operators.Physical Review A, 110(2):022606, 2024

work page 2024
[8]

Quantum circuit compilation and hybrid computation using Pauli-based computation.Quantum, 7:1126, 2023

Filipa CR Peres and Ernesto F Galvão. Quantum circuit compilation and hybrid computation using Pauli-based computation.Quantum, 7:1126, 2023

work page 2023
[9]

PauliEngine: High-Performant Symbolic Arithmetic for Quantum Operations

Leon Müller, Adelina Bärligea, Alexander Knapp, and Jakob S Kottmann. PauliEngine: High- Performant Symbolic Arithmetic for Quantum Operations.arXiv preprint arXiv:2601.02233, 2026. 9

work page internal anchor Pith review Pith/arXiv arXiv 2026