Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2312.11840 · Physical Review A

Measurement reduction for expectation values via fine-grained commutativity

Ben DalFavero, Rahul Sarkar, Jeremiah Rowland, Daan Camps, Nicolas P. D. Sawaya, Ryan LaRose

Published Oct 6, 2025• 3 citations
arXivHTMLPDF

Abstract

We introduce a notion of commutativity between operators on a tensor product space, nominally Pauli strings on qubits, that interpolates between qubitwise commutativity and (full) commutativity. We apply this notion, which we call $k$-commutativity, to measuring expectation values of observables in quantum circuits and show a reduction in the number measurements at the cost of increased circuit depth. We discuss the asymptotic measurement complexity of $k$-commutativity for several families of $n$-qubit Hamiltonians, showing examples with $O(1)$, $O(\sqrt{n})$, and $O(n)$ scaling.

DOI
10.1103/y6hl-gzr4

Related papers

Fast Partitioning of Pauli Strings into Commuting Families for Expectation Value Measurements of Dense Operators

Andrew Lytle, Nouman Butt, Ben Reggio +1 more

The cost of measuring quantum expectation values of an operator can be reduced by grouping the Pauli string (SU(2) tensor product) decomposition of the operator into maximally commuting sets. We detail an algorithm, presented in [1], to partition the full set of m-qubit Pauli strings into the minimal number of commuting families, and benchmark the performance with dense Hamiltonians on IBM hardware. Here we also compare how our method scales compared to graph-theoretic techniques for the generally commuting case.

arXiv:2311.08551•International Symposium on Lattice Field Theory (LATTICE)•May 3, 2024•0 citations

Fast partitioning of Pauli strings into commuting families for optimal expectation value measurements of dense operators

Ben Reggio, Nouman Butt, Andrew Lytle +1 more

The Pauli strings appearing in the decomposition of an operator can be can be grouped into commuting families, reducing the number of quantum circuits needed to measure the expectation value of the operator. 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, and we provide python code to perform the partitioning. The partitioning method scales linearly with the size of the set of Pauli strings and it naturally provides a fast method of diagonalizing the commuting families with quantum gates. We provide a package that integrates the partitioning into qiskit, and use this to benchmark the algorithm with dense Hamiltonians, such as those that arise in matrix quantum mechanics models, on IBM hardware. We demonstrate computational speedups close to the theoretical limit of ${(3/2)}^{m}$ relative to qubit-wise commuting groupings, for $m=2,...\phantom{\rule{0.16em}{0ex}},6$ qubits.

arXiv:2305.11847•Physical Review A•Aug 7, 2024•16 citations

Non-Clifford diagonalization for measurement shot reduction in quantum expectation value estimation

Nicolas P. D. Sawaya, Daan Camps, DalFavero, Ben +3 more

Estimating expectation values on near-term quantum computers often requires a prohibitively large number of measurements. One widely-used strategy to mitigate this problem has been to partition an operator's Pauli terms into sets of mutually commuting operators. Here, we introduce a method that relaxes this constraint of commutativity, instead allowing for entirely arbitrary terms to be grouped together, save a locality constraint. The key idea is that we decompose the operator into arbitrary tensor products with bounded tensor size, ignoring Pauli commuting relations. This method -- named $k$-NoCliD ($k$-local non-Clifford diagonalization) -- allows one to measure in far fewer bases in most cases, often (though not always) at the cost of increasing the circuit depth. We introduce several partitioning algorithms tailored to different Hamiltonian classes. For electronic structure, we numerically demonstrate the existence of threshold values of $k$ for which $k$-NoCliD leads to the lowest shot counts, though we leave improved partitioning algorithms to future work. We focus primarily on three Hamiltonian classes -- molecular vibrational structure, Fermi-Hubbard, and Bose-Hubbard -- and show that $k$-NoCliD reduces the number of circuit shots, often by a very large margin, and often even for $k$ as small as 2.

arXiv:2408.11898•Aug 21, 2024•2 citations

Optimised Baranyai partitioning of the second quantised Hamiltonian

Bence Csakany, Alex J. W. Thom

