Optimal Scheduling of Graph States via Path Decompositions
March 8, 2024
Jason Gavriel, Samuel Elman, and I have just uploaded to arXiv our paper "Optimal Scheduling of Graph States via Path Decompositions". In this paper we study the optimal scheduling of graph states in measurement-based quantum computation, establishing an equivalence between measurement schedules and path decompositions of graphs.
- A qubit is initialised exactly once.
- A qubit is measured only after all neighbouring qubits are initialised.
We say that a qubit is active if it has been initialised but not yet measured. We shall represent a measurement schedule as a sequence of subsets of vertices $(X_i)_{i=1}^n$, with each subset corresponding to the qubits that are active at a given step. The cost of a measurement schedule is $\max_{i}|X_i|$. The spatial cost $\operatorname{sc}(\ket{G})$ of a graph state $\ket{G}$ is the minimum cost over all possible measurement schedules on $\ket{G}$. We say that a measurement schedule is optimal if its cost is equal to the spatial cost. Note that there may be multiple optimal measurement schedules for a given graph state.
- For each $v \in V$, there exists an $i$ such that $v \in X_i$.
- For each $e \in E$, there exists an $i$ such that $e \subseteq X_i$.
- For all $i \leq j \leq k$, if $v \in X_i \cap X_k$, then $v \in X_j$.
The width of a path decomposition is $\max_{i}|X_i|-1$. The pathwidth $\operatorname{pw}(G)$ of a graph $G$ is the minimum width over all possible path decompositions of $G$.
Our main result is the following.
- $\mathcal{X}$ is a measurement schedule on $\ket{G}$.
- $\mathcal{X}$ is a path decomposition of $G$.
We obtain the following corollary.
This result shows that the spatial cost of a measurement-based quantum computation scales with the pathwidth of the graph.
We show that approximating the spatial cost is NP-hard. Bodlaender et al. showed that the problem of approximating the pathwidth up to an additive error is NP-hard. This gives rise to the following corollary.
While approximating the spatial cost is NP-hard, we show that there is an fixed-parameter tractable algorithm when parameterised by the spatial cost. This follows from results on the fixed-parameter tractability of the pathwidth due to Bodlaender and Fürer. We have the following corollary.
This result implies that an optimal measurement schedule can be efficiently computed for graphs with bounded spatial cost. However, we show that there exists an efficient classical algorithm for simulating measurement-based quantum computation in such cases. Markov and Shi showed that there is an efficient algorithm for simulating a measurement-based quantum computation for graphs with bounded treewidth. We apply their result to obtain the following corollary.