Counting anticommuting Pauli pairs in linear time

• URL: http://arxiv.org/abs/2605.11016v1
• Date: Sun, 10 May 2026 14:41:11 GMT
• Title: Counting anticommuting Pauli pairs in linear time
• Abstract summary: We provide an $O(m)$ algorithm for the bounded locality regime.<n>Our algorithm is particularly useful for processing large collections of Pauli strings within the bounded locality regime.
• Score: 5.706918315850497
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• An efficient Pauli decomposition algorithm for structured matrices [0.12744523252873352]
  We consider a promise version of a Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = mathsfpoly(n)$ Pauli strings.<n>We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability of at least $1 - $.
  arXiv  Detail & Related papers  (2026-06-30T16:57:07Z)
• Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance [6.852394426719304]
  This class generalizes well-studied families, including sparse unitaries, quantum $k$-juntas, $2k$-Pauli dimensional channels, and compositions of depth $O(loglog n)$ circuits.
  arXiv  Detail & Related papers  (2026-03-31T20:13:10Z)
• Quantum many-body simulations with PauliStrings.jl [0.0]
  We present the Julia package PauliStrings for quantum many-body simulations.<n>It performs fast operations on the Pauli group by encoding Pauli strings in binary.<n>We show that this representation allows for easy encoding of any geometry.
  arXiv  Detail & Related papers  (2024-10-12T21:18:47Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Efficiently manipulating Pauli strings with PauliArray [0.0]
  Pauli matrices and Pauli strings are widely used in quantum computing. It is important to have a well-rounded, versatile and efficient tool to handle a large number of Pauli strings and operators expressed in this basis. This library introduces data structures to represent arrays of Pauli strings and operators as well as various methods to modify and combine them.
  arXiv  Detail & Related papers  (2024-05-29T17:18:08Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Fast Partitioning of Pauli Strings into Commuting Families for Optimal Expectation Value Measurements of Dense Operators [0.0]
  Pauli strings appearing in the decomposition of an operator can be can be grouped into commuting families.<n>We detail an algorithm to completely partition the full set of Pauli strings acting on any number of qubits into the minimal number of sets of commuting families.
  arXiv  Detail & Related papers  (2023-05-19T17:39:33Z)
• The qudit Pauli group: non-commuting pairs, non-commuting sets, and structure theorems [0.7673339435080445]
  We study the structure of the qudit Pauli group for any, including composite, $d$ in several ways. For any specified set of commutation relations, we construct a set of qudit Paulis satisfying those relations. We also study the maximum size of sets of Paulis that mutually non-commute and sets that non-commute in pairs.
  arXiv  Detail & Related papers  (2023-02-15T22:06:40Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Coherent randomized benchmarking [68.8204255655161]
  We show that superpositions of different random sequences rather than independent samples are used. We show that this leads to a uniform and simple protocol with significant advantages with respect to gates that can be benchmarked.
  arXiv  Detail & Related papers  (2020-10-26T18:00:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.