Optimal Scheduling of Graph States via Path Decompositions
<|reference_start|>Optimal Scheduling of Graph States via Path Decompositions: 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 $\textsf{NP}$-hard, while for graphs with bounded spatial cost, we establish an efficient algorithm for computing an optimal measurement schedule.<|reference_end|>
@article{elman2024optimal,
    title={Optimal Scheduling of Graph States via Path Decompositions},
    author={Samuel J. Elman, Jason Gavriel, Ryan L. Mann},
    journal={arXiv preprint arXiv:2403.04126},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04126},
    primaryClass={quant-ph cs.CC cs.DS}
}