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 NP-hard, while for graphs with bounded spatial cost, we establish an efficient algorithm for computing an optimal measurement schedule.
Authors
- Ryan L. Mann (ORCID: https://orcid.org/0000-0002-5118-8467)
- Samuel J. Elman (ORCID: https://orcid.org/0000-0003-2140-4787)
- Jason Gavriel (ORCID: https://orcid.org/0009-0008-5834-7521)
Institutions
- University of Technology Sydney (AU)
- Centre for Quantum Computation and Communication Technology (AU)
Publication Details
- Journal
- Physical review. A/Physical review, A
- Published
- 2025-01-27
- DOI
- https://doi.org/10.1103/physreva.111.012627
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- U.S. Department of Defense
- Defense Advanced Research Projects Agency
- Centre of Excellence for Quantum Computation and Communication Technology, Australian Research Council