Pauli Partitioning with Respect to Gate Sets

Andrew Jena; Michele Mosca; Scott Genin

arxiv: 1907.07859 · v1 · pith:55YYQHJHnew · submitted 2019-07-18 · 🪐 quant-ph · math.CO

Pauli Partitioning with Respect to Gate Sets

Andrew Jena , Scott Genin , Michele Mosca This is my paper

Pith reviewed 2026-05-24 20:08 UTC · model grok-4.3

classification 🪐 quant-ph math.CO

keywords Pauli operatorssimultaneous measurementClifford operatorsgraph coloringvariational quantum eigensolverquantum measurementrandom graphs

0 comments

The pith

Allowing arbitrary Clifford operators reduces the number of Pauli measurement partitions linearly with operator length

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

This paper studies how to group Pauli operators so that their expectation values can be obtained from fewer simultaneous measurements on a prepared quantum state. It derives an upper bound on the typical number of groups by treating compatibility as a random-graph coloring problem. The central conjecture states that permitting arbitrary Clifford operators before measurement, rather than restricting to single-qubit gates, produces a reduction in the number of groups that scales linearly with the length of the Pauli strings. Numerical experiments on random subsets of Paulis are offered as supporting evidence. The authors note that such a reduction would directly lower the measurement overhead in variational quantum eigensolvers.

Core claim

By representing the problem of simultaneous measurability after Clifford conjugation as the chromatic number of an associated graph, the paper conjectures that the minimum number of measurement rounds for a collection of Pauli operators falls linearly with the operators' lengths when general Clifford gates are allowed, in contrast to the single-qubit case, and supplies numerical confirmation of this linear scaling for random Pauli subsets.

What carries the argument

The chromatic number of the graph whose vertices are the given Pauli operators and whose edges connect pairs that fail to commute after conjugation by a chosen Clifford operator

If this is right

The total number of circuit executions needed to estimate a Hamiltonian expectation value drops in proportion to operator length
Variational quantum eigensolver runs on near-term hardware become cheaper when general Clifford pre-rotations are used for measurement
Upper bounds derived from random-graph coloring supply a theoretical limit on how many partitions are required
The linear improvement applies at least to randomly chosen collections of Pauli strings

Where Pith is reading between the lines

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

If the linear scaling persists for the highly structured Pauli sets that arise from molecular Hamiltonians, the technique would give an immediate practical reduction in VQE shot counts
The same graph-coloring approach could be applied to measurement tasks outside VQE, such as estimating observables in quantum simulation or tomography
Explicit constructions of the required Clifford operators, rather than existence arguments, would turn the conjecture into a deployable algorithm

Load-bearing premise

The pattern of which Pauli operators commute after Clifford conjugation behaves like the edge set of a random graph whose chromatic number grows linearly with the number of vertices in the manner required by the conjecture

What would settle it

Computing the minimal number of partitions for the actual Pauli terms appearing in a small molecular Hamiltonian both with and without general Clifford gates and checking whether the observed reduction scales linearly with average string length

read the original abstract

Measuring the expectation value of Pauli operators on prepared quantum states is a fundamental task in a multitude of quantum algorithms. Simultaneously measuring sets of operators allows for fewer measurements and an overall speedup of the measurement process. We investigate the task of partitioning a random subset of Pauli operators into simultaneously-measurable parts. Using heuristics from coloring random graphs, we give an upper bound for the expected number of parts in our partition. We go on to conjecture that allowing arbitrary Clifford operators before measurement, rather than single-qubit operations, leads to a decrease in the number of parts which is linear with respect to the lengths of the operators. We give evidence to confirm this conjecture and comment on the importance of this result for a specific near-term application: speeding up the measurement process of the variational quantum eigensolver.

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

Random-graph bound on Pauli partitions is straightforward, but the linear Clifford conjecture rests on untested extrapolation from random instances to structured VQE Hamiltonians.