Simultaneous measurement of multiple Pauli strings (tensor products of Pauli matrices) is the basis for efficient measurement of observables on quantum computers by partitioning the observable into commuting sets of Pauli strings. We present the implementation and optimisation of the Baranyai grouping method for second quantised Hamiltonian partitioning in molecules up to CH$_4$ (cc-pVDZ, 68 qubits) and efficient construction of the diagonalisation circuit in $O(N)$ quantum gates, compared to $O(N^2)$, where $N$ is the number of qubits. We show that this method naturally handles sparsity in the Hamiltonian and produces a $O(1)$ number of groups for linearly scaling Hamiltonians, such as those formed by molecules in a line; rising to $O(N^3)$ for fully connected two-body Hamiltonians. While this is more measurements than some other schemes it allows for the flexibility to move Pauli strings and optimise the variance. We also present an explicit optimisation for spin-symmetry which reduces the number of groups by a factor of $8$, without extra computational effort.

arXiv:2311.11826•Nov 20, 2023•1 citation

Reducing circuit depth with qubitwise diagonalization

Edison M. Murairi, Michael J. Cervia

A variety of quantum algorithms employ Pauli operators as a convenient basis for studying the spectrum or evolution of Hamiltonians or measuring multibody observables. One strategy to reduce circuit depth in such algorithms involves simultaneous diagonalization of Pauli operators generating unitary evolution operators or observables of interest. We propose an algorithm yielding quantum circuits with depths $O(nlogr)$ diagonalizing $n$-qubit operators generated by $r$ Pauli operators. Moreover, as our algorithm iteratively diagonalizes all operators on at least one qubit per step, it is well suited to maintain low circuit depth even on hardware with limited qubit connectivity. We observe that our algorithm performs favorably in producing quantum circuits diagonalizing randomly generated Hamiltonians as well as molecular Hamiltonians with short depths and low two-qubit gate counts.

arXiv:2306.00170•Physical Review A•Dec 13, 2023•2 citations

Verifying random matrix product states with autoregressive local measurements

Hyunho Cha, Subin Kim, Jungwoo Lee

Matrix product states (MPS) are a central language for one-dimensional quantum matter and a practical target for near-term quantum simulators and variational algorithms. Yet, while substantial effort has focused on preparing MPS with shallow circuits, scalable methods to \emph{verify} that a many-body device has actually produced the intended state remain underdeveloped. Direct fidelity estimation (DFE) relies only on local Pauli measurements, but in many-body settings it suffers an exponential classical overhead from the preprocessing needed to sample Pauli strings. We eliminate this obstacle by introducing an \emph{autoregressive} importance sampler that draws Pauli strings sequentially from efficiently computable conditional distributions, reducing the per-shot classical overhead to linear scaling in the number of qubits. We further develop a grouped extension that constructs qubit-wise commuting measurement settings via a \emph{sorting string} and simultaneously estimates the entire commuting group from a single setting, significantly reducing estimator variance while preserving efficient postprocessing. Our approach extends naturally to matrix product operators (MPO), enabling scalable verification of tensor-network states and observables in long one-dimensional quantum systems. We utilize random MPS as a natural benchmark for generic 1D entangled states.

