Counting anticommuting Pauli pairs in linear time

Hyunho Cha, Jungwoo Lee · 2026

Read Counting anticommuting Pauli pairs in linear time by Hyunho Cha, Jungwoo Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11016.txt.

Introduction

Hyunho Cha and Jungwoo Lee give a linear-time algorithm for counting anticommuting Pauli pairs, a routine subroutine in quantum computing workflows. Long lists of Pauli strings must be checked for pairwise commutation or counted for anticommuting pairs, and the standard binary symplectic route costs quadratic time.

In the bounded-locality regime, each string's weight stays bounded by a constant. Their algorithm tracks counts of all labeled subpatterns of inserted strings and answers each new query through a subset zeta identity. The result runs in linear time and suits large Pauli collections. Quantum software builders get a fast exact counter for a ubiquitous bookkeeping task.

Catalog record

CREATORHyunho Cha, Jungwoo Lee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20374
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11016

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting anticommuting Pauli pairs in linear time Hyunho Cha, Jungwoo Lee Abstract Many quantum computing workflows manipulate long lists of Pauli strings. A basic classical subroutine involves taking m m Pauli strings on n 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 ) O(m^{2}) time. Here, we provide an O ⁡ ( m ) 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. 1 Introduction Quantum states are vectors, and quantum gates are matrices. A great deal of quantum algorithm design is nevertheless written in a much smaller symbolic language consisting of products of the four one-qubit matrices I, X=(\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}), Y=(\begin{smallmatrix}0&-i\\ i&0\end{smallmatrix}), and Z=(\begin{smallmatrix}1&0\\ 0&-1\end{smallmatrix}). A tensor product such as X\otimes I\otimes Z\otimes Y is called a Pauli string. These strings form an operator basis, so Hamiltonians, observables, stabilizer checks, Pauli rotations, and many intermediate objects in quantum software can be stored as weighted sums of Pauli strings [ 1 , 5 ] . Consider the task of local Pauli commutation certification and anticommutation counting, which is a common classical subroutine within quantum algorithms and software. Given an input of m sparse n -qubit Pauli strings P^{(1)},\dots,P^{(m)} where each string acts nontrivially on at most k qubits, the objective is to produce one of several outputs based on the specific requirements of the workflow. Specifically, the routine should be able to calculate the exact number of unordered anticommuting pairs \{i,j\} , provide a certificate that all strings commute pairwise, or, in cases where they do not all commute, identify a witness pair (i,j) such that P^{(i)}P^{(j)}=-P^{(j)}P^{(i)} . This primitive is important because simultaneous measurement and simultaneous diagonalization require commutation. Variational quantum eigensolver measurement reduction partitions Pauli terms into commuting families, frequently through graph coloring or clique cover formulations [ 2 , 3 , 8 , 9 ] . Recent partitioning methods avoid some graph costs for dense operator bases but explicitly target dense settings rather than arbitrary sparse local Hamiltonians [ 7 ] . Pauli-based computation uses sequences of pairwise commuting Pauli measurements [ 6 ] . Modern Pauli arithmetic libraries optimize multiplication and commutator testing by bit operations, but the batching problem still appears naturally whenever many pairs must be screened or many candidate commuting sets must be verified [ 4 ] . Listing all anticommuting edges can take \Omega(m^{2}) time when the output graph is dense. Exact counting and certification, however, have only a logarithmic-size or constant-size output and are exactly what many verification steps need. In this work, we improve the pairwise graph baseline from quadratic to linear in m when k is fixed. 2 Preliminaries 2.1 Qubits, tensor products, and gates A single qubit is a unit vector in the two-dimensional complex vector space \mathbb{C}^{2} . The computational basis is |0\rangle=\begin{pmatrix}1\\ 0\end{pmatrix},\qquad|1\rangle=\begin{pmatrix}0\\ 1\end{pmatrix}. An n -qubit pure state is a unit vector in the tensor product space (\mathbb{C}^{2})^{\otimes n}=\underbrace{\mathbb{C}^{2}\otimes\cdots\otimes\mathbb{C}^{2}}_{\times n}, which has dimension 2^{n} . A quantum gate on n qubits is a 2^{n}\times 2^{n} unitary matrix, meaning a complex matrix U satisfying U^{\dagger}U=UU^{\dagger}=I_{2^{n}} . When matrices A and B act on two different qubit registers, their combined action is described by the tensor product A\otimes B . For matrices A,B,C,D of compatible sizes, (A\otimes B)(C\otimes D)=(AC)\otimes(BD). The same identity extends to any number of tensor factors. 2.2 Pauli letters and Pauli strings The one-qubit Pauli letters are I, X=(\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}), Y=(\begin{smallmatrix}0&-i\\ i&0\end{smallmatrix}), and Z=(\begin{smallmatrix}1&0\\ 0&-1\end{smallmatrix}). They satisfy X^{2}=Y^{2}=Z^{2}=I, and any two distinct non-identity Pauli matrices anticommute: XY=-YX,\qquad YZ=-ZY,\qquad ZX=-XZ. The identity commutes with all three. A phase-free n -qubit Pauli string is a word P=(P_{1},\ldots,P_{n})\in\{I,X,Y,Z\}^{n}, identified with the matrix P_{1}\otimes P_{2}\otimes\cdots\otimes P_{n}. The support and weight of P are \operatorname{supp}(P)=\{j\in\{1,\ldots,n\}:P_{j}\neq I\},\qquad\operatorname{wt}(P)=|\operatorname{supp}(P)|. The string is k -local if \operatorname{wt}(P)\leq k . Global phases \pm 1,\pm i are ignored because they do not affect whether two strings commute. Sparse input means that P is stored as the list of pairs (j,P_{j}) for j\in\operatorname{supp}(P) , not as all n letters. 2.3 Commutation and anticommutation Two square matrices A and B commute if AB=BA and anticommute if AB=-BA . For Pauli strings, exactly one of these two possibilities holds. For two Pauli strings P,Q , define their conflict set \operatorname{conf}(P,Q)=\{j:P_{j}\neq I,\ Q_{j}\neq I,\ P_{j}\neq Q_{j}\}. This is the set of qubits where both strings act nontrivially and the two one-qubit Pauli letters are different. Lemma 1 . For any two phase-free n -qubit Pauli strings P,Q\in\{I,X,Y,Z\}^{n} , PQ=(-1)^{|\operatorname{conf}(P,Q)|}QP. Consequently, P and Q commute if |\operatorname{conf}(P,Q)| is even, and anticommute if |\operatorname{conf}(P,Q)| is odd. 2.4 The binary symplectic baseline A standard representation maps each Pauli string to two binary vectors x,z\in\mathbb{F}_{2}^{n} by I\leftrightarrow(0,0),\qquad X\leftrightarrow(1,0),\qquad Z\leftrightarrow(0,1),\qquad Y\leftrightarrow(1,1). If P\leftrightarrow(x,z) and Q\leftrightarrow(x^{\prime},z^{\prime}) , then P\text{ anticommutes with }Q\quad\Longleftrightarrow\quad x\cdot z^{\prime}+z\cdot x^{\prime}=1\pmod{2}. This is the binary symplectic form. It gives a very fast single-pair test, especially with word-level bit operations [ 1 , 4 ] . For a list of m strings, however, applying this test to every unordered pair costs \Theta(m^{2}) pair checks. If the strings are sparse and k -local, each pair can be checked in O(k) time by merging or hashing their supports, for total O(m^{2}k) . 3 Problem formulation Fix positive integers n,m,k . The input is a sequence P^{(1)},\ldots,P^{(m)}\in\{I,X,Y,Z\}^{n} with \operatorname{wt}\!\big(P^{(i)}\big)\leq k for every i , given in sparse form. The anticommutation count is A\big(P^{(1)},\ldots,P^{(m)}\big)=\left|\left\{\{i,j\}:1\leq i<j\leq m,\ \left|\operatorname{conf}\!\big(P^{(i)},P^{(j)}\big)\right|\equiv 1\pmod{2}\right\}\right|. The certification problem is to decide whether A\big(P^{(1)},\ldots,P^{(m)}\big)=0 . The witness version must return a pair (i,j) with i<j and P^{(i)}P^{(j)}=-P^{(j)}P^{(i)} when such a pair exists. If the requested output is the full anticommutation graph, then the output itself can have \Theta(m^{2}) edges. Our subquadratic result is for counting, certification, and witness finding, not for explicitly listing all edges. 4 The locality-zeta data structure 4.1 Patterns A labeled Pauli pattern is a pair (A,a) , where A\subseteq\{1,\ldots,n\} is a finite set of qubit positions and a:A\to\{X,Y,Z\} assigns a non-identity Pauli letter to every position in A . The empty pattern is (\varnothing,\varnothing) . A Pauli string Q contains the pattern (A,a) , written Q\succeq(A,a), if A\subseteq\operatorname{supp}(Q) and Q_{j}=a(j) for every j\in A . For a multiset G of previously inserted Pauli strings, define the table of pattern counts D_{G}(A,a)=|\{Q\in G:Q\succeq(A,a)\}|. The table stores counts for patterns that occur inside the inserted strings. If a key has never been inserted, its count is interpreted as zero. In particular, D_{G}(\varnothing,\varnothing)=|G|. 4.2 Insertion To insert a w -local Pauli string Q , enumerate every subset A\subseteq\operatorname{supp}(Q) and increment D_{G}(A,Q|_{A}) by one, where Q|_{A} is the letter assignment on A . 4.3 Query Let P be a query string with support S=\operatorname{supp}(P) . For a subset A\subseteq S , define \mathcal{L}_{P}(A)=\{a:A\to\{X,Y,Z\}:a(j)\neq P_{j}\text{ for every }j\in A\}. Thus \mathcal{L}_{P}(A) contains the assignments that force a conflict with P on every position of A . Define F_{G}(P,A)=\sum_{a\in\mathcal{L}_{P}(A)}D_{G}(A,a).

Read the complete text