Samuel J. Elman, Jason Gavriel, Ryan L. Mann (Mar 08 2024).
Abstract: We study the optimal scheduling of graph states in measurement-based quantum computation, establishing an equivalence between measurement schedules and path decompositions of graphs. We define the spatial cost of a measurement schedule based on the number of simultaneously active qubits and prove that an optimal measurement schedule corresponds to a path decomposition of minimal width. Our analysis shows that approximating the spatial cost of a graph is \textsfNP-hard, while for graphs with bounded spatial cost, we establish an efficient algorithm for computing an optimal measurement schedule.