read the letter

The main points are an upper bound on the expected number of commuting partitions for random Pauli subsets, obtained by applying known random-graph coloring results, plus a conjecture that arbitrary Clifford pre-rotations produce a linear reduction in partition count relative to single-qubit rotations, backed by unspecified numerics on those random subsets. The bound itself is a direct and uncontroversial application of external graph theory. The conjecture is the element that has not appeared in the cited prior work on Pauli partitioning. Both pieces are tied explicitly to the measurement bottleneck in VQE, which gives the work a clear near-term motivation. The numerics are presented only as confirmation rather than a full empirical study, so the bound stands on firmer ground than the scaling claim. The soft spot is the modeling step that treats the post-Clifford commutation graph as behaving like a random-graph instance whose chromatic number scales linearly. VQE Hamiltonians generate sparse, local, low-weight Pauli sets whose graphs carry additional structure—bounded degree from locality and possible large cliques from overlapping supports—that can alter chromatic-number behavior. The abstract supplies no tests on actual molecular Hamiltonians and no analytic argument that the linear scaling survives conjugation on those structured sets. Without that check, the claimed practical payoff remains conditional. This is the sort of incremental algorithmic note that belongs in a quantum-computing venue focused on near-term methods. Readers already working on measurement grouping or VQE resource estimation would get value from the bound and the open conjecture. The paper is coherent on its own terms and deserves referee time so the conjecture can be stress-tested on realistic instances.

Referee Report

3 major / 2 minor

Summary. The paper studies partitioning random subsets of Pauli operators into commuting groups for simultaneous measurement. It derives an upper bound on the expected number of parts via random-graph coloring heuristics. The central claim is a conjecture that pre-applying arbitrary Clifford operators (rather than only single-qubit gates) yields a linear reduction in the number of parts with respect to operator length; numerical evidence on random subsets is supplied, together with remarks on relevance to VQE measurement overhead.

Significance. If the conjecture holds and the random-graph scaling persists for the sparse, local Pauli sets that appear in molecular Hamiltonians, the result would directly improve the measurement cost of VQE on near-term hardware. The random-graph approach supplies a clean analytic upper bound, which is a positive feature, but the absence of an analytic derivation of the linear scaling and the lack of tests on structured Hamiltonians limit the strength of the claimed near-term application.

major comments (3)

[Abstract] Abstract and conjecture statement: the claimed linear reduction in partition size under arbitrary Clifford conjugation is supported only by unspecified numerical evidence on random Pauli subsets; no analytic derivation from the paper's own quantities, no error bars, and no comparison against known lower bounds on chromatic number are provided.
[VQE discussion] VQE application paragraph: the extrapolation from random-graph chromatic-number scaling to VQE Hamiltonians is load-bearing for the stated motivation, yet the manuscript contains no numerical test on low-weight, local Pauli sets (which induce graphs with bounded degree and possible large cliques from shared supports) that would confirm the scaling survives the additional structure.
[Numerical results] Numerical evidence section: the modeling choice that post-Clifford commutation relations behave like a random-graph instance is presented without a quantitative check (e.g., degree distribution or clique number) against the actual commutation graphs arising from the paper's own random subsets, weakening the link between the heuristic bound and the conjecture.

minor comments (2)

[Introduction] Define 'length of the operators' explicitly at first use and state the precise ensemble of random Pauli subsets employed in the numerics.
[Results] Add a short table or plot comparing the observed partition sizes against the random-graph upper bound for at least two different operator lengths.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the careful review and constructive feedback. We address each major comment below, clarifying the numerical nature of our results and proposing targeted revisions to improve clarity and temper claims where appropriate.

read point-by-point responses

Referee: [Abstract] Abstract and conjecture statement: the claimed linear reduction in partition size under arbitrary Clifford conjugation is supported only by unspecified numerical evidence on random Pauli subsets; no analytic derivation from the paper's own quantities, no error bars, and no comparison against known lower bounds on chromatic number are provided.

