Quantum State Tomography - Optimizing and Scheduling Quantum State Tomography Experiments with Graph Coloring Heuristics

Abstract

Quantum State Tomography (QST) is the standard tool for reconstructing an unknown quantum state-typically represented by a density matrix-through the measurement of expectation values of a set of observables (data acquisition step), followed by suitable post-processing. One of the key challenges in QST is to determine an optimal set of quantum circuits (unitary operations) to measure a tomographically complete set of observables-a task that becomes computationally hard due to the exponential scaling of the Hilbert space with the number of qubits. In this work, we recast the task of identifying an optimal set of quantum circuits in QST as a graph coloring problem. Within this framework, we explore a variety of algorithms and heuristic approaches to optimize QST experiments, including Degree of Saturation (DSATUR), Recursive Largest First (RLF), Integer Linear Programming (ILP), Graph Neural Networks (GNNs), Spectral Clustering (SC), and a range of hybrid methods that aim to balance solution optimality with computational efficiency. Our results demonstrate that the graph coloring heuristic not only determines and substantially reduces the number of required quantum circuits but also guides appropriate priority-based experiment scheduling that maximizes information gain per experimental setting for efficient QST. Furthermore, the optimization process completes within minutes for systems of up to five qubits on a standard laptop, offering a substantial speedup over brute-force methods, which can take several hours. This highlights the heuristic’s potential as a practical and scalable solution for characterizing noisy intermediate-scale quantum (NISQ) devices.