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

Pauli Partitioning with Respect to Gate Sets

Andrew Jena, Scott N. Genin, Michele Mosca

Published Jul 18, 2019• 124 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.1907.07859

Related papers

Optimization of variational-quantum-eigensolver measurement by partitioning Pauli operators using multiqubit Clifford gates on noisy intermediate-scale quantum hardware

Andrew Jena, Scott N. Genin, Michele Mosca

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 Pauli operators allows for fewer measurements and an overall speedup of the measurement process. Using results from coloring random graphs, we give evidence for an upper bound on the expected minimum number of simultaneously measurable parts necessary to partition a set of Pauli operators. By expanding our gate set to allow multiqubit Clifford gates before measurement, we were able to cut down the number of measurements considerably compared to previous approaches. We conjecture that this improvement is, in general, linear with respect to the lengths of the Pauli operators. We conclude by demonstrating the feasibility of this approach by implementing the variational quantum eigensolver on the Aspen-4-4Q-A quantum processor unit. In doing so, we calculate the ground-state energies of ${\mathrm{H}}_{2}$ using fewer measurements than is possible with single-qubit gates with no statistically significant difference in accuracy.

Physical Review A•Oct 27, 2022•13 citations

Heuristically optimizing, synthesizing, and prioritizing measurement settings for quantum state tomography

Sumukh S. Moudghalya, Anton Frisk Kockum, Akshay Gaikwad

A key task in many quantum-computing applications, e.g., quantum simulation and quantum state tomography (QST), is to partition an arbitrary set of operators into mutually commuting subsets for efficient measurements. However, brute-force approaches to this task quickly become intractable as the number and dimensionality of operators grow. Here, we reformulate operator partitioning as a graph-coloring (GC) problem and develop an efficient computational framework to solve it, balancing accuracy and efficiency. Our framework enables leveraging a range of GC algorithms, which we benchmark for operator partitioning. Then, we demonstrate their utility in optimizing QST experiments, where determining non-overlapping data acquisition settings for QST is a major challenge, and prioritizing among these settings, i.e., selecting the experiments that provide the most information. We further show how to perform these experiments by synthesizing Clifford circuits for joint measurement of commuting Pauli operators in multi-qubit systems. We validate our framework across multi-qubit (up to five qubits), multi-qutrit (up to three qutrits), and hybrid qubit-qutrit systems. Our results show that heuristic GC methods substantially reduce the number of required measurement settings for QST and enable priority-based scheduling that maximizes the information gain per experiment. The optimization converges within minutes on a student-grade laptop, providing speedups of several orders of magnitude over brute-force methods already for these relatively small quantum systems. This demonstrates the potential of GC heuristics as a scalable and practical tool for characterization of noisy intermediate-scale quantum devices. We have made the Python implementation of our GC framework to optimize and schedule QST experiments publicly available at https://github.com/ssm8015/QST_GT.git.

quant-pharXiv:2609.02633•Sep 3, 2026•0 citations

Partitioning Pauli Operators: in Theory and in Practice

Andrew Jena

Measuring the expectation value of Pauli operators on prepared quantum states is a \nfundamental task in the variational quantum eigensolver. Simultaneously measuring sets \nof operators allows for fewer measurements and an overall speedup of the measurement \nprocess. In this thesis, we look both at the task of partitioning all Pauli operators of a \n xed length and of partitioning a random subset of these Pauli operators. We rst show \nhow Singer cycles can be used to optimally partition the set of all Pauli operators, giving \nsome insight to the structure underlying many constructions of mutually unbiased bases. \nThereafter, we show how graph coloring algorithms promise to provide speedups linear \nwith respect to the lengths of the operators over currently-implemented techniques in the \nmeasurement step of the variational quantum eigensolver.

•Sep 4, 2019•1 citation

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•23 citations

Measuring All Compatible Operators in One Series of Single-Qubit Measurements Using Unitary Transformations

Tzu-Ching Yen, Vladyslav Verteletskyi, Artur F. Izmaylov

The Variational Quantum Eigensolver approach to the electronic structure problem on a quantum computer involves measurement of the Hamiltonian expectation value. Formally, quantum mechanics allows one to measure all mutually commuting or compatible operators simultaneously. Unfortunately, the current hardware permits measuring only a much more limited subset of operators that share a common tensor product eigen-basis. We introduce unitary transformations that transform any fully commuting group of operators to a group that can be measured on current hardware. These unitary operations can be encoded as a sequence of Clifford gates and let us not only measure much larger groups of terms but also to obtain these groups efficiently on a classical computer. The problem of finding the minimum number of fully commuting groups of terms covering the whole Hamiltonian is found to be equivalent to the minimum clique cover problem for a graph representing Hamiltonian terms as vertices and commutativity between them as edges. Tested on a set of molecular electronic Hamiltonians with up to 50 thousand terms, the introduced technique allows for the reduction of the number of separately measurable operator groups down to few hundreds, thus achieving up to 2 orders of magnitude reduction. Based on the test set results, the obtained gain scales at least linearly with the number of qubits.

arXiv:1907.09386•Journal of Chemical Theory and Computation•Mar 9, 2020•207 citations

Efficient quantum measurement of Pauli operators in the presence of finite sampling error

Ophelia Crawford, Barnaby van Straaten, Daochen Wang +3 more