quant-pharXiv:2604.16578•Apr 20, 2026•0 citations
We introduce a notion of commutativity between operators on a tensor product space, nominally Pauli strings on qubits, that interpolates between qubitwise commutativity and (full) commutativity. We apply this notion, which we call kkk-commutativity, to measuring expectation values of observables in quantum circuits and show a reduction in the number measurements at the cost of increased circuit depth. We discuss the asymptotic measurement complexity of kkk-commutativity for several families of nnn-qubit Hamiltonians, showing examples with O(1)O(1)O(1), O(n)O(\sqrt{n})O(n​), and O(n)O(n)O(n) scaling.
The cost of measuring quantum expectation values of an operator can be reduced by grouping the Pauli string (SU(2) tensor product) decomposition of the operator into maximally commuting sets. We detail an algorithm, presented in [1], to partition the full set of m-qubit Pauli strings into the minimal number of commuting families, and benchmark the performance with dense Hamiltonians on IBM hardware. Here we also compare how our method scales compared to graph-theoretic techniques for the generally commuting case.
The Pauli strings appearing in the decomposition of an operator can be can be grouped into commuting families, reducing the number of quantum circuits needed to measure the expectation value of the operator. 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, and we provide python code to perform the partitioning. The partitioning method scales linearly with the size of the set of Pauli strings and it naturally provides a fast method of diagonalizing the commuting families with quantum gates. We provide a package that integrates the partitioning into qiskit, and use this to benchmark the algorithm with dense Hamiltonians, such as those that arise in matrix quantum mechanics models, on IBM hardware. We demonstrate computational speedups close to the theoretical limit of (3/2)m{(3/2)}^{m}(3/2)m relative to qubit-wise commuting groupings, for m=2,...,6m=2,...\phantom{\rule{0.16em}{0ex}},6m=2,...,6 qubits.
Estimating expectation values on near-term quantum computers often requires a prohibitively large number of measurements. One widely-used strategy to mitigate this problem has been to partition an operator's Pauli terms into sets of mutually commuting operators. Here, we introduce a method that relaxes this constraint of commutativity, instead allowing for entirely arbitrary terms to be grouped together, save a locality constraint. The key idea is that we decompose the operator into arbitrary tensor products with bounded tensor size, ignoring Pauli commuting relations. This method -- named kkk-NoCliD (kkk-local non-Clifford diagonalization) -- allows one to measure in far fewer bases in most cases, often (though not always) at the cost of increasing the circuit depth. We introduce several partitioning algorithms tailored to different Hamiltonian classes. For electronic structure, we numerically demonstrate the existence of threshold values of kkk for which kkk-NoCliD leads to the lowest shot counts, though we leave improved partitioning algorithms to future work. We focus primarily on three Hamiltonian classes -- molecular vibrational structure, Fermi-Hubbard, and Bose-Hubbard -- and show that kkk-NoCliD reduces the number of circuit shots, often by a very large margin, and often even for kkk as small as 2.
Simultaneous measurement of multiple Pauli strings (tensor products of Pauli matrices) is the basis for efficient measurement of observables on quantum computers by partitioning the observable into commuting sets of Pauli strings. We present the implementation and optimisation of the Baranyai grouping method for second quantised Hamiltonian partitioning in molecules up to CH4_44​ (cc-pVDZ, 68 qubits) and efficient construction of the diagonalisation circuit in O(N)O(N)O(N) quantum gates, compared to O(N2)O(N^2)O(N2), where NNN is the number of qubits. We show that this method naturally handles sparsity in the Hamiltonian and produces a O(1)O(1)O(1) number of groups for linearly scaling Hamiltonians, such as those formed by molecules in a line; rising to O(N3)O(N^3)O(N3) for fully connected two-body Hamiltonians. While this is more measurements than some other schemes it allows for the flexibility to move Pauli strings and optimise the variance. We also present an explicit optimisation for spin-symmetry which reduces the number of groups by a factor of 888, without extra computational effort.
A variety of quantum algorithms employ Pauli operators as a convenient basis for studying the spectrum or evolution of Hamiltonians or measuring multibody observables. One strategy to reduce circuit depth in such algorithms involves simultaneous diagonalization of Pauli operators generating unitary evolution operators or observables of interest. We propose an algorithm yielding quantum circuits with depths O(nlogr)O(nlogr)O(nlogr) diagonalizing nnn-qubit operators generated by rrr Pauli operators. Moreover, as our algorithm iteratively diagonalizes all operators on at least one qubit per step, it is well suited to maintain low circuit depth even on hardware with limited qubit connectivity. We observe that our algorithm performs favorably in producing quantum circuits diagonalizing randomly generated Hamiltonians as well as molecular Hamiltonians with short depths and low two-qubit gate counts.
Matrix product states (MPS) are a central language for one-dimensional quantum matter and a practical target for near-term quantum simulators and variational algorithms. Yet, while substantial effort has focused on preparing MPS with shallow circuits, scalable methods to \emph{verify} that a many-body device has actually produced the intended state remain underdeveloped. Direct fidelity estimation (DFE) relies only on local Pauli measurements, but in many-body settings it suffers an exponential classical overhead from the preprocessing needed to sample Pauli strings. We eliminate this obstacle by introducing an \emph{autoregressive} importance sampler that draws Pauli strings sequentially from efficiently computable conditional distributions, reducing the per-shot classical overhead to linear scaling in the number of qubits. We further develop a grouped extension that constructs qubit-wise commuting measurement settings via a \emph{sorting string} and simultaneously estimates the entire commuting group from a single setting, significantly reducing estimator variance while preserving efficient postprocessing. Our approach extends naturally to matrix product operators (MPO), enabling scalable verification of tensor-network states and observables in long one-dimensional quantum systems. We utilize random MPS as a natural benchmark for generic 1D entangled states.