⚛️ quantum physics

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

This paper presents a scalable computational framework that reformulates operator partitioning for quantum state tomography as a graph-coloring problem, utilizing heuristic algorithms to efficiently optimize and prioritize measurement settings across multi-qubit, multi-qutrit, and hybrid systems while significantly reducing the number of required experiments compared to brute-force methods.

Original authors: Sumukh S. Moudghalya, Anton Frisk Kockum, Akshay Gaikwad

Published 2026-09-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sumukh S. Moudghalya, Anton Frisk Kockum, Akshay Gaikwad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

To understand the work of quantum scientists, one must first grasp the nature of the object they are trying to see. A quantum system, such as a collection of tiny particles called qubits, exists in a state that is far more complex than a simple switch being on or off. To fully describe this state, researchers must reconstruct a mathematical map known as a density matrix. This map contains every possible detail about the system's behavior. The standard method for creating this map is called quantum state tomography. It is a process of taking many different measurements to piece together the whole picture. However, as the system grows larger, the number of measurements required explodes. For a system with just a few particles, the number of settings needed becomes so vast that gathering the data would take an impractical amount of time, even if the measurements themselves were instantaneous. The bottleneck is not just the time it takes to measure, but the sheer number of different configurations a scientist must set up to ensure they have not missed a single piece of information.

A team of researchers at Chalmers University of Technology in Sweden has developed a new way to tackle this overwhelming complexity. Instead of trying to measure every possible configuration one by one, they found a way to group the measurements together. Their approach relies on a mathematical concept called graph coloring, which is a method for organizing items into groups so that no two conflicting items end up in the same group. In the context of quantum physics, two measurements conflict if they cannot be performed at the same time. The researchers realized that if they could identify groups of measurements that do not conflict, they could perform all the measurements in a group simultaneously. This reduces the total number of experimental setups required.

The team treated the problem of organizing these measurements as a puzzle. They created a map where every possible measurement was a point, and lines connected points that could not be measured together. Their goal was to color the points using as few colors as possible, where each color represented a single experimental setup. By using efficient computer algorithms to solve this coloring puzzle, they could determine the smallest number of setups needed to get a complete picture of the quantum state. They tested several different strategies to solve this puzzle, including methods that look for the most crowded points first, methods that use artificial intelligence to learn patterns, and methods that try to find the absolute perfect solution. They found that while finding the perfect solution is computationally impossible for larger systems, their heuristic methods—smart shortcuts that get very close to the best answer—could solve the problem in seconds on a standard laptop.

The results of their simulations were striking. For a system of five qubits, which is relatively small in the world of quantum computing, the traditional approach would require hundreds of measurement settings. Their new method reduced this number significantly, often cutting the required settings by more than half compared to standard random sampling techniques. For example, in a four-qubit system, they achieved a high-quality reconstruction of the quantum state with only twenty-five measurement settings, whereas the standard method needed many more to reach the same level of accuracy. The researchers also demonstrated that the order in which these measurements are taken matters. By performing the most informative groups of measurements first, they could build up a clear picture of the system much faster, allowing them to stop the experiment early if they had already gathered enough information.

This framework is not limited to simple particles called qubits. The researchers successfully applied their method to more complex systems involving particles with three states, known as qutrits, and even mixed systems containing both types. In every case, their graph-coloring approach provided a practical way to schedule experiments that would otherwise be too slow to run. They also showed how to translate these abstract groups of measurements into actual physical instructions for a quantum computer, using a specific set of basic operations to align the system for measurement. While the paper notes that implementing these instructions on real hardware still presents engineering challenges, the theoretical framework provides a clear path forward.

The significance of this work lies in its ability to make the characterization of quantum devices faster and more efficient. As quantum computers grow in size and complexity, the ability to quickly verify their state is essential for their development. By reducing the number of experiments needed, this method saves valuable time and resources. The researchers have made their computer code available to the public, allowing others to use these tools to optimize their own experiments. Their findings suggest that by viewing the problem of measurement as a coloring puzzle, scientists can bypass the combinatorial explosion that has long hindered progress in quantum state tomography, making the characterization of noisy, intermediate-scale quantum devices a more manageable task.

Technical Summary: Heuristically Optimizing, Synthesizing, and Prioritizing Measurement Settings for Quantum State Tomography

Problem Statement
Quantum State Tomography (QST) is essential for reconstructing the density matrix of a quantum system but faces a "curse of dimensionality." As system size grows, the number of required experiments and the computational cost of reconstruction increase exponentially. A primary bottleneck lies in the data acquisition stage: efficiently partitioning an arbitrary set of observables into mutually commuting subsets. While brute-force approaches can find optimal partitions for small systems, they become intractable as the number of operators and system dimensionality increase. Furthermore, existing strategies often target specific tasks (e.g., estimating specific matrix elements) or rely on structures like Mutually Unbiased Bases (MUBs) that are not universally applicable to arbitrary-dimensional Hilbert spaces or reduced subspaces. The challenge is to find a computationally efficient method to partition arbitrary operator sets into the minimum number of commuting subsets to minimize measurement settings, and to prioritize these settings to maximize information gain early in the process.