Estimating the expectation value of an operator corresponding to an observable is a fundamental task in quantum computation. It is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the operator into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version collects mutually commuting Pauli operators together before measuring all operators within a collection simultaneously. The effectiveness of doing this depends on two factors. Firstly, we must understand the improvement offered by a given arrangement of Paulis in collections. In our work, we propose two natural metrics for quantifying this, operating under the assumption that measurements are distributed optimally among collections so as to minimise the overall finite sampling error. Motivated by the mathematical form of these metrics, we introduce S ORTED I NSERTION, a collecting strategy that exploits the weighting of each Pauli operator in the overall sum. Secondly, to measure all Pauli operators within a collection simultaneously, a circuit is required to rotate them to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any collection of k independent commuting n -qubit Pauli operators using at most k n − k ( k + 1 ) / 2 and O ( k n / log ⁡ k ) two-qubit gates respectively. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the operators in question are molecular Hamiltonians. As measured by our metrics, S ORTED I NSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of collections.

arXiv:1908.06942•Quantum•Jan 20, 2021•236 citations
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.
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 Pauli operators allows for fewer measurements and an overall speedup of the measurement process. Using results from coloring random graphs, we give evidence for an upper bound on the expected minimum number of simultaneously measurable parts necessary to partition a set of Pauli operators. By expanding our gate set to allow multiqubit Clifford gates before measurement, we were able to cut down the number of measurements considerably compared to previous approaches. We conjecture that this improvement is, in general, linear with respect to the lengths of the Pauli operators. We conclude by demonstrating the feasibility of this approach by implementing the variational quantum eigensolver on the Aspen-4-4Q-A quantum processor unit. In doing so, we calculate the ground-state energies of H2{\mathrm{H}}_{2}H2​ using fewer measurements than is possible with single-qubit gates with no statistically significant difference in accuracy.
A key task in many quantum-computing applications, e.g., quantum simulation and quantum state tomography (QST), is to partition an arbitrary set of operators into mutually commuting subsets for efficient measurements. However, brute-force approaches to this task quickly become intractable as the number and dimensionality of operators grow. Here, we reformulate operator partitioning as a graph-coloring (GC) problem and develop an efficient computational framework to solve it, balancing accuracy and efficiency. Our framework enables leveraging a range of GC algorithms, which we benchmark for operator partitioning. Then, we demonstrate their utility in optimizing QST experiments, where determining non-overlapping data acquisition settings for QST is a major challenge, and prioritizing among these settings, i.e., selecting the experiments that provide the most information. We further show how to perform these experiments by synthesizing Clifford circuits for joint measurement of commuting Pauli operators in multi-qubit systems. We validate our framework across multi-qubit (up to five qubits), multi-qutrit (up to three qutrits), and hybrid qubit-qutrit systems. Our results show that heuristic GC methods substantially reduce the number of required measurement settings for QST and enable priority-based scheduling that maximizes the information gain per experiment. The optimization converges within minutes on a student-grade laptop, providing speedups of several orders of magnitude over brute-force methods already for these relatively small quantum systems. This demonstrates the potential of GC heuristics as a scalable and practical tool for characterization of noisy intermediate-scale quantum devices. We have made the Python implementation of our GC framework to optimize and schedule QST experiments publicly available at https://github.com/ssm8015/QST_GT.git.
Measuring the expectation value of Pauli operators on prepared quantum states is a \nfundamental task in the variational quantum eigensolver. Simultaneously measuring sets \nof operators allows for fewer measurements and an overall speedup of the measurement \nprocess. In this thesis, we look both at the task of partitioning all Pauli operators of a \n xed length and of partitioning a random subset of these Pauli operators. We rst show \nhow Singer cycles can be used to optimally partition the set of all Pauli operators, giving \nsome insight to the structure underlying many constructions of mutually unbiased bases. \nThereafter, we show how graph coloring algorithms promise to provide speedups linear \nwith respect to the lengths of the operators over currently-implemented techniques in the \nmeasurement step of the variational quantum eigensolver.
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 Variational Quantum Eigensolver approach to the electronic structure problem on a quantum computer involves measurement of the Hamiltonian expectation value. Formally, quantum mechanics allows one to measure all mutually commuting or compatible operators simultaneously. Unfortunately, the current hardware permits measuring only a much more limited subset of operators that share a common tensor product eigen-basis. We introduce unitary transformations that transform any fully commuting group of operators to a group that can be measured on current hardware. These unitary operations can be encoded as a sequence of Clifford gates and let us not only measure much larger groups of terms but also to obtain these groups efficiently on a classical computer. The problem of finding the minimum number of fully commuting groups of terms covering the whole Hamiltonian is found to be equivalent to the minimum clique cover problem for a graph representing Hamiltonian terms as vertices and commutativity between them as edges. Tested on a set of molecular electronic Hamiltonians with up to 50 thousand terms, the introduced technique allows for the reduction of the number of separately measurable operator groups down to few hundreds, thus achieving up to 2 orders of magnitude reduction. Based on the test set results, the obtained gain scales at least linearly with the number of qubits.
Estimating the expectation value of an operator corresponding to an observable is a fundamental task in quantum computation. It is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the operator into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version collects mutually commuting Pauli operators together before measuring all operators within a collection simultaneously. The effectiveness of doing this depends on two factors. Firstly, we must understand the improvement offered by a given arrangement of Paulis in collections. In our work, we propose two natural metrics for quantifying this, operating under the assumption that measurements are distributed optimally among collections so as to minimise the overall finite sampling error. Motivated by the mathematical form of these metrics, we introduce S ORTED I NSERTION, a collecting strategy that exploits the weighting of each Pauli operator in the overall sum. Secondly, to measure all Pauli operators within a collection simultaneously, a circuit is required to rotate them to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any collection of k independent commuting n -qubit Pauli operators using at most k n − k ( k + 1 ) / 2 and O ( k n / log ⁡ k ) two-qubit gates respectively. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the operators in question are molecular Hamiltonians. As measured by our metrics, S ORTED I NSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of collections.