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:2305.11847 · Physical Review A

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

Ben Reggio, Nouman Butt, Andrew Lytle, Patrick Draper

Published Aug 7, 2024• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.110.022606

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

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

Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement

Tomochika Kurita, Morita, Mikio, Hirotaka Oshima +1 more

We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry, one of the most promising applications of quantum computing. The algorithm is based on the Ising model optimization problem, which can be quickly solved using an Ising machine. We develop an algorithm that is applicable to problems with sizes larger than the maximum number of variables that an Ising machine can handle ($n_\text{bit}$) through its iterative use. The algorithm has much better time complexity and solution optimality than other algorithms such as Boppana--Halldórsson algorithm and Bron--Kerbosch algorithm, making it useful for the quick and effective reduction of the number of quantum circuits required for measuring the expectation values of multiple Pauli strings. We investigate the performance of the algorithm using the second-generation Digital Annealer, a high-performance Ising hardware, for up to $65,535$ Pauli strings using Hamiltonians of molecules and the full tomography of quantum states. We demonstrate that partitioning problems for quantum chemical calculations can be solved with a time complexity of $O(N)$ for $N\leq n_\text{bit}$ and $O(N^2)$ for $N>n_\text{bit}$ for the worst case, where $N$ denotes the number of candidate Pauli strings and $n_\text{bit}=8,192$ for the second-generation Digital Annealer used in this study. The reduction factor, which is the number of Pauli strings divided by the number of obtained partitions, can be $200$ at maximum.

arXiv:2205.03999•May 9, 2022•0 citations

Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families

Pranav Gokhale, Olivia Angiuli, Yongshan Ding +5 more

Variational quantum eigensolver (VQE) is a promising algorithm suitable for near-term quantum machines. VQE aims to approximate the lowest eigenvalue of an exponentially sized matrix in polynomial time. It minimizes quantum resource requirements both by co-processing with a classical processor and by structuring computation into many subproblems. Each quantum subproblem involves a separate state preparation terminated by the measurement of one Pauli string. However, the number of such Pauli strings scales as $N^4$ for typical problems of interest--a daunting growth rate that poses a serious limitation for emerging applications such as quantum computational chemistry. We introduce a systematic technique for minimizing requisite state preparations by exploiting the simultaneous measurability of partitions of commuting Pauli strings. Our work encompasses algorithms for efficiently approximating a MIN-COMMUTING-PARTITION, as well as a synthesis tool for compiling simultaneous measurement circuits. For representative problems, we achieve 8-30x reductions in state preparations, with minimal overhead in measurement circuit cost. We demonstrate experimental validation of our techniques by estimating the ground state energy of deuteron on an IBM Q 20-qubit machine. We also investigate the underlying statistics of simultaneous measurement and devise an adaptive strategy for mitigating harmful covariance terms.

arXiv:1907.13623•Jul 31, 2019•76 citations

Measurement reduction for expectation values via fine-grained commutativity

Ben DalFavero, Rahul Sarkar, Jeremiah Rowland +3 more

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.

arXiv:2312.11840•Physical Review A•Oct 6, 2025•3 citations

Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurements

Tomochika Kurita, Mikio Morita, Hirotaka Oshima +1 more

High Resolution Image Download MS PowerPoint Slide We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry, one of the most promising applications of quantum computing. The algorithm is based on the Ising model optimization problem, which can be quickly solved using an Ising machine. We develop an algorithm that is applicable to problems with sizes larger than the maximum number of variables that an Ising machine can handle ( n bit ) through its iterative use. The algorithm has much better time complexity and solution optimality than other existing algorithms. We investigate the performance of the algorithm using the second-generation Digital Annealer, a high-performance Ising hardware, for up to 65535 Pauli strings using Hamiltonians of molecules and the full tomography of quantum states. We demonstrate a time complexity of O ( N ) for N ≤ n bit and O ( N 2 ) for N > n bit for the worst case, where N denotes the number of candidate Pauli strings and n bit = 8,192 in this study. The reduction factor, which is the number of Pauli strings divided by the number of obtained partitions, can be 200 at maximum.

The Journal of Physical Chemistry A•Jan 18, 2023•9 citations
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.
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.
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.
We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry, one of the most promising applications of quantum computing. The algorithm is based on the Ising model optimization problem, which can be quickly solved using an Ising machine. We develop an algorithm that is applicable to problems with sizes larger than the maximum number of variables that an Ising machine can handle (nbitn_\text{bit}nbit​) through its iterative use. The algorithm has much better time complexity and solution optimality than other algorithms such as Boppana--Halldórsson algorithm and Bron--Kerbosch algorithm, making it useful for the quick and effective reduction of the number of quantum circuits required for measuring the expectation values of multiple Pauli strings. We investigate the performance of the algorithm using the second-generation Digital Annealer, a high-performance Ising hardware, for up to 65,53565,53565,535 Pauli strings using Hamiltonians of molecules and the full tomography of quantum states. We demonstrate that partitioning problems for quantum chemical calculations can be solved with a time complexity of O(N)O(N)O(N) for N≤nbitN\leq n_\text{bit}N≤nbit​ and O(N2)O(N^2)O(N2) for N>nbitN>n_\text{bit}N>nbit​ for the worst case, where NNN denotes the number of candidate Pauli strings and nbit=8,192n_\text{bit}=8,192nbit​=8,192 for the second-generation Digital Annealer used in this study. The reduction factor, which is the number of Pauli strings divided by the number of obtained partitions, can be 200200200 at maximum.
Variational quantum eigensolver (VQE) is a promising algorithm suitable for near-term quantum machines. VQE aims to approximate the lowest eigenvalue of an exponentially sized matrix in polynomial time. It minimizes quantum resource requirements both by co-processing with a classical processor and by structuring computation into many subproblems. Each quantum subproblem involves a separate state preparation terminated by the measurement of one Pauli string. However, the number of such Pauli strings scales as N4N^4N4 for typical problems of interest--a daunting growth rate that poses a serious limitation for emerging applications such as quantum computational chemistry. We introduce a systematic technique for minimizing requisite state preparations by exploiting the simultaneous measurability of partitions of commuting Pauli strings. Our work encompasses algorithms for efficiently approximating a MIN-COMMUTING-PARTITION, as well as a synthesis tool for compiling simultaneous measurement circuits. For representative problems, we achieve 8-30x reductions in state preparations, with minimal overhead in measurement circuit cost. We demonstrate experimental validation of our techniques by estimating the ground state energy of deuteron on an IBM Q 20-qubit machine. We also investigate the underlying statistics of simultaneous measurement and devise an adaptive strategy for mitigating harmful covariance terms.
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.
High Resolution Image Download MS PowerPoint Slide We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry, one of the most promising applications of quantum computing. The algorithm is based on the Ising model optimization problem, which can be quickly solved using an Ising machine. We develop an algorithm that is applicable to problems with sizes larger than the maximum number of variables that an Ising machine can handle ( n bit ) through its iterative use. The algorithm has much better time complexity and solution optimality than other existing algorithms. We investigate the performance of the algorithm using the second-generation Digital Annealer, a high-performance Ising hardware, for up to 65535 Pauli strings using Hamiltonians of molecules and the full tomography of quantum states. We demonstrate a time complexity of O ( N ) for N ≤ n bit and O ( N 2 ) for N > n bit for the worst case, where N denotes the number of candidate Pauli strings and n bit = 8,192 in this study. The reduction factor, which is the number of Pauli strings divided by the number of obtained partitions, can be 200 at maximum.