{"id":"arxiv/2605.11016","url":"https://arxiv.org/abs/2605.11016","tags":["quant-ph"],"score":0,"title":"Counting anticommuting Pauli pairs in linear time","domain":"quant-ph","source":"arxiv","authors":["Hyunho Cha","Jungwoo Lee"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-10","reactions":{}}