Authors: The linear reduction is presented explicitly as a conjecture supported by numerical evidence on random subsets. We will revise the abstract to state this more clearly, add error bars to the reported numerical results, and include comparisons to known chromatic-number lower bounds where feasible. An analytic derivation from the paper's quantities is not available. revision: partial
Referee: [VQE discussion] VQE application paragraph: the extrapolation from random-graph chromatic-number scaling to VQE Hamiltonians is load-bearing for the stated motivation, yet the manuscript contains no numerical test on low-weight, local Pauli sets (which induce graphs with bounded degree and possible large cliques from shared supports) that would confirm the scaling survives the additional structure.

Authors: We agree that direct tests on structured, low-weight Pauli sets would be needed to confirm the scaling for molecular Hamiltonians. The manuscript derives its bound and conjecture for random subsets; we will revise the VQE paragraph to note this limitation and state that further validation on realistic Hamiltonians is required before claiming direct applicability. revision: yes
Referee: [Numerical results] Numerical evidence section: the modeling choice that post-Clifford commutation relations behave like a random-graph instance is presented without a quantitative check (e.g., degree distribution or clique number) against the actual commutation graphs arising from the paper's own random subsets, weakening the link between the heuristic bound and the conjecture.

Authors: The random-graph heuristic is used to obtain an analytic upper bound on the expected number of parts. We will add a quantitative comparison (degree distributions and clique numbers) between the commutation graphs generated from our random subsets and Erdős–Rényi instances in the revised numerical section to strengthen this link. revision: yes

standing simulated objections not resolved

Analytic derivation of the conjectured linear reduction in partition count under arbitrary Clifford conjugation.

Circularity Check

0 steps flagged

No circularity; bound uses external random-graph results and conjecture is numerically evidenced rather than self-derived

full rationale

The paper states an upper bound on partition size obtained from known heuristics on coloring random graphs and presents the linear scaling conjecture under arbitrary Cliffords as a claim supported by numerical checks on random Pauli subsets. No equation or claim reduces by construction to a fitted parameter, self-citation chain, or renamed input; the central conjecture is explicitly labeled as such and is not forced by the paper's own modeling choices. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on the standard fact that two Pauli operators can be measured simultaneously after Clifford conjugation if and only if they commute, plus known asymptotic results on the chromatic number of random graphs; no free parameters or invented entities are introduced.

axioms (2)

domain assumption Two Pauli strings commute after Clifford conjugation precisely when their supports satisfy the usual commutation relation on overlapping qubits.
Invoked when the simultaneous-measurability graph is defined.
standard math The chromatic number of the random graph formed by non-commuting Pauli pairs follows the known random-graph scaling.
Used to obtain the stated upper bound on expected partition size.

pith-pipeline@v0.9.0 · 5653 in / 1456 out tokens · 19477 ms · 2026-05-24T20:08:17.163412+00:00 · methodology

discussion (0)

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

An Error-aware and Adaptive Method for the Estimation of Quantum Observables on Qudit-Based Quantum Computers
quant-ph 2026-05 unverdicted novelty 7.0

AQUIRE is the first error-aware adaptive Bayesian protocol for simultaneously estimating the mean and error of observables on qudit quantum computers using generalized Pauli operators and overlap grouping.
Shot-noise reduction for lattice Hamiltonians
quant-ph 2024-10 unverdicted novelty 6.0

Geometric partitioning of lattice Hamiltonians into local patches enables energy measurements in patch eigenbases, producing lower-variance estimators than Pauli grouping for eigenstates with rigorous guarantees even ...
Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
quant-ph 2025-07 unverdicted novelty 5.0

A hybrid quantization scheme enables efficient switching between first- and second-quantization in quantum circuits for molecular systems, claiming up to three orders of magnitude fewer ground-state preparations for 2...