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.

Definition 1 (Measurement sequence) A measurement schedule on a graph state $\ket{G}$ is a sequence of initialising and measuring qubits, such that:

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.

Definition 2 (Path decomposition) A path decomposition of a graph $G=(V, E)$ is a sequence $(X_i)_{i=1}^n$ of subsets of $V$, such that:

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.

Theorem 1 Let $G=(V, E)$ be a graph and let $\mathcal{X}=(X_i)_{i=1}^n$ be a sequence of subsets of $V$. The following statements are equivalent:

$\mathcal{X}$ is a measurement schedule on $\ket{G}$.
$\mathcal{X}$ is a path decomposition of $G$.

We obtain the following corollary.

Corollary 2 Let $G$ be a graph. An optimal measurement schedule on $\ket{G}$ is determined by a path decomposition of $G$ of minimal width, i.e., $\operatorname{sc}(\ket{G})=\operatorname{pw}(G)+1$.

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.

Corollary 3 Let $G=(V, E)$ be a graph. It is NP-hard to approximate $\operatorname{sc}(\ket{G})$ up to an additive error of $|V|^\epsilon$ for $0\lt\epsilon\lt1$.

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.

Corollary 4 Let $G=(V, E)$ be a graph. The spatial cost of $\ket{G}$ and a corresponding measurement schedule can be computed in time $\exp[O\left(\operatorname{sc}(\ket{G})^2\right)]\cdot|V|$.

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.

Corollary 5 Let $G=(V, E)$ be a graph. A measurement-based quantum computation on the graph state $\ket{G}$ can be simulated by a randomised algorithm in time $\exp[O\left(\operatorname{sc}(\ket{G})\right)]\cdot|V|^{O(1)}$.

Ryan Mann

Optimal Scheduling of Graph States via Path Decompositions

About

Profiles

Recent Papers

Collaborators

Interesting Blogs

Useful Tools