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:2311.11826

Optimised Baranyai partitioning of the second quantised Hamiltonian

Bence Csakany, Alex J. W. Thom

Published Nov 20, 2023• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2311.11826

Related papers

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

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

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

Pauli-string grouping for VQE measurement reduction on a sparse-connectivity quantum annealer

Raul Martinez, Miguel Sanchez-Beato, Mario Calonge

The Variational Quantum Eigensolver (VQE) requires a large number of measurements to evaluate molecular Hamiltonians. Expressing a molecular Hamiltonian as a linear combination of Pauli strings creates a measurement bottleneck: non-commuting Pauli strings cannot be measured simultaneously. Consequently, mutually commuting Pauli strings must be grouped and measured together to minimise the number of quantum-state preparations. This task maps to the minimum clique cover problem on a commutativity graph, an NP-hard problem typically addressed using classical heuristics. Although an Ising-model formulation has recently been explored on fully connected CMOS Ising machines and demonstrated on physical quantum annealers only at small scale, the embedding cost that governs its behaviour on hardware with sparse connectivity, where each logical variable must be represented by a chain of physical qubits, has not been characterised. In this work, we formulate the Pauli-grouping problem as a standard QUBO colouring model and study its scalability on a D-Wave quantum annealer. Across a series of molecular systems and for both qubit-wise and full commutativity, we quantify the growth in the number of logical variables and the QUBO interaction density, characterise the physical-qubit and chain-length overhead required for embedding on the Zephyr topology, and compare the annealer's time-to-solution and solution quality with those of heuristic classical baselines. This analysis identifies the threshold of molecular complexity beyond which hardware connectivity prevents viable embedding, and shows that a second, practical limit is reached earlier. The threshold therefore measures how far current annealers are from the regime in which pre-optimising a VQE measurement scheme on hardware would be worth considering.

quant-pharXiv:2609.20861•Sep 11, 2026•0 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

Assessment of Commuting Pauli Product Grouping Measurement Techniques in the Presence of Noise

Zachary Pierce Bansingh

Measuring quantum observables by grouping terms that can be rotated to sums of only products of Pauli ˆz operators (Ising form) is proven to be efficient in near-term quantum computing algorithms.This approach requires extra unitary transformations to rotate the state of interest so that the measurement of a fragment’s Ising form would be equivalent to measurement of the fragment for the unrotated state. These extra rotations allow one to perform a fewer number of measurements by grouping more terms into the measurable fragments with a lower overall estimator variance. However, previous estimations of the number of measurements did not take into account non-unit fidelity of quantum gates implementing the additional transformations. Through a circuit fidelity reduction, additional transformations introduce extra uncertainty and increase the needed number of measurements. Here we consider a simple model for errors introduced by additional gates needed in schemes involving grouping of commuting Pauli products. For a set of molecular electronic Hamiltonians, we confirm that the numbers of measurements in schemes using non-local qubit rotations are still lower than those in their local qubit rotation counterparts, even after accounting for uncertainties introduced by additional gates.

•Jun 1, 2023•0 citations
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.
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.
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.
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 Variational Quantum Eigensolver (VQE) requires a large number of measurements to evaluate molecular Hamiltonians. Expressing a molecular Hamiltonian as a linear combination of Pauli strings creates a measurement bottleneck: non-commuting Pauli strings cannot be measured simultaneously. Consequently, mutually commuting Pauli strings must be grouped and measured together to minimise the number of quantum-state preparations. This task maps to the minimum clique cover problem on a commutativity graph, an NP-hard problem typically addressed using classical heuristics. Although an Ising-model formulation has recently been explored on fully connected CMOS Ising machines and demonstrated on physical quantum annealers only at small scale, the embedding cost that governs its behaviour on hardware with sparse connectivity, where each logical variable must be represented by a chain of physical qubits, has not been characterised. In this work, we formulate the Pauli-grouping problem as a standard QUBO colouring model and study its scalability on a D-Wave quantum annealer. Across a series of molecular systems and for both qubit-wise and full commutativity, we quantify the growth in the number of logical variables and the QUBO interaction density, characterise the physical-qubit and chain-length overhead required for embedding on the Zephyr topology, and compare the annealer's time-to-solution and solution quality with those of heuristic classical baselines. This analysis identifies the threshold of molecular complexity beyond which hardware connectivity prevents viable embedding, and shows that a second, practical limit is reached earlier. The threshold therefore measures how far current annealers are from the regime in which pre-optimising a VQE measurement scheme on hardware would be worth considering.
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.
Measuring quantum observables by grouping terms that can be rotated to sums of only products of Pauli ˆz operators (Ising form) is proven to be efficient in near-term quantum computing algorithms.This approach requires extra unitary transformations to rotate the state of interest so that the measurement of a fragment’s Ising form would be equivalent to measurement of the fragment for the unrotated state. These extra rotations allow one to perform a fewer number of measurements by grouping more terms into the measurable fragments with a lower overall estimator variance. However, previous estimations of the number of measurements did not take into account non-unit fidelity of quantum gates implementing the additional transformations. Through a circuit fidelity reduction, additional transformations introduce extra uncertainty and increase the needed number of measurements. Here we consider a simple model for errors introduced by additional gates needed in schemes involving grouping of commuting Pauli products. For a set of molecular electronic Hamiltonians, we confirm that the numbers of measurements in schemes using non-local qubit rotations are still lower than those in their local qubit rotation counterparts, even after accounting for uncertainties introduced by additional gates.