Optimal Scheduling of Graph States via Path Decompositions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913667285516288 |
|---|---|
| author | Elman, Samuel J. Gavriel, Jason Mann, Ryan L. |
| author_facet | Elman, Samuel J. Gavriel, Jason Mann, Ryan L. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04126 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Scheduling of Graph States via Path Decompositions Elman, Samuel J. Gavriel, Jason Mann, Ryan L. Quantum Physics Computational Complexity Data Structures and Algorithms 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. |
| title | Optimal Scheduling of Graph States via Path Decompositions |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.04126 |