Methodology
The authors reformulate the operator partitioning problem as a Graph Coloring (GC) problem.

Graph Construction: An undirected graph is constructed where vertices represent operators. An edge connects two vertices if and only if the corresponding operators do not commute.
Partitioning via GC: The goal is to color the graph such that no two adjacent vertices share a color, minimizing the total number of colors (the chromatic number). Each color class corresponds to a set of mutually commuting operators that can be measured simultaneously in a common eigenbasis.
Algorithmic Framework: The paper benchmarks five distinct algorithms to solve this GC problem:
- Degree of Saturation (DSATUR): A heuristic ordering vertices by the number of distinct colors assigned to their neighbors.
- Recursive Largest First (RLF): A heuristic prioritizing vertices with the highest degree (most neighbors).
- Integer Linear Programming (ILP): An exact method formulated as a Minimum Clique Cover (MCC) problem on the complement graph (the commutation graph), solved using solvers like CBC.
- Graph Neural Networks (GNNs): A learning-based approach treating coloring as a node-classification problem, trained on operator-commutation graphs to predict partitions.
- Spectral Clustering (SC): A method leveraging the eigenstructure of the graph Laplacian to cluster nodes based on commutation similarity.
Circuit Synthesis: For each identified commuting subset, the authors synthesize change-of-basis quantum circuits using a binary symplectic representation and symplectic Gaussian elimination. These circuits consist solely of elementary Clifford gates (Hadamard, Phase, CNOT) to enable joint measurement.
Prioritization Strategy: Once partitions are generated, the authors propose a scheduling strategy that orders measurement settings by the cardinality (size) of the commuting subsets, executing the largest subsets first to maximize information gain per experiment.

Key Contributions

Generalized Framework: The work provides a unified framework applicable to arbitrary operator sets and arbitrary-dimensional Hilbert spaces, including multi-qubit, multi-qutrit, and hybrid qubit-qutrit systems, moving beyond the limitations of Pauli-specific algebraic methods.
Algorithm Benchmarking: A comprehensive comparison of heuristic and exact GC algorithms for QST. The study identifies DSATUR as the heuristic offering the best trade-off between solution quality (number of partitions) and runtime, with GNNs showing promise for rapid inference after training.
Efficiency Gains: The framework demonstrates that heuristic GC methods can reduce the number of required measurement settings significantly compared to standard random sampling protocols (e.g., $\{I, R_x, R_y\}^{\otimes N}$ ), while converging within minutes on standard consumer hardware (8-core CPU, 16 GB RAM).
Open Source Implementation: The authors provide a public Python implementation of the framework, including the GC algorithms and circuit synthesis tools.

Results
The framework was validated on systems up to five qubits, three qutrits, and hybrid configurations (e.g., $2q \otimes 2t$ ).

Partitioning Performance:
- ILP achieved optimal partition counts for smaller systems (up to 4 qubits) but became intractable for larger instances (e.g., 5 qubits, 3 qutrits) due to exponential runtime.
- Heuristics (DSATUR, GNN, RLF, SC) produced solutions in seconds to minutes. DSATUR and GNN consistently yielded the fewest partitions among heuristics, often approaching the theoretical optimum (e.g., $2^N + 1$ for $N$ qubits).
- For a 5-qubit system (1,023 operators), DSATUR and GNN generated valid partitions in tens of seconds, whereas ILP failed to converge in a practical timeframe.
Tomography Performance:
- Using the priority-based scheduling (largest subsets first), the GC-derived schedules achieved high-fidelity state reconstruction with significantly fewer measurements than standard QST.
- For a 4-qubit system, GC-based methods (GNN, DSATUR) achieved near-perfect fidelity ( $F \approx 1$ ) with only 25 settings, whereas standard QST required many more settings to reach similar fidelity and remained below 0.75 with the same number of settings.
- The priority scheduling allowed for rapid accumulation of information; for 5-qubit systems, average fidelity exceeded 0.9 after just 50 settings, compared to 0.65 for standard protocols.

Significance and Claims
The paper claims that graph-coloring heuristics offer a scalable and practical tool for characterizing noisy intermediate-scale quantum (NISQ) devices. By shifting the optimization focus from classical post-processing to the data-acquisition stage, the framework reduces experimental overhead and measurement time.

Scalability: The approach enables the characterization of systems where brute-force partitioning is impossible, providing speedups of several orders of magnitude.
Adaptability: The priority-based scheduling allows experimentalists to stop data acquisition once a target fidelity is reached, making the process adaptive.
Versatility: The method is not limited to qubits or Pauli operators, extending naturally to qutrits and hybrid systems, addressing a gap in current tomography protocols.
Future Outlook: The authors note that while the framework is robust, challenges remain in efficiently synthesizing the change-of-basis circuits for arbitrary commuting sets on universal gate sets. They suggest that GNNs, due to their ability to generalize from training on small examples to larger unseen systems, represent a particularly promising direction for future scalable measurement scheduling.

Technical Summary: Heuristically Optimizing, Synthesizing, and Prioritizing Measurement Settings for Quantum State Tomography

More like this