# QUANTUM-INSPIRED TENSOR NETWORK FOR EARTH SCIENCE

###### Abstract

Deep Learning (DL) is one of many successful methodologies to extract
informative patterns and insights from ever increasing noisy large-scale
datasets (in our case, satellite images). However, DL models consist of a few
thousand to millions of training parameters, and these training parameters
require tremendous amount of electrical power for extracting informative
patterns from noisy large-scale datasets (e.g., computationally expensive).
Hence, we employ a quantum-inspired tensor network for compressing trainable
parameters of physics-informed neural networks (PINNs) in Earth science. PINNs
are DL models penalized by enforcing the law of physics; in particular, the
law of physics is embedded in DL models. In addition, we apply tensor
decomposition to HyperSpectral Images (HSIs) to improve their spectral
resolution. A quantum-inspired tensor network is also the native formulation
to efficiently represent and train quantum machine learning models on big
datasets on GPU tensor cores. Furthermore, the key contribution of this paper
is twofold: (I) we reduced a number of trainable parameters of PINNs by using
a quantum-inspired tensor network, and (II) we improved the spectral
resolution of remotely-sensed images by employing tensor decomposition. As a
benchmark PDE, we solved Burger’s equation. As practical satellite data, we
employed HSIs of Indian Pine, USA and of Pavia University, Italy.

Index Terms—  Tensor decomposition, quantum-inspired tensor decomposition,
quantum-inspired machine learning.

##  1 introduction

Deep Learning (DL) is a machinery for extracting most informative patterns,
insights from large-scale data, and apply this knowledge to make predictions
[1]. DL models currently have been outperforming conventional techniques and
methods in science and engineering, even in remote sensing and Earth science
[2, 3, 4]. However, DL models compose of a huge number of parameters, making
their interpretation and predictions on large-scale data difficult. Their
energy requirements also extremely limit their scalability (or computationally
expensive) [5]. Hence, the authors of the articles [6, 7, 8] utilized a
quantum-inspired tensor network to compress the parameters (e.g., hidden
layers) of DL models and to decompose data tensors in very small factor
matrices. Here, tensors are multidimensional arrays which can generalize
vectors and matrices. A quantum-inspired tensor network can compress the
training parameters of DL models and decompose data tensors in a small number
of factor matrices. It is also widely used to represent quantum Machine
Learning models as tensor-networks, which can be efficiently trained on big
real-world datasets on GPU tensor cores [9].

Physics-Informed Neural Networks (PINNs) are DL models (e.g., Neural
Networks), whose training parameters are penalized by enforcing the law of
physics [10]; namely, the law of physics is embedded in Neural Networks (NNs).
Moreover, PINNs can be utilized to compute and analyse computationally
expensive Partial Differential Equations (PDEs) when data is of limited
quantity and quality [11]. However, PINNs are still computationally expensive
for obtaining solutions to PDEs in Earth science.

Remotely-sensed datasets are data tensors
$\mathcal{X}\in\mathbb{R}^{I_{1}\times\dots\times I_{n}}$ which are so complex
and diverse that they cannot be easily classified and analyzed even by using
DL models. In particular, these datasets are characterized by not only volume
but also another so-called “4V” features (Volume, Variety, Veracity, and
Velocity) [12].

Fig. 1: Satellite datasets: [Left] HSIs of Indian Pine, USA and [Right] of
Pavia University, Italy

The key contribution of this paper is twofold: The first contribution of this
paper is that we reduced a number of trainable parameters of DL models (i.e.
PINNs) by using the quantum-inspired tensor network. The compressed DL models
can be also applied to analyse and classify big real-world datasets as shown
in the article [7]. The second contribution of this paper is that we improved
the spectral resolution of remotely-sensed images by employing tensor
decomposition. As practical satellite data, we employed HSIs of Indian Pine,
USA and of Pavia University, Italy. As a PDE, we considered Burger’s equation.

##  2 our datasets

We use practical satellite datasets and refer them as 3rd-order data tensors.
In particular, the HSI of Indian Pine is the data tensor
$\mathbb{R}^{240\times 240\times 200}$ with 16 classes, and the HSI of Pavia
University is the data tensor $\mathbb{R}^{610\times 340\times 103}$ with 9
classes (see Fig. 1).

Fig. 2: The two contributions of this paper in pictorial representation: [Top]
Quantum-inspired tensor network (decomposition) for improving spectral
resolution of real-world noisy data tensor, and [Bottom] Quantum-inspired
tensor network for compressing Physics-Informed Neural Networks, which can be
efficiently simulated on GPU tensor cores.

##  3 our methodology

Remotely sensed images can be viewed as 3rd-order data tensors
$\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}}$. The 3rd-order data
tensors can be decomposed in factor matrices by using so-called
CANDECOMP/PARAFAC (CP)-decomposition [6]:

$\mathcal{X}=\sum_{r=1}^{R}\mathbf{a}_{r}\circ\mathbf{b}_{r}\circ\mathbf{c}_{r},$
(1)

where $R$, called the rank, is a real positive number, “$\circ$” denotes an
outer product, and $\mathbf{a}_{r}\in\mathbb{R}^{I_{1}}$,
$\mathbf{b}_{r}\in\mathbb{R}^{I_{2}}$, and
$\mathbf{c}_{r}\in\mathbb{R}^{I_{3}}$ are factor matrices (see Fig. 2 [Top]).

Another commonly used quantum-inspired tensor network is Tensor Train
(TT)-decomposition, called also Matrix Product State (MPS) in quantum physics
[13]. TT-decomposition expresses a 3rd-order tensor as core tensors and factor
matrices:

$\mathcal{X}=\mathbf{A}\times_{3}^{1}\mathbf{G}^{(2)}\times_{3}^{1}\mathbf{B},$
(2)

where $\mathbf{G}^{(2)}\in\mathbb{R}^{R_{1}\times I_{2}\times R_{2}}$ is a
core tensor, $\mathbf{A}$ and $\mathbf{B}$ are factor matrices, and
$\times_{3}^{1}$ is called a mode-(k,l) product .

TT-decomposition can compress DL models, and the compressed DL models can
generate classes with the similar accuracy as their non-compressed ones [7]
(see Fig. 2 [Bottom]). In addition, TT-decomposition is widely employed to
efficiently simulate quantum circuits on conventional computers. Hence, TT-
decomposition have been applying to design and train quantum-inspired machine
learning models on large-scale datasets on GPU tensor cores [14, 15, 16].

Fig. 3: A solution to Burger’s equation (blue is an exact solution, and red is
a predicted solution): [Top] The original PINN, and [Bottom] The compressed
PINN

##  4 our experiment

###  4.1 Contribution I: compressing PINNs

We represented a solution $u=u(t,x)$ to 1D Burger’s equation by an NN [10]. In
mathematical form, 1D Burger’s equation is

$\begin{split}&u_{t}+uu_{x}-(0.01/\pi)u_{xx}=0,\quad t\in[0,1],\\\
&u(0,x)=-\sin(\pi x),\\\ &u(t,-1)=u(t,1)=0.\end{split}$ (3)

When we used the NN with $8$ hidden layers, and each layer comprises $100$
neurons, its trainable parameters are amounted to $71,101$ parameters. We
reduced these $71,101$ parameters to $32,701$ parameters by compressing the
odd numbers of the hidden layers by utilizing the TT-decomposition (see Fig. 2
[Bottom]) [7]. We found a solution $u$ to the Burger’s equation while
utilizing both the original and compressed PINNs. Furthermore, the compressed
PINN generated a solution to the Burger’s equation with high accuracy such as
having been produced by its original PINN, while it occupies a smaller
parameter space than its original one (see Fig. 3). More importantly, the
compressed NNs can be also utilized to analyse and classify any real-world
datasets as shown in the article [7, 17].

Fig. 4: Two examples of HSIs before and after tensor decomposition: [Top] The
band 74 of the Indian Pine HSI before and after tensor decomposition, and
[Bottom] The band 1 of the Pavia University HSI before and after tensor
decomposition.

###  4.2 Contribution II: decomposing real-world data tensors in factor
matrices

We decompose two practical HSIs shown in Fig. 1 in a very small number of
factor matrices by using CP-decomposition expressed by Eq. (1) to improve
their spectral resolution; we illustrate our method for decomposing these HSIs
in Fig. 2 [Top]. In our experiment, we set the rank $R$ of the CP-
decomposition at 145. For the Indian Pine HSI, the decomposition time was
$0.1711$ seconds, the compression ratio was $60$, and the R-squared value
between the raw and the decomposed Indian Pine HSI was $0.9959$. For the Pavia
University HSI, the decomposition time was $1.1013$ seconds, the compression
ratio was $140$, and the R-squared value between the raw and the decomposed
Pavia University HSI was $0.9450$. From these results, we gained the insight
that we improved the spectral resolution of the HSIs, and the HSIs can be
stored efficiently in conventional storage devices at the same time, while
applying tensor decomposition to the practical HSIs. We presented some visual
examples of our finding in Fig. 4.

##  5 conclusion

This paper focused on designing and applying a quantum-inspired tensor-network
to DL models and real-world data tensors. Our contribution is twofold: (I) We
reduced the parameters of a DL model when compressing them by using TT-
decomposition. As a DL model, we utilized a physics-informed neural network
for finding a solution to 1D Burger’s equation. The compressed model generates
solutions to 1D Burger’s equation with high accuracy such as having produced
by its original one. (II) We improved the spectral resolution of hyperspectral
images (i.e. data tensors) by decomposing them in sparse factor matrices
through CP-decomposition. The decomposed data tensors are represented by
sparse tensors, while the decomposition time was extremely small (around 1
second). Additionally, we can store these decomposed images (i.e. sparse
tensors) efficiently and securely in distributed storage devices thanks to
their sparse factor matrices. As practical HSIs, we used HSIs of Indian Pine,
USA and of Pavia University, Italy.

As a future and on-going work, we invent and design quantum-inspired machine
learning models for data-driven and model-driven practical problems. In
addition, we invent and analyse DL models supported by quantum tensor networks
[14, 15, 11, 16].

## References

  * [1] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton,  “Deep learning,”  Nature, vol. 521, no. 7553, pp. 436–444, May 2015.
  * [2] Kamal Choudhary, Brian DeCost, Chi Chen, Anubhav Jain, Francesca Tavazza, Ryan Cohn, Cheol Woo Park, Alok Choudhary, Ankit Agrawal, Simon J. L. Billinge, Elizabeth Holm, Shyue Ping Ong, and Chris Wolverton,  “Recent advances and applications of deep learning methods in materials science,”  npj Computational Materials, vol. 8, no. 1, pp. 59, Apr 2022.
  * [3] G. Cheng, X. Xie, J. Han, L. Guo, and G. S. Xia,  “Remote sensing image scene classification meets deep learning: Challenges, methods, benchmarks, and opportunities,”  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 13, pp. 3735–3756, 2020.
  * [4] Dimitrios Marmanis, Mihai Datcu, Thomas Esch, and Uwe Stilla,  “Deep learning earth observation classification using imagenet pretrained networks,”  IEEE Geoscience and Remote Sensing Letters, vol. 13, no. 1, pp. 105–109, 2016.
  * [5] David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean,  “Carbon emissions and large neural network training,” 2021.
  * [6] Andrzej Cichocki,  “Era of big data processing: A new approach via tensor networks and tensor decompositions,”  CoRR, vol. abs/1403.2048, 2014.
  * [7] Ze-Feng Gao, Song Cheng, Rong-Qiang He, Z. Y. Xie, Hui-Hai Zhao, Zhong-Yi Lu, and Tao Xiang,  “Compressing deep neural networks by matrix product operators,”  Phys. Rev. Res., vol. 2, pp. 023300, Jun 2020.
  * [8] Jiaqi Gu, Ben Keller, Jean Kossaifi, Anima Anandkumar, Brucek Khailany, and David Z. Pan,  “Heat: Hardware-efficient automatic tensor decomposition for transformer compression,” 2022.
  * [9] Hao Huang, Xiao-Yang Liu, Weiqin Tong, Tao Zhang, Anwar Walid, and Xiaodong Wang,  “High performance hierarchical tucker tensor learning using gpu tensor cores,”  IEEE Transactions on Computers, pp. 1–1, 2022.
  * [10] M. Raissi, P. Perdikaris, and G.E. Karniadakis,  “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations,”  Journal of Computational Physics, vol. 378, pp. 686–707, 2019.
  * [11] George Em Karniadakis, Ioannis G. Kevrekidis, Lu Lu, Paris Perdikaris, Sifan Wang, and Liu Yang,  “Physics-informed machine learning,”  Nature Reviews Physics, vol. 3, no. 6, pp. 422–440, Jun 2021.
  * [12] Markus Reichstein, Gustau Camps-Valls, Bjorn Stevens, Martin Jung, Joachim Denzler, Nuno Carvalhais, and Prabhat,  “Deep learning and process understanding for data-driven earth system science,”  Nature, vol. 566, no. 7743, pp. 195–204, Feb 2019.
  * [13] Chase Roberts, Ashley Milsted, Martin Ganahl, Adam Zalcman, Bruce Fontaine, Yijian Zou, Jack Hidary, Guifre Vidal, and Stefan Leichenauer,  “TensorNetwork: A Library for Physics and Machine Learning,” 2019.
  * [14] E Miles Stoudenmire,  “Learning relevant features of data with multi-scale tensor networks,”  Quantum Science and Technology, vol. 3, no. 3, pp. 034003, apr 2018\.
  * [15] William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and E Miles Stoudenmire,  “Towards quantum machine learning with tensor networks,”  Quantum Science and Technology, vol. 4, no. 2, pp. 024001, jan 2019\.
  * [16] Ivan Glasser, Nicola Pancotti, and J. Ignacio Cirac,  “From probabilistic graphical models to generalized tensor networks for supervised learning,”  IEEE Access, vol. 8, pp. 68169–68182, 2020.
  * [17] Xun Gao, Eric R. Anschuetz, Sheng-Tao Wang, J. Ignacio Cirac, and Mikhail D. Lukin,  “Enhancing generative models via quantum correlations,”  Phys. Rev. X, vol. 12, pp. 021037, May 2022.


# Splittings for symbolic powers of edge ideals of complete graphs

Susan M. Cooper  Department of Mathematics
University of Manitoba
520 Machray Hall
186 Dysart Road
Winnipeg, MB
Canada R3T 2N2<EMAIL_ADDRESS>,  Sergio Da Silva  Department of
Mathematics and Economics
Virginia State University
1 Hayden Drive
Petersburg, VA
USA 23806<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Max Gutkin  Department of
Mathematics
University of Manitoba
420 Machray Hall
186 Dysart Road
Winnipeg, MB
Canada R3T 2N2<EMAIL_ADDRESS>and  Tessa Reimer  Department of
Statistics
University of Manitoba
330 Machray Hall
186 Dysart Road
Winnipeg, MB
Canada R3T 2N2<EMAIL_ADDRESS>
###### Abstract.

In this paper we study the $s$-th symbolic powers of the edge ideals of
complete graphs. In particular, we provide a criterion for finding an Eliahou-
Kervaire splitting on these ideals, and use the splitting to provide a
description for the graded Betti numbers. We also discuss the symbolic powers
and graded Betti numbers of edge ideals of parallelizations of finite simple
graphs.

###### Key words and phrases:

Betti numbers, Splittings, Symbolic powers, Edge ideals

###### 2010 Mathematics Subject Classification:

13D02; 13F55

Cooper was supported by the Natural Sciences and Engineering Research Council
of Canada (NSERC). Da Silva was supported in part by a PIMS postdoctoral
fellowship at the University of Manitoba and an NSERC Postdoctoral Fellowship
at McMaster University. Gutkin was supported by a University of Manitoba
Undergraduate Research Award and Reimer was supported by a University of
Manitoba Student Union (UMSU) Undergraduate Research Award.

##  1\. Introduction

Edge ideals of finite simple graphs provide a rich collection of ideals for
which many aspects of commutative algebra can be reduced to a combinatorial
description (see [Adam13]). For example, a primary decomposition of the edge
ideal can be described using the facets of a simplicial complex via Stanley-
Reisner theory. Graph-theoretic concepts such as graph colourings and vertex
covers are also frequently used. It is natural to generalize this theory to
other ideals which have similar combinatorial descriptions. Working with
powers of square-free monomial ideals is one such direction (see [Herzog-Hibi]
for example).

Another natural extension of this viewpoint is to consider symbolic powers of
edge ideals of graphs. This would serve a two-fold purpose of retaining some
of the combinatorics enjoyed by edge ideals while also shedding light on
properties of symbolic powers. Indeed, symbolic powers have played a central
role in many problems, yet their invariants are quite challenging to determine
even when restricted to the family of square-free monomial ideals. The
Waldschmidt constant and resurgence number for certain cases were studied in
[GHOS18], and questions about the symbolic Rees algebra were considered in
[Bahiano04]. In this article we study the graded Betti numbers for symbolic
powers of edge ideals. In particular, with a focus on complete graphs, we
highlight the fruitfulness of using Eliahou-Kervaire splittings as a way to
obtain information about the graded Betti numbers of a symbolic power of an
ideal.

The symbolic power of a monomial ideal $I$ has a convenient description in
terms of its primary decomposition, and is easier to describe compared to more
general homogeneous ideals. Let $I\subset R=k[x_{1},\ldots,x_{m}]$ be a
monomial ideal, where $k$ is a field. Suppose that $I=I_{1}\cap\dots\cap
I_{r}$ is a primary decomposition for $I$. Given a maximal associated prime
ideal $Q$ of $I$ and a positive integer $s$, we define

$I_{\subseteq Q}=\bigcap_{\sqrt{I_{\ell}}\subseteq Q}I_{\ell}$

so that the $s$-th symbolic power of $I$ is

$I^{(s)}=\bigcap_{Q\in\mathrm{maxAss}(I)}I_{\subseteq Q}^{s},$

where $\sqrt{I_{\ell}}=\\{r\in R\mid r^{n}\in I_{\ell}\,\,\,\text{for some
positive integer $n$}\\}$ denotes the radical of $I_{\ell}$ and
$\mathrm{maxAss}(I)$ denotes the set of associated primes of $I$ that are
maximal with respect to inclusion.

This definition doesn’t depend on the primary decomposition since
$I_{\subseteq Q}=R\cap IR_{Q}$ (see [CEHH]). In Sections 3 and 4 we provide a
description of the minimal monomial generating set for $I(G)^{(s)}$ when $G$
is a complete graph or a parallelization of a finite simple graph. These
descriptions are necessary to study Eliahou-Kervaire splittings for symbolic
powers of edge ideals, which in turn allow us to compute graded Betti numbers
recursively. Theorem 3.5 provides a criterion for defining an Eliahou-Kervaire
splitting in this context. A similar technique is employed for a specific
family of monomial ideals found in [Valla05].

Having a method to determine the graded Betti numbers of symbolic powers of
edge ideals allows one to readily obtain information of related invariants of
interest. We demonstrate this for the minimum socle degree in Section 3.4. It
is known that symbolic powers of edge ideals of complete graphs are Cohen-
Macaulay and have dimension 1 (see Lemma 3.15 for the relevant citations).
Projectively these are fat points, and this implies that Section 3 is studying
zero-dimensional arithmetically Cohen-Macaulay schemes, which complements the
content found in [Tohaneanu-VanTuyl].

Finally, a discussion about the graded Betti numbers for graph
parallelizations of finite simple graphs can be found in Section 4. The
definition of a graph parallelization is given there, but the utility of this
construction comes from the ability to define families of graphs with
properties that are related to the original graph (which can be useful for
finding examples or counter-examples).

The arguments in this article work over any field $k$. While there exist some
subtleties when working over fields of positive characteristic (for instance,
[FHV08, Example 4.2] illustrates a Betti splitting which fails to be a
splitting except in characteristic 2), our arguments rely on a particular
splitting map which is characteristic-free.

##  2\. Preliminaries

There is a rich theory involving edge ideals and their combinatorial
properties. We refer the reader to [Adam13] for a thorough overview of this
theory. Throughout the paper, $G$ will denote an undirected finite simple
graph with vertex set $V(G)=\\{x_{1},\ldots,x_{m}\\}$ and edge set $E(G)$.
Recall that $G$ is simple if it does not have multiple edges between vertices
and if it does not have any loops at vertices. Let $k$ be a field and
$R=k[x_{1},\ldots,x_{m}]$. The edge ideal of $G$ is defined as the square-free
monomial ideal $I(G)=\langle x_{i}x_{j}:\\{x_{i},x_{j}\\}\in
E(G)\rangle\subset R$.

We mainly focus on complete graphs in this paper. Recall that the complete
graph on $m$ vertices, denoted $K_{m}$, is the simple undirected graph for
which every pair of distinct vertices is connected by exactly one unique edge.

In the sections that follow, we will also consider subgraphs of graphs. An
induced subgraph $H$ of $G$ is a graph with vertex set $V(H)\subseteq V(G)$
and edge set $E(H)=E(G)\cap[V(H)]^{2}$. That is, if $u,v\in V(H)$, then $u$
and $v$ are adjacent in $H$ if and only if they are adjacent in $G$. For
example, the complete graph $K_{3}$ is an induced subgraph of $K_{4}$, whereas
the subgraph with 4 vertices but no edges is not.

Determining invariants of symbolic powers of homogeneous ideals in the
polynomial ring can be quite challenging. Recall from the introduction that we
can define the $s$-th symbolic power of a monomial ideal $I$ in terms of a
primary decomposition of $I$. When $I$ is the edge ideal of a graph $G$, this
becomes tractable via vertex covers of $G$. A subset $W\subseteq V(G)$ is said
to be a vertex cover if $W\cap e\neq\emptyset$ for all $e\in E(G)$. A vertex
cover $W$ is a minimal vertex cover if no proper subset of $W$ is a vertex
cover of $G$. We have the following useful connection between vertex covers
and $I(G)$.

######  Lemma 2.1 ([Adam13, Theorem 1.34, Corollary 1.35]).

Let $W_{1},\ldots,W_{t}$ be the minimal vertex covers of a graph $G$. If we
set $\langle W_{i}\rangle=\langle x_{j}\mid x_{j}\in W_{i}\rangle$, then
$I(G)=\langle W_{1}\rangle\cap\cdots\cap\langle W_{t}\rangle$ is the minimal
primary decomposition of $I(G)$.

One of the main goals of this paper is to investigate the use of a splitting
technique due to Eliahou and Kervaire (in particular, a splitting for the
symbolic powers of $I(G)$) to reduce the determination of graded Betti numbers
to an induction on much simpler base cases. We denote the set of minimal
monomial generators of a monomial ideal $I\subset R$ (which are unique) by
$\mathcal{G}(I)$, and recall the following definition from [FHV08].

######  Definition 2.2.

Let $I,J$ and $K$ be monomial ideals of $R=k[x_{1},\ldots,x_{m}]$ such that
$\mathcal{G}(I)$ is the disjoint union of $\mathcal{G}(J)$, $\mathcal{G}(K)$.
We call $I=J+K$ an Eliahou-Kervaire splitting (or E-K splitting) if there
exists a splitting function $\mathcal{G}(J\cap
K)\longrightarrow\mathcal{G}(J)\times\mathcal{G}(K)$ sending
$w\mapsto(\phi(w),\varphi(w))$ such that:

  1. (1)

$w=\mathrm{lcm}(\phi(w),\varphi(w))$; and

  2. (2)

for every subset $S\subset\mathcal{G}(J\cap K)$, both $\mathrm{lcm}(\phi(S))$
and $\mathrm{lcm}(\varphi(S))$ strictly divide $\mathrm{lcm}(S)$.

One benefit of having an Eliahou-Kervaire splitting is the ability to compute
the graded Betti numbers of $I$ in terms of the graded Betti numbers for $J$
and $K$. Recall that the $i,j$-th graded Betti number of $I$ is by definition
$\beta_{i,j}(I)=\dim_{k}\text{Tor}_{i}(k,I)_{j}$. That is, $\beta_{i,j}(I)$ is
the number of copies of $R(-j)$ appearing in the $i$-th module of the graded
minimal free resolution of $I$:

$0\rightarrow\bigoplus_{j}R(-j)^{\beta_{\ell,j}(I)}\rightarrow\cdots\rightarrow\bigoplus_{j}R(-j)^{\beta_{1,j}(I)}\rightarrow\bigoplus_{j}R(-j)^{\beta_{0,j}(I)}\rightarrow
I\rightarrow 0,$

where $R(-j)$ is the polynomial ring $R$ shifted by degree $j$.

######  Lemma 2.3 ([Fatabbi01, Proposition 3.2]).

Let $I,J$ and $K$ be monomial ideals of $k[x_{1},\ldots,x_{m}]$ such that
$I=J+K$ is an Eliahou-Kervaire splitting. Then

$\beta_{i,j}(I)=\beta_{i,j}(J)+\beta_{i,j}(K)+\beta_{i-1,j}(J\cap K),$

for all $i\in\mathbb{N}$ and multidegrees $j$.

######  Remark 2.4.

The original version of this result was proved for total Betti numbers in
[EK90, Proposition 3.1] over an arbitrary field. The proof of Lemma 2.3 is
also valid over any field, even if the author of [Fatabbi01] assumes that the
field is algebraically closed (which is needed later in [Fatabbi01]).

All E-K splittings are examples of Betti splittings, which are a choice of
monomial ideals $I=J+K$ where
$\mathcal{G}(I)=\mathcal{G}(J)\sqcup\mathcal{G}(K)$ which also satisfy the
graded Betti number equality from Lemma 2.3. The distinction will not be
important for us since all of the splittings in the sections that follow are
E-K splittings. See [FHV08] for more information on Betti splittings. We
finish with a simple auxiliary lemma, which we leave as an exercise.

######  Lemma 2.5.

If $I\subset k[x_{1},\ldots,x_{m}]$ is a monomial ideal, then
$\beta_{i,j}(x_{\ell}I)=\beta_{i,j-1}(I)$ for all $i,j\geq 1$, $1\leq\ell\leq
m$.

##  3\. Symbolic Powers Of Edge Ideals Of Complete Graphs

We denote the complete graph on $m$ vertices by $K_{m}$ and label its vertices
by $x_{1},\ldots,x_{m}$. Fix $R=k[x_{1},\ldots,x_{m}]$. Our main goal is to
determine the graded Betti numbers for the symbolic powers of the edge ideal
of $K_{m}$. In order to make use of the Eliahou-Kervaire splitting technique,
we need a convenient description for the minimal monomial generators of
symbolic powers of $I(K_{m})$. The following lemma will simplify this task.

######  Lemma 3.1 ([Wald15, Lemma 2.6]).

Let $I\subset R=k[x_{1},\ldots,x_{m}]$ be a square-free monomial ideal with
minimal primary decomposition $I=P_{1}\cap\hskip 0.7113pt\cdots\hskip
0.7113pt\cap P_{n}$ with $P_{\ell}=\langle
x_{j_{1}},\ldots,x_{j_{\alpha_{\ell}}}\rangle$ for $\ell=1,\ldots,n$. Then
$x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in I^{(s)}$ if and only if
$a_{j_{1}}+\cdots+a_{j_{\alpha_{\ell}}}\geq s$ for $\ell=1,\ldots,n$.

We now determine the minimal monomial generating set
$\mathcal{G}(I(K_{m})^{(s)})$ for the $s$-th symbolic power of
$I(K_{m})\subset R$.

######  Proposition 3.2.

If $I=I(K_{m})\subset R$ and $s\geq 2$, then $I^{(s)}$ has minimal monomial
generating set

$\mathcal{L}:=\\{x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}:\exists\,\,1\leq i\leq
m\,\,\text{with}\,\,\sum_{j\not=i}a_{j}=s,a_{i}=\max_{j\not=i}\\{a_{j}\\}\\}.$

That is, $\mathcal{G}(I^{(s)})=\mathcal{L}$.

###### Proof.

Let $x=x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in\mathcal{L}$ where $a_{i}\geq 0$
for each $1\leq i\leq m$. Without loss of generality, suppose that
$a_{1}+\cdots+a_{m-1}=s$ and $a_{m}=\max\\{a_{1},\ldots,a_{m-1}\\}$. Note that
any choice of $m-1$ vertices of $K_{m}$ defines a minimal vertex cover for
$K_{m}$, and so by Lemma 2.1 we can write $I=\bigcap_{i=1}^{m}\langle
x_{1},\ldots,\hat{x_{i}},\ldots,x_{m}\rangle$, which is the minimal primary
decomposition for $I$. Then, by Lemma 3.1, $x\in I^{(s)}$ since every subset
of $\\{a_{1},\ldots,a_{m}\\}$ of size $m-1$ sums to a value larger than or
equal to $s$.

Conversely, suppose that $x=x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in I^{(s)}$.
Without loss of generality, we may assume that
$a_{m}=\max\\{a_{1},\ldots,a_{m}\\}$ so that $a_{1}+\cdots+a_{m-1}\geq s$ by
Lemma 3.1. Then $x$ is clearly in the ideal $\langle\mathcal{L}\rangle$,
proving that $\mathcal{L}$ is a generating set for $I^{(s)}$.

To see that $\mathcal{L}=\mathcal{G}(I^{(s)})$, suppose $x=x_{1}^{a_{1}}\cdots
x_{m}^{a_{m}}$ and $y=x_{1}^{b_{1}}\cdots x_{m}^{b_{m}}$ are both monomials in
$\mathcal{L}$ such that $x$ divides $y$ (i.e. $b_{t}\geq a_{t}$ for
$t=1,\ldots,m$). Suppose $1\leq i,j\leq m$ are such that

$a_{1}+\cdots+a_{m}-a_{i}=b_{1}+\cdots+b_{m}-b_{j}=s\,\,\text{with}\,\,a_{i}=\max\\{a_{1},\ldots,a_{m}\\},\,\,b_{j}=\max\\{b_{1},\ldots,b_{m}\\}.$

Then $b_{j}\geq b_{i}\geq a_{i}$ and we can write $b_{j}-a_{i}=c\geq 0$. Thus,

$b_{1}+\cdots+b_{m}=s+b_{j}=s+a_{i}+c=a_{1}+\cdots+a_{m}+c.$

Therefore,

$c=\sum_{\ell=1}^{m}(b_{\ell}-a_{\ell})=(b_{j}-a_{i})+(b_{i}-a_{j})+\sum_{\ell\neq
i,j}^{m}(b_{\ell}-a_{\ell})\implies(b_{i}-a_{j})+\sum_{\ell\neq
i,j}^{m}(b_{\ell}-a_{\ell})=0.$

Note that since $a_{i}=\max\\{a_{1},\ldots,a_{m}\\}$, we have that $a_{j}\leq
a_{i}\leq b_{i}$ and so $b_{i}-a_{j}\geq 0$. Then each term in the previous
equation is non-negative showing that $a_{\ell}=b_{\ell}$ for $\ell\neq i,j$
and $b_{i}=a_{j}$. Since $b_{j}=\max\\{b_{1},\ldots,b_{m}\\}$, there must be
some $t\not=j$ such that $b_{t}=b_{j}$ (by the definition of $\mathcal{L}$).
Now if $b_{j}\not=b_{i}$, then $t\not=i$ and $a_{t}=b_{t}=b_{j}>b_{i}\geq
a_{i}=\max\\{a_{1},\ldots,a_{m}\\}$, a contradiction. Thus,
$b_{j}=b_{i}=a_{j}$. We conclude that $x=y$, as required. ∎

###  3.1. E-K Splittings

We are now in a position to use splittings to determine the graded Betti
numbers of symbolic powers of the edge ideal of a complete graph $K_{m}$. As
before, we let $R=k[x_{1},\ldots,x_{m}]$. Observe that if we set $G=K_{m}$ and
fix $0\leq r\leq m$, then we can view $H=K_{r}$ as an induced subgraph of
$K_{m}$ where $V(K_{r})=\\{x_{1},\ldots,x_{r}\\}$ (here $K_{0}$ is the null
subgraph and $I(K_{0})$ is the zero ideal).

######  Definition 3.3.

Let $G=K_{m}$ and $H=K_{r}$ for some fixed $0\leq r\leq m$. If $s\geq 2$ is an
integer and $r\not=m$, then

$I_{H,s}=\langle w\in\mathcal{G}(I(G)^{(s)}):x_{i}\nmid
w,i=r+1,\ldots,m\rangle\,\,\,\text{and}\,\,\,I_{G\setminus
H,s}=I(G)^{(s)}\cap\langle\prod_{j=r+1}^{m}x_{j}\rangle.$

By convention, if $r=m$, then we define $I_{H,s}=I_{G\setminus
H,s}=I(G)^{(s)}$.

In general, if $w=x_{1}^{a_{1}}\cdots
x_{m}^{a_{m}}\in\mathcal{G}(I(K_{m})^{(s)})$, then $w\in\mathcal{G}(I_{H,s})$
if $a_{r+1}=\cdots=a_{m}=0$ and $w\in\mathcal{G}(I_{G\setminus H,s})$ if
$a_{i}\neq 0$ for all $i\in\\{r+1,\ldots,m\\}$. Also, observe that $I_{H,s}$
can be viewed as the extension of $I(H)^{(s)}\subset k[x_{1},\ldots,x_{r}]$ to
the ring $k[x_{1},\ldots,x_{n}]$.

######  Lemma 3.4.

If $m\geq 3,s\geq 2,G=K_{m}$ and $H=K_{m-1}$, then $I_{H,s}\cap I_{G\setminus
H,s}=x_{m}I_{H,s}$.

###### Proof.

Note first that $I_{H,s}$ is an ideal contained in $I(G)^{(s)}$, and so
$I_{H,s}\cap I(G)^{(s)}=I_{H,s}$.
Thus, $I_{H,s}\cap I_{G\setminus H,s}=I_{H,s}\cap I(G)^{(s)}\cap\langle
x_{m}\rangle=I_{H,s}\cap\langle x_{m}\rangle$. Since no generator of $I_{H,s}$
is divisible by $x_{m}$, it is clear that $I_{H,s}\cap\langle
x_{m}\rangle=x_{m}I_{H,s}$. ∎

We now define an E-K splitting for ideals of the form $I_{K_{m}\setminus
K_{r},s}$. The ideal $I(K_{m})^{(s)}$ is a special case, and an E-K splitting
for it will follow as a corollary of the next theorem. These results are
needed as part of the induction for the next section.

######  Theorem 3.5.

Let $m\geq 3,s\geq 2$ and $r\in\\{1,\ldots,m\mid r\not=m-s-1\\}$. If
$G=K_{m},H=K_{r}$,

$L_{1}=\langle w\in\mathcal{G}(I_{G\setminus H,s}):x_{r}\mid
w\rangle=I_{G\setminus H,s}\cap\langle x_{r}\rangle,\,\,\,\text{ and
}\,\,\,L_{2}=\langle w\in\mathcal{G}(I_{G\setminus H,s}):x_{r}\nmid w\rangle,$

then $I_{G\setminus H,s}=L_{1}+L_{2}$ is an Eliahou-Kervaire splitting.

###### Proof.

We first note that the minimal monomial generating set of $L_{2}$ is given by
all monomials $w=x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in\mathcal{G}(I(G)^{(s)})$
such that $a_{r}=0$ and every exponent from $\\{a_{r+1},\dots,a_{m}\\}$ is
nonzero.

To construct a splitting function that sends $w\in\mathcal{G}(L_{1}\cap
L_{2})$ to
$(\phi(w),\varphi(w))\in\mathcal{G}(L_{1})\times\mathcal{G}(L_{2})$, we need
to define two functions, $\varphi:\mathcal{G}(L_{1}\cap
L_{2})\rightarrow\mathcal{G}(L_{2})$ and $\phi:\mathcal{G}(L_{1}\cap
L_{2})\rightarrow\mathcal{G}(L_{1})$. We start with the function $\varphi$.
First notice that by a similar argument to Lemma 3.4, $L_{1}\cap
L_{2}=x_{r}L_{2}$ and each $w\in\mathcal{G}(L_{1}\cap L_{2})$ can be written
uniquely as $w=x_{r}v$, where $v\in\mathcal{G}(L_{2})$. Therefore, we define
$\varphi:\mathcal{G}(L_{1}\cap L_{2})\rightarrow\mathcal{G}(L_{2})$ by
$w=x_{r}v\mapsto v.$

Next we define $\phi:\mathcal{G}(L_{1}\cap
L_{2})\rightarrow\mathcal{G}(L_{1})$. Given $w=x_{r}v\in\mathcal{G}(L_{1}\cap
L_{2})$, let $a_{i}$ denote the exponent of $x_{i}$ in $w$ for $1\leq i\leq
m$. Note that $a_{r}=1$. Let $j\in\\{1,\ldots,m\\}\setminus\\{r\\}$ be the
smallest index such that

$a_{1}+\cdots+a_{m}-a_{r}-a_{j}=s,\hskip 5.69054pt\text{ and }\hskip
5.69054pta_{j}=a_{max}\coloneqq\max(\\{a_{1},\ldots,a_{m}\\}\setminus\\{a_{r},a_{j}\\}).$

Let $t\in\\{1,\ldots,m\\}\setminus\\{j,r\\}$ be the smallest index such that
$a_{t}=a_{max}$. The indices $j$ and $t$ exist by Proposition 3.2. Observe
that $j$ and $t$ are the two smallest indices in
$\\{1,\ldots,m\\}\setminus\\{r\\}$ such that $a_{t}=a_{j}=a_{max}$ and that
$j<t$. Define $\phi:\mathcal{G}(L_{1}\cap L_{2})\rightarrow\mathcal{G}(L_{1})$
by

$w=x_{r}v=x_{1}^{a_{1}}\cdots
x_{m}^{a_{m}}\mapsto\begin{cases}\cfrac{w}{x_{j}}&\text{ if }\exists\hskip
2.56073pt\ell\neq j,t,r\text{ with }a_{\ell}=a_{max},\\\
\cfrac{w}{x_{t}x_{j}}&\text{ otherwise.}\end{cases}$

We need to show that $\phi$ does in fact map into $\mathcal{G}(L_{1})$. If
$a_{t}$ is the only value in
$\\{a_{1},\ldots,a_{m}\\}\setminus\\{a_{j},a_{r}\\}$ such that
$a_{t}=a_{max}$, then let
$A^{\prime}=\\{x_{1},\ldots,x_{m}\\}\setminus\\{x_{t}\\}$ and for each $1\leq
i\leq m$, let $a_{i}^{\prime}$ denote the exponent of $x_{i}$ in $\phi(w)$.
Note that
$a_{j}^{\prime}=a_{j}-1,a_{t}^{\prime}=a_{t}-1,a_{r}^{\prime}=a_{r}=1$ and
$a_{l}^{\prime}=a_{l}$ for all $l\neq j,t$. Then

$\displaystyle\sum_{x_{i}\in
A^{\prime}}a_{i}^{\prime}=\sum_{i=1}^{m}a_{i}^{\prime}-a_{t}^{\prime}=\deg(\phi(w))-(a_{t}-1)$
$\displaystyle=\deg(w)-2-(a_{max}-1)$
$\displaystyle=\sum_{i=1}^{m}a_{i}-1-a_{max}$
$\displaystyle=\sum_{i=1}^{m}a_{i}-a_{r}-a_{j}=s.$

Also,

$a_{max}^{\prime}\coloneqq\max(\\{a_{1}^{\prime},\ldots,a_{m}^{\prime}\\}\setminus\\{a_{t}^{\prime}\\})=a_{j}^{\prime}=a_{max}-1\
\ \text{and}\ \ a_{t}^{\prime}=a_{t}-1=a_{max}-1=a_{max}^{\prime}.$

Thus $\phi(w)\in\mathcal{G}(I(G)^{(s)})$.

To show that $\phi(w)\in\mathcal{G}(I_{G\setminus H,s})$, it suffices to
verify that $\prod_{i=r+1}^{m}x_{i}$ divides $\phi(w)$. To this end, assume
that $\prod_{i=r+1}^{m}x_{i}$ does not divide $\phi(w)$. Recall that
$w=x_{r}v$ for some $v\in\mathcal{G}(L_{2})$. Since
$\mathcal{G}(L_{2})\subset\mathcal{G}(I_{G\setminus H,s})$, we know that
$\prod_{i=r+1}^{m}x_{i}$ divides $v$. Thus, $\prod_{i=r+1}^{m}x_{i}$ divides
$w$. Since $\phi(w)=w/(x_{j}x_{t})$ and $\prod_{i=r+1}^{m}x_{i}$ does not
divide $\phi(w)$, it must be that at least one of $j$ or $t$ is greater than
or equal to $r+1$ and $a_{j}=a_{t}=1$. Since $a_{j}=a_{t}=a_{max}$, this
implies that $w$ is a square-free monomial. Hence,

$\deg(w)=a_{1}+\cdots+a_{m}=s+2$

and so $\phi(w)$ has degree $s$. This is a contradiction since
$\phi(w)\in\mathcal{G}(I(G)^{(s)})$ which consists of monomials of degree
$s+1$ and higher. We conclude that $\prod_{i=r+1}^{m}x_{i}$ divides $\phi(w)$,
and thus $\phi(w)\in\mathcal{G}(I_{G\setminus H,s})$. Furthermore, since
$x_{r}\mid\phi(w)$, we cannot have $\phi(w)\in\mathcal{G}(L_{2})$. Thus,
$\phi(w)\in\mathcal{G}(L_{1})$.

Similarly, if $a_{t}$ is not the only value in
$\\{a_{1},\ldots,a_{m}\\}\setminus\\{a_{j},a_{r}\\}$ such that
$a_{t}=a_{max}$, then define $A^{\prime}$ and each $a_{i}^{\prime}$ as before.
Note that $a_{j}^{\prime}=a_{j}-1,a_{r}=a_{r}^{\prime}=1$ and
$a_{l}^{\prime}=a_{l}$ for all $l\neq j$. Then

$\sum_{x_{i}\in
A^{\prime}}a_{i}^{\prime}=\sum_{i=1}^{m}a_{i}^{\prime}-a_{t}^{\prime}=\deg(\phi(w))-a_{t}=\deg(w)-1-a_{max}=\sum_{i=1}^{m}a_{i}-a_{r}-a_{j}=s.$

Also,

$a_{max}^{\prime}\coloneqq\max(\\{a_{1}^{\prime},\ldots,a_{m}^{\prime}\\}\setminus\\{a_{t}^{\prime}\\})=a_{max}\
\ \ \text{and}\ \ \ a_{t}^{\prime}=a_{t}=a_{max}=a_{max}^{\prime}.$

Thus, $\phi(w)\in\mathcal{G}(I(G)^{(s)})$.

We need to show that $\phi(w)=w/x_{j}\in\mathcal{G}(I_{G\setminus H,s})$.
Again, it suffices to verify that $\prod_{i=r+1}^{m}x_{i}$ divides $\phi(w)$.
Arguing by contradiction, suppose that $\prod_{i=r+1}^{m}x_{i}$ does not
divide $\phi(w)$. As above, $w=x_{r}v$ for some $v\in\mathcal{G}(L_{2})$ and
$\prod_{i=r+1}^{m}x_{i}$ divides $v$ and hence $w$. Since $\phi(w)=w/x_{j}$,
it follows that $j\geq r+1$ and $a_{j}=1$. Thus, since $t>j$ and
$a_{t}=a_{max}=a_{j}$, we have $t>r+1$ and $1=a_{t}=a_{j}=a_{max}$. This
implies that $w$ is a square-free monomial. Further, since the exponents in
$\phi(w)$ of the variables in $A^{\prime}$ sum to $s$ and
$a_{t}^{\prime}=a_{t}=1$, $\deg(\phi(w))=s+1$. By the choice of $j$ and $t$,
this implies that for all $1\leq i<r$ we have $a_{i}\not=a_{max}$. Since $w$
is square-free, we must have $a_{i}=0$ for $1\leq i<r$. But then $w$ is
square-free and divisible by $x_{r}$ and $\prod_{i=r+1}^{m}x_{i}$, and so
$w=\prod_{i=r}^{m}x_{i}$. Thus $\deg(\phi(w))=(m-r+1)-1=m-r$, and so

$m-r=s+1\implies m-s-1=r,$

a contradiction to the assumption that $m-s-1\not=r$. We conclude that
$\prod_{i=r+1}^{m}x_{i}$ divides $\phi(w)$, and so
$\phi(w)\in\mathcal{G}(I_{G\setminus H,s})$. Again, since $x_{r}\mid\phi(w)$,
we have that $\phi(w)$ is not in $\mathcal{G}(L_{2})$ and thus
$\phi(w)\in\mathcal{G}(L_{1})$.

We now show that these maps define an E-K splitting. It is easy to verify the
first condition by checking that $\mathrm{lcm}(\phi(w),\varphi(w))=w$ when
$w\in\mathcal{G}(L_{1}\cap L_{2})$. To check the second condition, we need to
verify that for every subset $S\subset\mathcal{G}(J\cap K)$, both
$\mathrm{lcm}(\phi(S))$ and $\mathrm{lcm}(\varphi(S))$ strictly divide
$\mathrm{lcm}(S)$. To this end, let $S\subset\mathcal{G}(L_{1}\cap L_{2})$.
Clearly, $\mathrm{lcm}(\phi(S))$ and $\mathrm{lcm}(\varphi(S))$ both divide
$\mathrm{lcm}(S)$. Since $x_{r}\mid\mathrm{lcm}(S)$ and
$x_{r}\nmid\mathrm{lcm}(\varphi(S))$, we cannot have
$\mathrm{lcm}(\varphi(S))=\mathrm{lcm}(S)$, so $\mathrm{lcm}(\varphi(S))$
strictly divides $\mathrm{lcm}(S)$, as required.

To show $\mathrm{lcm}(\phi(S))\neq\mathrm{lcm}(S)$, let $a$ be the maximum
exponent of any variable in any monomial in $S$. Let $i_{0}$ be the smallest
index such that $x_{i_{0}}^{a}$ divides at least one $w\in S$. By definition
of $\phi$, $x_{i_{0}}^{a}\nmid\phi(w)$. If there exists any $w^{\prime}\in S$
such that $x_{i_{0}}^{a}\mid\phi(w^{\prime})$, then either there exists an
exponent in $w^{\prime}$ that is larger than $a$, or there exists an index
$i_{1}<i_{0}$ such that $x_{i_{1}}^{a}\mid w^{\prime}$. Both are clear
contradictions. Thus, $x_{i_{0}}^{a}\nmid\mathrm{lcm}(\phi(S))$, yet it
clearly divides $\mathrm{lcm}(S)$, showing that
$\mathrm{lcm}(\phi(S))\neq\mathrm{lcm}(S)$ and completing the proof. ∎

######  Example 3.6.

The assumption that $r\not=m-s-1$ is necessary in Theorem 3.5. For example,
consider $m=5,s=2$ and $r=2$. By definition,
$x_{3}x_{4}x_{5}\in\mathcal{G}(L_{2})$, and so
$w=x_{2}x_{3}x_{4}x_{5}\in\mathcal{G}(L_{1}\cap L_{2})$. Here, $a_{max}=1$.
The smallest index $j\in\\{1,\ldots,5\\}\setminus\\{2\\}$ such that
$a_{j}=a_{max}$ is 3. The smallest index
$t\in\\{1,\ldots,5\\}\setminus\\{2,3\\}$ such that $a_{t}=a_{max}$ is 4. Note
that $a_{5}=a_{max}$ and $5\not=j,t,r$. Thus,
$w/x_{j}=w/x_{3}=x_{2}x_{4}x_{5}$ is not in $\mathcal{G}(I_{G\setminus H,s})$
as it is not divisible by $x_{3}x_{4}x_{5}$.

######  Corollary 3.7.

If $m\geq 3,s\geq 2,G=K_{m}$ and $H=K_{m-1}$, then
$I(G)^{(s)}=I_{H,s}+I_{G\setminus H,s}$ is an E-K splitting.

###### Proof.

By definition, $I(K_{m})=I(G)^{(s)}=I_{K_{m}\setminus K_{m},s}$. Therefore, by
Theorem 3.5 with $r=m$, we have that $I_{K_{m}/K_{m},s}=L_{1}+L_{2}$ is an E-K
splitting where

$L_{1}=I_{K_{m}\setminus K_{m},s}\cap\langle x_{m}\rangle=I_{K_{m}\setminus
K_{m-1},s}\ \ \text{and}\ \ L_{2}=I_{K_{m-1}\setminus
K_{m-1},s}=I(K_{m-1})^{(s)}=I_{K_{m-1},s}.$

∎

######  Remark 3.8.

With these results, if $m-s-1<0$, then we may repeatedly apply the splitting
defined in Theorem 3.5 to define a function that gives the graded Betti
numbers of $I(G)^{(s)}$. In fact, it is an important observation that $L_{1}$
from Theorem 3.5 is actually of the form $I_{K_{m}\setminus K_{r-1},s}$, since
$I_{K_{m}\setminus K_{r-1},s}=I_{K_{m}\setminus K_{r},s}\cap\langle
x_{r}\rangle$, which allows the theorem to be iteratively applied to each
subsequent $L_{1}$. Each step of this iteration applies Theorem 3.5 to
$I_{K_{m}\setminus K_{r},s}$ for decreasing $r$, and terminates with
$I_{K_{m}\setminus K_{0},s}$.

###  3.2. Graded Betti Numbers Of Symbolic Powers Of $I(K_{2})$ and $I(K_{3})$

We now use splittings and induction to determine the graded Betti numbers for
the $s$-th symbolic powers of the edge ideal of $K_{3}$. We begin with the
following observation.

######  Lemma 3.9.

If $I=I(K_{2})\subset R=k[x_{1},x_{2}]$ and $s\geq 2$, then
$\beta_{1,2s}(I_{K_{2},s})=1$ and $\beta_{i,j}(I_{K_{2},s})=0$ for
$i\not=1,j\not=2s$.

###### Proof.

Notice that $I^{(s)}=\langle x_{1}^{s}x_{2}^{s}\rangle=I^{s}$. It is
straightforward to see that a minimal graded free resolution of $I^{(s)}$
(over any field $k$) is given by $0\rightarrow R(-2s)\rightarrow R\rightarrow
R/I^{(s)}\rightarrow 0$. ∎

######  Theorem 3.10.

If $i,j\in\mathbb{Z}^{+}$ and $s\geq 1$, then we have:

$\beta_{1,\frac{3s}{2}}(I(K_{3})^{(s)})=1;\,\,\,\beta_{2,\frac{3s+3}{2}}(I(K_{3})^{(s)})=2;\,\,\,\beta_{1,j}(I(K_{3})^{(s)})=3\,\,\,\,\text{if
$\frac{3s+1}{2}\leq j\leq 2s$};$
$\beta_{2,j}(I(K_{3})^{(s)})=3\,\,\,\,\text{if $\frac{3s+4}{2}\leq j\leq
2s+1$};\,\,\,\text{and}\,\,\,\,\beta_{i,j}(I(K_{3})^{(s)})=0\,\,\,\,\text{otherwise}.$

###### Proof.

We induct on $s$. The result is clear for $s=1$ and $s=2$ via a computation
using Macaulay2. Fix $s>2$ and suppose the function holds for all positive
integers $s^{\prime}<s$. By Corollary 3.7, there is an E-K splitting of
$I(K_{3})^{(s)}=I_{K_{2},s}+I_{K_{3}\setminus K_{2},s}$, and by Lemma 2.3 we
can write

$\beta_{i,j}(I(K_{3})^{(s)})=\beta_{i,j}(I_{K_{2},s})+\beta_{i,j}(I_{K_{3}\setminus
K_{2},s})+\beta_{i-1,j}(I_{K_{2},s}\cap I_{K_{3}\setminus K_{2},s}).$

Using Lemma 3.4, we know that $I_{K_{2},s}\cap I_{K_{3}\setminus
K_{2},s}=x_{3}I_{K_{2},s}$, and by Lemma 2.5,
$\beta_{i-1,j}(x_{3}I_{K_{2},s})=\beta_{i-1,j-1}(I_{K_{2},s})$. Therefore,

$\beta_{i,j}(I(K_{3})^{(s)})=\beta_{i,j}(I_{K_{2},s})+\beta_{i,j}(I_{K_{3}\setminus
K_{2},s})+\beta_{i-1,j-1}(I_{K_{2},s}).$

We now write $\beta_{i,j}(I_{K_{3}\setminus K_{2},s})$ in terms of the known
graded Betti numbers coming from the induction. Let $L_{1}$ and $L_{2}$ be as
in Theorem 3.5 with $m=3$ and $r=2$. Then $I_{K_{3}\setminus
K_{2},s}=L_{1}+L_{2}$ is an E-K splitting, and therefore

$\beta_{i,j}(I_{K_{3}\setminus
K_{2},s})=\beta_{i,j}(L_{1})+\beta_{i,j}(L_{2})+\beta_{i-1,j}(L_{1}\cap
L_{2}).$

From the proof of Theorem 3.5, $L_{1}\cap L_{2}=x_{2}L_{2}$ so that
$\beta_{i-1,j}(L_{1}\cap L_{2})=\beta_{i-1,j-1}(L_{2})$. By a change of
coordinates, we have that $\beta_{i,j}(L_{2})=\beta_{i,j}(I_{K_{2}\setminus
K_{1},s})=\beta_{i,j}(I_{K_{2},s})$. Therefore

$\beta_{i,j}(I_{K_{3}\setminus
K_{2},s})=\beta_{i,j}(L_{1})+\beta_{i,j}(I_{K_{2},s})+\beta_{i-1,j-1}(I_{K_{2},s}).$

It remains to show that $\beta_{i,j}(L_{1})$ can be computed using what is
known from the induction. We require one more E-K splitting. By definition,
$L_{1}=I_{K_{3}\setminus K_{1},s}$, so we can apply Theorem 3.5 one more time
(using $m=3$ and $r=1$) to get a splitting
$L_{1}=L_{1}^{\prime}+L_{2}^{\prime}$, where
$L_{1}^{\prime}=I(K_{3})^{(s)}\cap\langle x_{1}x_{2}x_{3}\rangle$. This yields

$\beta_{i,j}(L_{1})=\beta_{i,j}(L_{1}^{\prime})+\beta_{i,j}(L_{2}^{\prime})+\beta_{i-1,j}(L_{1}^{\prime}\cap
L_{2}^{\prime}).$

Using the same observations as before, notice that
$\beta_{i,j}(L_{2}^{\prime})=\beta_{i,j}(I_{K_{2}\setminus
K_{0},s})=\beta_{i,j}(I_{K_{2},s})$ and $\beta_{i-1,j}(L_{1}^{\prime}\cap
L_{2}^{\prime})=\beta_{i-1,j-1}(I_{K_{2},s})$. It is not difficult to see that
$L_{1}^{\prime}=x_{1}x_{2}x_{3}I(K_{3})^{(s-2)}$ so that
$\beta_{i,j}(L_{1}^{\prime})=\beta_{i,j-3}(I(K_{3})^{(s-2)})$.

Overall we have shown that

$\beta_{i,j}(I(K_{3})^{(s)})=3\beta_{i,j}(I_{K_{2},s})+3\beta_{i-1,j-1}(I_{K_{2},s})+\beta_{i,j-3}(I(K_{3})^{(s-2)}).$

By Lemma 3.9, we know that $\beta_{i,j}(I_{K_{2},s})=1$ if $i=1$, $j=2s$ and
$0$ otherwise. The result follows by induction. ∎

######  Remark 3.11.

We relied on the reduction to $L_{1}^{\prime}=x_{1}x_{2}x_{3}I(K_{3})^{(s-2)}$
in the proof of Theorem 3.10, and this is why 3 splittings are needed in the
proof. See Lemma 3.12 for a generalization.

###  3.3. Graded Betti Numbers Of Symbolic Powers Of $I(K_{m})$ In General

In Theorem 3.10, we used the fact that $I(K_{3})^{(s)}\cap\langle
x_{1}x_{2}x_{3}\rangle=x_{1}x_{2}x_{3}I(K_{3})^{(s-2)}$. The reader might
wonder why we actually needed 3 splittings in the theorem. Perhaps the
induction could be completed using just 2 splittings, for example, requiring a
similar identification for $L_{1}=I(K_{3})^{(s)}\cap\langle
x_{2}x_{3}\rangle$. A look at the generators however shows that we need all of
the variables present in the second ideal in the intersection to make such an
identification. For example, we know that
$\mathcal{G}(I(K_{3})^{(3)})=\\{x_{1}^{3}x_{2}^{3},x_{1}^{2}x_{2}^{2}x_{3},x_{1}^{2}x_{2}x_{3}^{2},x_{1}x_{2}^{2}x_{3}^{2},x_{1}^{3}x_{3}^{3},x_{2}^{3}x_{3}^{3}\\}$.
If we look at the terms for which $x_{2}x_{3}$ can be factored out, we notice
that the generator $x_{1}^{2}x_{2}^{2}x_{3}$ can be factored as
$x_{2}x_{3}(x_{1}^{2}x_{2})$, but $x_{1}^{2}x_{2}$ is not a minimal generator
for $I(K_{2})^{(s)}$ or $I(K_{3})^{(s)}$ with any choice of $s$. We avoid this
issue by only considering generators where each variable $x_{i}$ can be
factored out. In particular, when computing graded Betti numbers for
$I(K_{m})^{(s)}$, one will need to use $m$ E-K splittings to reduce to the
case $I_{K_{m}\setminus K_{0},s}$ and achieve a similar result to Theorem
3.10.

######  Lemma 3.12.

We have $I_{K_{m}\setminus K_{0},s}=I(K_{m})^{(s)}\cap\langle x_{1}\cdots
x_{m}\rangle=x_{1}\cdots x_{m}I(K_{m})^{(s-m+1)}$ when $s\geq m\geq 2$.

###### Proof.

This follows from the observation that if $x_{1}^{a_{1}}\cdots
x_{m}^{a_{m}}\in\mathcal{G}(I(K_{m})^{(s)})\cap\langle x_{1}\cdots
x_{m}\rangle$, then $x_{1}^{a_{1}-1}\cdots
x_{m}^{a_{m}-1}\in\mathcal{G}(I(K_{m})^{(s-m+1)})$. ∎

The underlying ideas in the proof of Theorem 3.10 can now be generalized to
obtain formulae for the graded Betti numbers for the $s$-th symbolic powers of
the edge ideal of $K_{m}$. However, as $m$ increases, so does the complexity
in writing the formulae. For the sake of concreteness, we provide only the
formulae for $m=4$ below.

######  Theorem 3.13.

If $i,j\in\mathbb{Z}^{+}$ and $s\geq 4$, then we have:

$\beta_{i,j}(I(K_{4})^{(s)})=6\,\,\,\,\text{if $i=1$, $j=2s$ or $i=3$,
$j=2s+2$};\,\,\,\beta_{2,2s+1}(I(K_{4})^{(s)})=12;\,\,\,and$
$\beta_{i,j}(I(K_{4})^{(s)})=\beta_{i,j-4}(I(K_{4})^{(s-3)})+4\beta_{i-1,j-4}(I(K_{3})^{(s-2)})+4\beta_{i,j-3}(I(K_{3})^{(s-2)})\,\,\,\,\text{otherwise}.$

While the statement of the formulae for these graded Betti numbers seems
cumbersome, they are a direct result of an inductive computation as in Theorem
3.10.

######  Remark 3.14.

Given any fixed $m>3$, we are able to inductively compute
$\beta_{i,j}(I(K_{m})^{(s)})$ for any $s>m-1$. If $s<m$, then at some point in
the induction process $r=m-s-1$ and we cannot reduce the computation any
further, and are left with finitely many Betti numbers to manually compute by
other means.

###  3.4. Minimum Socle Degree Of Symbolic Powers Of Edge Ideals Of Complete
Graphs

Having formulae for the graded Betti numbers of the symbolic powers for edge
ideals of complete graphs gives us information on related invariants of the
ideals. For example, we can obtain the minimum socle degrees which we now
discuss. In the following, the dimension of a homogeneous ideal $I\subseteq
R=k[x_{1},\ldots,x_{m}]$ is the Krull dimension of $R/I$. If $A=\oplus_{i\geq
0}A_{i}$ is a graded Artinian $k$-algebra, then $\mathfrak{m}=\oplus_{i\geq
1}A_{i}$ is a maximal ideal and we call the ideal quotient
$\mathrm{Socle}(A)=0:\mathfrak{m}=\\{r\in A\mid r\mathfrak{m}=0\\}$ the socle
of $A$. It is a finite-dimensional graded $k$-vector space, and we write
$\mathrm{Socle}(A)=\oplus_{i=0}k(-a_{i})$ where $a_{i}\in\mathbb{Z}^{+}$ are
the socle degrees of $A$. The minimum socle degree of $A$ is the minimum of
the $a_{i}$.

If $I$ is a homogeneous ideal of $R$ such that $R/I$ is Cohen-Macaulay, then
we can find a maximal regular sequence $f_{1},\ldots,f_{n}$ of $R/I$ where
$f_{i}$ is a homogeneous polynomial of degree 1 and $n=\dim(R/I)$. Let
$\bar{I}=I+\langle f_{1},\ldots,f_{n}\rangle$. In this situation, the Artinian
reduction $A=R/\bar{I}$ is $0$-dimensional, and hence Artinian. It is well-
known that the socle degrees of $A$ are related to the back twists at the end
of a minimal resolution of $R/I$. More precisely, let us write the graded
minimal free resolution for $R/I$ as

$0\rightarrow F_{m-1}=\bigoplus_{i}R(-a_{i})\rightarrow\cdots\rightarrow
F_{1}\rightarrow R\rightarrow R/I\rightarrow 0.$

The last module in the free resolution for $R/\bar{I}$ is $F_{m-1}(-n)$. Since
it is in position $m+n-1$ of the free resolution, the socle degrees of $A$ are
$s_{i}=(a_{i}+n)-(m+n-1)=a_{i}-(m-1)$ by [Kustin-Ulrich, Lemma 1.3]. With a
slight abuse of notation, we will say that socle degrees of $A$ are the socle
degrees of $R/I$. In particular, the minimum socle degree of $R/I$ is just
$\min_{i}\\{s_{i}\\}$. This is similar to the setup in [Tohaneanu] and
[Tohaneanu-VanTuyl] except for the labelling of indices.

######  Lemma 3.15.

If $I=I(K_{m})\subset R=k[x_{1},\ldots,x_{m}]$, then $R/I^{(s)}$ is Cohen-
Macaulay of dimension 1.

###### Proof.

The Cohen-Macaulay property follows from [RTY12, Theorem 3.6] and [Varbaro,
Theorem 2.1]. It suffices to show that $R/I$ has dimension 1 since $I^{(s)}$
and $I$ have the same height. Each vertex cover of $K_{m}$ involves exactly
$m-1$ vertices and defines a primary component in the primary decomposition of
$I$ by Lemma 2.1. Since $R/I$ is Cohen-Macaulay, all of the associated primes
of $I$ must have the same height, so it suffices to compute the height of just
one of these ideals. One such ideal is $\langle x_{1},\ldots,x_{m-1}\rangle$
which has height $m-1$ (so $R/I$ has dimension 1), proving the result. ∎

As a consequence, we can apply our technique to determine the minimum socle
degree of the $s$-th symbolic power of an edge ideal of any complete graph for
any $s\geq 2$. For example, the minimum socle degree of
$R/I(K_{2})^{(s)}=2s-1$ and the minimum socle degree of $R/I(K_{3})^{(3)}=4$
since, by Theorem 3.10,
$\beta_{2,6}(I(K_{3})^{(3)})=2,\beta_{1,5}(I(K_{3})^{(3)})=\beta_{1,6}(I(K_{3})^{(3)})=\beta_{2,7}(I(K_{3})^{(3)})=3$
and $\beta_{i,j}(I(K_{3})^{(3)})=0$ otherwise.

##  4\. Parallelizations

It is natural to ask if we can determine the graded Betti numbers of edge
ideals of graphs obtained by certain graph operations. One such operation is
called a graph parallelization, which we now turn our attention to. The notion
of a graph parallelization appears in [MMV11, Section 2] in the discussion
about polarizations and depolarizations of monomial ideals. We continue to
work with undirected finite simple graphs.

######  Definition 4.1.

Let $G$ be a graph with vertex set $\\{x_{1},\dots,x_{m}\\}$ and fix
$\alpha=(\alpha_{1},\dots,\alpha_{m})\in(\mathbb{Z}^{+})^{m}$. The
parallelization of $G$ by $\alpha$, denoted $G^{\alpha}$, is the graph with
vertex set
$V(G^{\alpha})=\\{x_{1,1},\dots,x_{1,\alpha_{1}},\dots,x_{m,1},\dots,x_{m,\alpha_{m}}\\}$
and edge set $E(G^{\alpha})=\\{\\{x_{i,t},x_{j,\ell}\\}|\\{x_{i},x_{j}\\}\in
E(G)\\}$.

For example, the graph for $K_{3}^{(3,1,1)}$ is obtained by duplicating
$x_{1}$ to get the vertices $x_{1,1},x_{1,2}$ and $x_{1,3}$ and adding edges
between these vertices and $x_{2,1}$ and $x_{3,1}$.

$x_{1,1}$$x_{2,1}$$x_{3,1}$$x_{1,2}$$x_{1,3}$

In particular, when $\alpha=(1,\ldots,1)$, we recover the original graph so
that $G^{(1,\ldots,1)}$ is the same as $G$ (we are identifying $x_{i,1}=x_{i}$
in general). We will denote the set of vertices of $G^{\alpha}$ corresponding
to the vertex $x_{i}\in V(G)$ by $V_{i}$. These are called the duplications of
$x_{i}$. The next lemma shows that all minimal vertex covers for $G^{\alpha}$
come from minimal vertex covers for $G$ replaced by the appropriate
duplications $V_{i}$. Recall that the open neighbourhood of a given set
$V^{\prime}$ of vertices in a graph $G$, denoted $N(V^{\prime})$, is the set
of all vertices which are adjacent to vertices in $V^{\prime}$, not including
the vertices in $V^{\prime}$ themselves.

######  Lemma 4.2.

Let $G$ be a graph on $m$ vertices and fix $\alpha\in(\mathbb{Z^{+}})^{m}$.
Then any minimal vertex cover for $G^{\alpha}$ has the form
$\\{x_{i_{1},1},\dots,x_{i_{1},\alpha_{i_{1}}},\dots
x_{i_{r},1}\dots,x_{i_{r},\alpha_{i_{r}}}\\}$ where
$\\{x_{i_{1}},\dots,x_{i_{r}}\\}$ is a minimal vertex cover of $G$.

###### Proof.

Let $S$ be a minimal vertex cover of $G$ and, without loss of generality,
suppose that $S=\\{x_{1},\dots,x_{n}\\}$. Let us define
$S^{\prime}=\\{x_{1,1},\dots,x_{1,\alpha_{1}},\dots,x_{n,1},\dots,x_{n,\alpha_{n}}\\}$
as the set of vertices of $G^{\alpha}$ obtained by replacing each vertex
$x_{i}$ in $S$ by all of its duplicates $V_{i}$ in $G^{\alpha}$. We first show
that $S^{\prime}$ is a minimal vertex cover of $G^{\alpha}$.

Let $\\{x_{i,t},x_{j,\ell}\\}$ be any edge of $G^{\alpha}$. By definition,
$\\{x_{i},x_{j}\\}\in E(G)$. Since $S$ is a minimal vertex cover of $G$, at
least one of $x_{i}$ or $x_{j}$ is in $S$. Without loss of generality, let us
suppose that $x_{i}\in S$. Then $V_{i}\subset S^{\prime}$, and so $S^{\prime}$
contains a vertex from the edge $\\{x_{i,t},x_{j,\ell}\\}$. That is,
$S^{\prime}$ is a vertex cover of $G^{\alpha}$.

To see that $S^{\prime}$ is minimal, suppose that there exists $x_{i,t}\in
S^{\prime}$ such that $S^{\prime}\backslash\\{x_{i,t}\\}$ is a vertex cover of
$G^{\alpha}$. Then necessarily $N(x_{i,t})\subseteq S^{\prime}$. By definition
of a parallelization, $N(V_{i})=N(x_{i,t})$. Hence, if $e\in E(G^{\alpha})$
contains some vertex $x_{i,\ell}$, then $S^{\prime}$ contains a vertex of $e$
other than $x_{i,\ell}$. That is, $S^{\prime}\backslash\\{V_{i}\\}$ is a
vertex cover of $G^{\alpha}$. However, since $N(V_{i})\subseteq S^{\prime}$,
by construction of $S^{\prime}$ it follows that $N(x_{i})\subseteq S$. Then
$S\backslash\\{x_{i}\\}$ is a vertex cover of $G$, contradicting the
minimality of $S$.

It remains to show that these are the only minimal vertex covers of
$G^{\alpha}$. Let $C^{\prime}$ be a minimal vertex cover of $G^{\alpha}$. Note
that for any $x_{i,t}\in C^{\prime}$, there exists an edge $e\in
E(G^{\alpha})$ such that $e=\\{x_{i,t},x_{j,\ell}\\}$ (since $C^{\prime}$ is a
minimal vertex cover, $x_{i,t}$ cannot be an isolated vertex). However,
$\\{x_{i,t},x_{j,\ell}\\}\in E(G^{\alpha})$ if and only if
$\\{x_{i},x_{j}\\}\in E(G)$. So for all $x\in V_{i},y\in V_{j},\\{x,y\\}\in
E(G^{\alpha})$. Furthermore, if there exists some $V_{i}$ such that
$V_{i}\nsubseteq C^{\prime}$, then by the above, $N(V_{i})\subseteq
C^{\prime}$. Hence, since $C^{\prime}$ is minimal, $V_{i}\cap
C^{\prime}=\emptyset$ and so either $V_{i}\subseteq C^{\prime}$ or
$V_{j}\subseteq C^{\prime}$. Thus $C^{\prime}=V_{1}\cup\dots\cup V_{t}$ for
some labelling of the partite sets. Since $G$ is an induced subgraph of
$G^{\alpha}$, $C^{\prime}$ being a minimal vertex cover implies that
$C=\\{x_{1},\dots,x_{t}\\}=V(G)\cap C^{\prime}$ is a vertex cover of $G$, and
if $C$ were not minimal then the minimal vertex cover contained in $C$ would
correspond to a minimal vertex cover of $G^{\alpha}$ properly contained in
$C^{\prime}$, a contradiction. ∎

######  Proposition 4.3.

Let $G$ be a graph with vertex set $\\{x_{1},\dots,x_{m}\\}$ and edge ideal
$I=I(G)$. Fix $\alpha=(\alpha_{1},\dots,\alpha_{m})\in(\mathbb{Z^{+}})^{m}$
and denote the edge ideal of $G^{\alpha}$ by $I_{\alpha}$. Then

$\mathcal{G}(I_{\alpha}^{(s)})=\\{x_{1,1}^{e_{1,1}}\cdots
x_{1,\alpha_{1}}^{e_{1,\alpha_{1}}}\cdots x_{m,1}^{e_{m,1}}\cdots
x_{m,\alpha_{m}}^{e_{m,\alpha_{m}}}|\sum_{j=1}^{\alpha_{i}}e_{i,j}=a_{i},\text{
where $x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in\mathcal{G}(I)$}\\}.$

###### Proof.

The argument is similar to that of Proposition 3.2. We use Lemma 3.1 and Lemma
4.2 to show that the set is generating. Minimality follows from the fact that
$x_{1}^{a_{1}}\cdots x_{m}^{a_{m}}\in\mathcal{G}(I)$ and the description of
minimal vertex covers. ∎

###  4.1. Graded Betti Numbers Of Parallelizations

The graded Betti numbers of parallelizations for complete graphs can be
bounded below using the splittings from Corollary 3.7. This however is a
special case of the next result.

######  Proposition 4.4.

If $G$ is finite simple graph on $m$ vertices, $s\geq 2$, and
$\alpha\in(\mathbb{Z^{+}})^{m}$, then for all $i,j\geq 1$,
$\beta_{i,j}(I(G^{\alpha})^{(s)})\geq\beta_{i,j}(I(G)^{(s)})$.

###### Proof.

Since we can view $G$ as an induced subgraph of $G^{\alpha}$, the result
follows as a direct consequence of [GHOS18, Lemma 4.4] (which is a
generalization of the work in [HH15] for edge ideals). ∎

Proposition 4.4 naturally leads one to try to determine what classes of ideals
are obtained by parallelization of graphs $G$ where the Betti numbers of
$I(G)^{(s)}$ are known. We illustrate this useful direction with complete
$n$-partite graphs. Recall that the complete $n$-partite graph with partite
sets of size $a_{1},\ldots,a_{n}$, denoted $K_{a_{1},\ldots,a_{n}}$, is the
graph with vertex set
$V=\\{x_{1,1},\ldots,x_{1,a_{1}},\dots,x_{n,1},\ldots,x_{n,a_{n}}\\}$ and edge
set $E=\\{\\{x_{i,j},x_{\ell,m}\\}\>|\>i\neq\ell\\}$. In addition, recall that
an independent set of vertices of a graph $G$ is a set of vertices in which no
two vertices are adjacent.

######  Corollary 4.5.

If $K_{a_{1},\ldots,a_{n}}$ is a complete $n$-partite graph, then for all
$s\geq 2$ and $i,j\geq 1$ we have the bound

$\beta_{i,j}(I(K_{a_{1},\ldots,a_{n}})^{(s)})\geq\beta_{i,j}(I(K_{n})^{(s)}).$

###### Proof.

The result follows by noticing that
$K_{a_{1},\ldots,a_{n}}=K_{n}^{(a_{1},\ldots,a_{n})}$. To see this, observe
that the duplicates of each vertex in $K_{n}^{(a_{1},\ldots,a_{n})}$ form an
independent set, and any two of these independent sets have all possible edges
between them by definition of a parallelization applied to a complete graph. ∎

As a consequence, the results of Section 3 combined with Corollary 4.5 yields
explicit lower bounds for the graded Betti numbers of symbolic powers of edge
ideals of complete $n$-partite graphs.

Not surprisingly, the bound of Proposition 4.4 is not very effective as the
entries in $\alpha$ grow. A better lower bound would not only depend on
$I(G)^{(s)}$, but also on $\alpha$. As a motivational example, consider
$I(K_{3})^{(2)}=\langle\epsilon_{1},\epsilon_{2},\epsilon_{3},\epsilon_{4}\rangle=\langle
x_{1}^{2}x_{2}^{2},x_{1}^{2}x_{3}^{2},x_{2}^{2}x_{3}^{2},x_{1}x_{2}x_{3}\rangle$.
One possible relation on these generators is
$\sigma=x_{3}\epsilon_{1}-x_{1}x_{2}\epsilon_{4}=0$. Now let $\alpha=(2,2,2)$
and consider $I(K_{3}^{\alpha})^{(2)}$. Then the relation demonstrated by
$\sigma$ also holds if we substitute any of the variable duplications. One
possible choice is using $x_{3,2}$ instead of $x_{3,1}=x_{3}$. Now if
$\epsilon_{4}^{\prime}=x_{1}x_{2}x_{3,2}$, then
$\sigma^{\prime}=x_{3,2}\epsilon_{1}-x_{1}x_{2}\epsilon_{4}^{\prime}=0$ also
(where $x_{1}=x_{1,1}$ and $x_{2}=x_{2,1}$). The same would hold true if we
replaced any of the variables $x_{i}$ by one of their duplications $x_{i,j}$.
In this way we get groupings of relations corresponding to some choice of the
duplicated variables, which is also true for higher syzygies.

We see this more generally. In particular, if $\sigma$ is a syzygy for the
$i$-th step of the minimal graded free resolution of $I(G)^{(s)}$, then it is
also a syzygy for the same step of the minimal graded free resolution of
$I(G^{\alpha})^{(s)}$, and substituting any variable in $\sigma$ with any of
its duplicates also yields a syzygy. We can expect $\prod_{i}\alpha_{i}$ many
blocks of such relations, and so we might guess that
$\beta_{i,j}(I(G^{\alpha})^{(s)})\geq(\prod_{i}\alpha_{i})\beta_{i,j}(I(G)^{(s)})$.
Another lower bound would instead use blocks of relations coming from disjoint
copies of $G$ in $G^{\alpha}$ (that is copies of $G$ which partition the
vertex set of $G^{\alpha}$). There are exactly
$\operatorname{min}\\{\alpha_{i}\\}$ many of these, leading to a weaker bound,
but likely one which is easier to prove. Instead, we will conjecture that the
stronger bound holds. This bound works over any field since any potential
cancellation in positive characteristic would occur both before and after any
substitution by duplications.

######  Conjecture 4.6.

Let $G$ be a graph on $m$ vertices and let
$\alpha=(\alpha_{1},\dots,\alpha_{m})\in(\mathbb{Z}^{+})^{m}$. For all
$i,j\in\mathbb{Z}^{+}$ and $s\geq 2$, we have
$\beta_{i,j}(I(G^{\alpha})^{(s)})\geq(\prod_{i}\alpha_{i})\beta_{i,j}(I(G)^{(s)})$.

One might worry that the relations might not be part of a minimal generating
set for the syzygy. However, we know from Gröbner theory that there at least
$\binom{\prod_{i}\alpha_{i}}{2}$ relations which generate the syzygy, and the
conjecture simply asks that a fraction of these are part of a minimal
generating set. In particular, we know how to find generators for syzygies
using $S$-polynomials (for example by Schreyer’s Theorem). Information about
$S$-polynomials and computing syzygies can be found in [Eisenbud]. To prove
the conjecture, one would need to show that the $S$-polynomials corresponding
to each choice of duplication are part of a minimal generating set.

## References


# Realizations of Measurement Based Quantum Computing

Swapnil Nitin Shah  Department of Physics, University of Washington, Seattle,
WA 98195, USA

###### Abstract

The Measurement Based Quantum Computation (MBQC) model achieves universal
quantum computation by employing projective single qubit measurements with
classical feedforward on a highly entangled multipartite cluster state [1].
Rapid advances in improving scalability of quantum computing systems have
enabled the generation of large cluster states for implementing MBQC on
various platforms. This review focuses on three such efforts, each utilizing a
different quantum computing technology viz., superconducting qubits [8],
trapped ion qubits [9] and squeezed photon states [4]. MBQC is being
increasingly employed on optical platforms which can generate large entangled
resource states but lack the ability to perform deterministic entangling gates
[4, 5].

Measurement Based Quantum Computation; Cluster States

††preprint: APS/123-QED

##  I Introduction

The standard circuit model of quantum computation involves initialization of
qubits in a known state followed by a sequence of one and two qubit gates as
determined by the algorithm. The result is read out by measuring the qubits in
a predetermined computational basis. Unlike classical computation, it is not
possible to build a general purpose programmable quantum circuit which can
perform an arbitrary computation based on an input program state [3]. The
Measurement Based Quantum Computation (MBQC) model employs successive single
qubit measurements on a highly entangled multipartite quantum state, i.e. a
cluster state in order to perform computation [1]. The unitary operation
performed is determined by the eigenbases chosen for these measurements. MBQC
allows the possibility of a general purpose programmable quantum computer,
given the ability to adapt measurements based on previous outcomes, on a
sufficiently large cluster state [2]. As single qubit measurements reduce
entanglement of the cluster state, MBQC is also called one-way quantum
computing.

In this paper, we review the MBQC model and its recent implementations using
superconducting qubits [8], trapped ion qubits [9] and spatial modes of
squeezed photons [4]. With rapid advances in utilizing these continuous
variable states of squeezed photons to create large cluster states, MBQC is
being increasingly employed on these platforms [4, 5].

###  I.1 Cluster States

Cluster states are multipartite quantum states on a _d_ -dimensional lattice
of qubits with Ising like nearest neighbor interactions [1]. Representing the
neighborhood of a qubit $c$ in a lattice $C$ by $\Gamma_{c}$, the cluster
state $\left|\psi_{C}\right\rangle$ is given by [1]

$\left|\psi_{C}\right\rangle\equiv\mathcal{N}\bigotimes_{c\in
C}\left(\left|1\right\rangle_{c}\bigotimes_{x\in\Gamma_{c}}Z^{(x)}+\left|0\right\rangle_{c}\right)$
(1)

where $\mathcal{N}$ is the normalization factor and $Z^{(x)}$ is the Pauli-Z
operator applied to qubit $x$. $\left|\psi_{C}\right\rangle$ is an eigenstate
of the stabilizer operator

$K_{a}\equiv X_{a}\bigotimes_{x\in\Gamma_{a}}Z^{(x)}$ (2)

where $X_{a}$ is the Pauli-X operator applied to qubit $a$. Such a state can
be realized by performing controlled-Z gates between qubits initialized in the
$\left|+\right\rangle\equiv\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right\rangle\right)$
states. Fig. 1 shows a 2-d cluster state on which a stabilizer operator is
applied.

Figure 1:  Visualization of a 2-d cluster state under the action of a
stabilizer operator (Source: Ref. 1)

###  I.2 MBQC Computation Scheme

Any unitary operation on an array of qubits can be decomposed into one-qubit
rotations and universal two-qubit gates (e.g. Controlled-NOT (CNOT)). Once a
sufficiently large cluster state (Eq. (1)) is available, it can be used for
arbitrary unitary operations using such decomposition [1, 2]. Measurements
implementing the gates are performed in a sequence (imposed by dependence on
previous measurements) along one dimension of the cluster state. Individual
gates can be carved out in the cluster by measuring the unused qubits in the
computational basis [1] (Fig. 2). Such a measurement destroys entanglement
between the measured qubit and its neighbors, effectively removing it from the
cluster. Formally,

$P^{(c^{*})}_{Z}\left|\psi_{C}\right\rangle=\mathcal{N}^{\prime}\bigotimes_{c\,\in\,C\backslash\\{c^{*}\\}}\left(\left|1\right\rangle_{c}\bigotimes_{x\in\Gamma_{c}}Z^{(x)}+\left|0\right\rangle_{c}\right)$
(3)

where $P^{(c^{*})}_{Z}$ is the projection operator in the computational basis
for qubit $c^{*}$.

Figure 2:  One-way quantum computation on a cluster state. $\odot$ represents
unused qubits measured in the computational (Pauli-Z) basis, $\uparrow$ are
qubits measured in Pauli-X basis and tilted arrows are qubits measured in X-Y
plane (Source: Ref. 1)

The qubit states are transported through the cluster via teleportation which
is performed by measurement of qubit state in the Pauli-X
($\left|+\right\rangle,\left|-\right\rangle$) basis. To illustrate, consider
Pauli-X measurement of a qubit in state
$\left|\psi_{\mathrm{in}}\right\rangle\equiv\alpha\left|0\right\rangle+\beta\left|1\right\rangle$
($\left|\psi^{\prime}_{\mathrm{in}}\right\rangle\equiv
Z\left|\psi_{\mathrm{in}}\right\rangle=\alpha\left|0\right\rangle-\beta\left|1\right\rangle$)
entangled with another qubit in a cluster state

$\left|\phi\right\rangle\equiv\left(\frac{1}{\sqrt{2}}\left|\psi_{\mathrm{in}}\right\rangle\otimes\left|0\right\rangle+\frac{1}{\sqrt{2}}\left|\psi^{\prime}_{\mathrm{in}}\right\rangle\otimes\left|1\right\rangle\right)$
(4a)
$P^{(\psi)}_{X}\left|\phi\right\rangle=\frac{1}{\sqrt{2}}\left(\alpha\left|+\right\rangle+(-1)^{s_{1}}\beta\left|-\right\rangle\right)$
(4b)

where $s_{1}=\\{0,1\\}$ is the outcome of measurement. The state
$\left|\psi_{\mathrm{in}}\right\rangle$ (up to a phase correction) is
teleported to the other qubit in the Pauli-X basis as a result of measurement
[1]. In general, the source qubit state is teleported to the target in the
Pauli-X basis for odd number of teleportation steps and in the Pauli-Z basis
for even number of steps.

####  I.2.1 Unitary Gates in MBQC

Every one-qubit rotation $U_{R}\in$ SU(2) admits a decomposition in Euler
angles as [2]

$U_{R}(\alpha,\beta,\gamma)=U_{X}(\gamma)U_{Z}(\beta)U_{X}(\alpha)$ (5)

where $U_{X}$ and $U_{Z}$ describe rotations about the Pauli-X and Pauli-Z
axis respectively. This can be implemented using a linear chain of 5 qubits on
a cluster state with input state on qubit 1 (Fig. 3). Qubits 1$\rightarrow$4
are measured in the following bases [1]

$\mathcal{B}_{j}\left(\theta_{j}\right)\equiv\left\\{\frac{\left|0\right\rangle+e^{i\theta_{j}}\left|1\right\rangle}{\sqrt{2}},\frac{\left|0\right\rangle-e^{i\theta_{j}}\left|1\right\rangle}{\sqrt{2}}\right\\}$
(6) $\begin{split}&\theta_{1}=0;\;\;\;\theta_{2}=\alpha(-1)^{s1+1};\\\
&\theta_{3}=\beta(-1)^{s2};\;\;\;\theta_{4}=\gamma(-1)^{s1+s3}\end{split}$ (7)

where $s1\dots s4$ are the measurement outcomes. The implemented unitary
operation is given by $U_{g}=U_{\Sigma}U_{R}$ where $U_{\Sigma}\equiv
X^{s2+s4}Z^{s1+s3}$ describes the correction required based on measurement
outcomes.

Figure 3:  One qubit rotation using a linear chain of 5 qubits in a cluster
state. (Source: Ref. 2)

In order to have a universal set of gates, a universal 2-qubit gate is
necessary. Fig. 4 shows a minimal CNOT implementation on a cluster state. The
input qubit $t_{in}$ and its neighbor are measured in the Pauli-X basis,
thereby implementing a CNOT (up to Pauli corrections) between control qubit
$c$ and output qubit $t_{out}$ [1]. In practice, the control and target qubits
are teleported to other qubits (Eq. (4)) in the cluster after computation.

Figure 4:  Minimal CNOT gate implementation on a cluster state. $t_{in}$ is
the input, $t_{out}$ is the output and $c$ is the control qubit (Source: Ref.
1)

A composite circuit such as in Fig. 2 can be created on the cluster which uses
arbitrary one qubit rotations and CNOT gates to perform complex unitary
operations on the input qubits.

##  II Implementations

Physical realizations of MBQC require the ability to a) Create large cluster
states with a high degree of persistent entanglement between the qubits and b)
Perform projective measurements on individual qubits forming the cluster in
chosen eigenbases with feedforward control [2]. There have been many recent
implementations of MBQC model, of which we focus on those employing
superconducting qubits [8], trapped ion qubits [9] and spatio-temporal modes
of squeezed photons [4]. This computation model is especially suitable for
photonic quantum systems which are quite scalable but lack the ability to
directly perform deterministic entangling gates. In the next few sections, we
review recent efforts of implementing MBQC on the aforementioned platforms.

###  II.1 MBQC with Squeezed Photon Modes

One can encode quantum information in spatial and temporal modes of squeezed
photon states viz., qumodes [6], which are continuous variable analogues of
qubits. The Pauli-Z basis is replaced by the position quadrature basis
$\left|q\right\rangle_{q\in\mathbb{R}}$ and the Pauli-X basis is replaced by
the momentum quadrature basis $\left|p\right\rangle_{p\in\mathbb{R}}$ in this
analogue. In the article [Ref. 4], the authors utilize squeezed photon states
in two spatial modes and standard linear optical devices to implement a) A 2-d
Gaussian photonic cluster state with a width of 6 qubits and infinite depth
and b) Universal set of one and two qubit Gaussian unitaries using this
cluster state.

####  II.1.1 Continuous Variable Cluster State

The article [Ref. 4] describes generation of a 2-d cluster state with temporal
mode encoding of squeezed photon states in two spatial modes, $A$ and $B$ in
Fig. 5. Optical Parametric Oscillators (OPO) are used to generate the squeezed
photon states which are interfered in an unbalanced interferometer (delay of
$\tau$ in spatial mode B) to generate a 1-d cluster state, also known as a
dual rail quantum wire [5]. Each point in this cluster corresponds to a single
spatial mode $s\in\\{A,B\\}$ and temporal mode $k\in\mathbb{N}$. Using a delay
line of $N\tau$ for mode $B$ of the 1-d cluster, it is coiled up into a 2-d
cylindrical cluster state. High efficiency homodyne detectors are employed for
both spatial modes which can make projective measurements in arbitrary
quadrature basis $\hat{q}\cos{\theta}+\hat{p}\sin{\theta}$.

Figure 5:  Experimental setup and visualization of the cylindrical 2-d cluster
state. $N=12$ which provides 6 parallel modes for computation (other 6 are
control modes). The measurement device consists of a beam splitter and two
homodyne detectors measuring in basis $\theta_{A,k},\theta_{B,k}$ for temporal
mode $k$ (Source: Ref. 4)

In Fig. 5, the gray nodes have $k$ odd and are measured in the quadrature
basis $\theta_{c}=(-1)^{(k-1)/2}\pi/4$. This projects the cluster as wires for
state teleportation along the length of the 2-d cylinder [4, 5]. These form
the logic levels for computation of arbitrary multimode gaussian unitaries. If
Gottesman-Kitaev-Preskill (GKP) encoded qubits are available, universal fault-
tolerant quantum computation is possible with this framework [6, 4].

####  II.1.2 Single Mode Gaussian Gates

A single mode Gaussian unitary is implemented using teleportation on a logic
level of the 2-d cluster [4] (Fig. 6).

Figure 6:  (Left) Single mode Gaussian gate on a projected wire, (Right)
Equivalent teleportation based circuit (Source: Ref. 4)

The unitary that is implemented depends on the measurement bases for the two
homodyne detectors (up to a measurement dependent displacement) as [4]

$\hat{U}=(-1)^{w}\hat{R}\left(\theta_{+}\right)\hat{S}\left(\tan{\theta_{-}}\right)\hat{R}\left(\theta_{+}\right)$
(8)

where $w$ is the wire number, $\theta_{\pm}=\theta_{A,k}\pm\theta_{B,k}$ and
$\hat{R}\left(\theta\right)$, $\hat{S}(t)$ are the quadrature rotation and
squeezing unitaries given by

$\hat{R}\left(\theta\right)\equiv
e^{i\theta(\hat{q}^{2}+\hat{p}^{2})/2},\;\;\;\;\hat{S}(t)\equiv
e^{i\ln{t}(\hat{x}\hat{p}+\hat{p}\hat{x})/2}$ (9)

A cascade of two such unitaries (Eq. (7)) can implement any single mode
Gaussian unitary (up to a displacement) by choosing appropriate quadrature
measurement bases [5].

####  II.1.3 Two Mode Controlled Phase Gate

To complete the universal set of Gaussian unitaries, an entangling two mode
gate must be implemented. The authors demonstrate how entanglement between two
logic levels and one pair of control modes can be used to implement a Gaussian
unitary with two input modes [4] (Fig. 7).

Figure 7:  (Left) Two mode Gaussian gate using two logic levels and a pair of
control modes (Right) Equivalent teleportation based circuit (Source: Ref. 4)

As with the single mode case, the implemented two mode unitary is determined
by the measurement bases of the homodyne detectors for each temporal mode. The
two mode controlled phase gate $\hat{C}_{z}\equiv
e^{ig(\hat{q}_{1}\otimes\hat{q}_{2})}$ along with the single mode rotation and
sqeezing gates (Eq. (8)) form a universal multimode Gaussian gate set [4]. To
implement the controlled phase gate (up to known rotations) between the two
input modes, choice of measurement bases are determined to be [4, 5]

$\begin{pmatrix}\theta_{A,k}\\\ \theta_{B,k}\\\ \theta_{A,k+2}\\\
\theta_{B,k+2}\\\ \theta_{A,k+N}\\\ \theta_{B,k+N}\\\ \theta_{A,k+N+1}\\\
\theta_{B,k+N+1}\\\ \theta_{A,k+N+2}\\\
\theta_{B,k+N+2}\end{pmatrix}=\begin{pmatrix}\pi/4\\\ -\pi/4\\\
(-1)^{w}\pi/4\\\ -(-1)^{w}\pi/4\\\ (-1)^{w}[\pi/2-\arctan{(g/2)}]\\\ 0\\\
(-1)^{w}\pi/4\\\ (-1)^{w}[\pi/4+2\arctan{(g/2)}]\\\
(-1)^{w}[\pi/2-\arctan{(g/2)}]\\\ 0\end{pmatrix}$ (10)

where $w$ is the wire number of the input mode $B,k$ and the implemented
unitary transformation is
$\left[\hat{R}(\pi/2)\otimes\hat{R}\left((-1)^{w}\pi/2\right)\right]\hat{C}_{z}$.

The above gate implementations assume infinite squeezing, which would require
infinite energy and are therefore unphysical. In practice, one employs
finitely squeezed photon states which introduce gate noise in the computation
which accumulates as more gates are added. For one and two mode gates, the
measured gate noise (after accounting for the gate noise factor of 6 dB)
agrees well with the measured squeezing variance of -4.4 dB in the initial
momentum quadratures. In order to make this approach scalable, some form of
error correction would be required. GKP encoded qubits [6] (albeit not yet
experimentally realized in optical spectrum) is one approach which could be
used for fault-tolerant quantum computation with this scheme.

###  II.2 MBQC with Superconducting Qubits

In the article [Ref. 8], the authors propose an experimentally feasible
implementation of a cluster state of the form - Eq. (1) using high fidelity
$\hat{C}_{z}$ gates on a 2-d lattice of superconducting qubits. They discuss
the construction of a universal CNOT gate (Fig. 4) on this plaform and its
expected fidelity. An alternative entangling $\hat{U}_{Bell}$ gate is proposed
which reduces the number of qubits required for CNOT gate implementation. The
2-d cluster state generated with $\hat{U}_{Bell}$ gates is expected to be
Maximally Persistent and Maximally Connected (MPMC) which could potentially
lead to increased scalability of such implementations [8].

####  II.2.1 Cluster State with Transmon Qubits

The interaction Hamiltonian of a pair of Transmon qubits with same energy gap
between ground $\left|0\right\rangle$ and excited $\left|1\right\rangle$
states is of the form [8]

$\hat{H}_{\mathrm{int}}=\hbar\,g_{\mathrm{eff}}\sum_{(j,k),\,j<k}\left(\frac{\mathbb{I}-\sigma^{j}_{z}}{2}\right)\left(\frac{\mathbb{I}+\sigma^{k}_{z}}{2}\right)$
(11)

For a 2-d lattice of Transmons, time evolution of interaction is given by
$\hat{\mathcal{U}}=e^{-i\hat{H}_{\mathrm{int}}t/\hbar}$. For
$g_{\mathrm{eff}}t=\pi$ and initial states $\left|+\right\rangle$, this
describes a cluster state of the form

$\left|\psi^{\prime}_{C}\right\rangle\equiv\mathcal{N}\bigotimes_{c\in
C}\left(\left|1\right\rangle_{c}\bigotimes_{x\in\Gamma_{c}}-Z^{(x)}+\left|0\right\rangle_{c}\right)$
(12)

which differs in sign of Pauli-Z operator from Eq. (1). To express this
cluster state in terms of $\hat{C}_{z}$ gates, one considers initial state of
a qubit to be $\left|+\right\rangle$ for control of even number of qubits and
$\left|-\right\rangle$ for control of odd number of qubits (Fig. 8). For a 2-d
lattice of Transmon qubits of size $h\times l$, each qubit can be represented
by a vector $\vec{p}\equiv(j,k)$, where $(j,k)$ is its coordinate on the
lattice [8].

Figure 8:  Cluster state with Transmon qubits. Arrows represent $\hat{C}_{z}$
gates from control to target. All arrows of same color represent gates that
can be applied simultaneously. “+” and “-” represent respective state
initializations (Source: Ref. 8)

Using this, the cluster (Eq. (11)) is given by

$\displaystyle\left|\psi^{\prime}_{C}\right\rangle=\left[\prod_{\vec{p}\in\left\\{\mathcal{L}+\mathcal{L}_{x}\right\\}}\mathcal{C}^{\left(\vec{p},\vec{p}+\hat{m}\right)}_{z}\right]\left[\prod_{\vec{p}\in\left\\{\mathcal{L}+\mathcal{L}_{y}\right\\}}\mathcal{C}^{\left(\vec{p},\vec{p}+\hat{n}\right)}_{z}\right]$
(13)
$\displaystyle\times\left[\bigotimes_{\vec{p}\in\mathcal{L}}\left|+_{\vec{p}}\right\rangle\right]\left[\bigotimes_{\vec{p}\in\mathcal{L}_{x}}\left|-_{\vec{p}}\right\rangle\right]\left[\bigotimes_{\vec{p}\in\mathcal{L}_{y}}\left|-_{\vec{p}}\right\rangle\right]$
$\displaystyle\otimes\left|+_{(h,l)}\right\rangle$

where $\mathcal{L}\equiv\\{(j,k)\\}$, $\mathcal{L}_{x}\equiv\\{(j,l)\\}$,
$\mathcal{L}_{y}\equiv\\{(h,k)\\}$, $j=\\{1,2\dots h-1\\}$, $k=\\{1,2\dots
l-1\\}$ and $\hat{m}\equiv(1,0)$, $\hat{n}\equiv(0,1)$.

####  II.2.2 CNOT with Transmon Cluster States

Implementation of a CNOT gate using the Transmon cluster state (Eq. (11))
follows the recipe shown in Fig. 4. The initial state of the four qubits is

$\left|\Psi_{0}\right\rangle\equiv\left|i_{1}\right\rangle\left|+\right\rangle\left|+\right\rangle\left|c_{4}\right\rangle$
(14)

On applying the three $\hat{C}_{z}$ gates followed by measurement of qubits 1
and 2 in the Pauli-X basis, this state evolves into [8]

$\left|\Psi_{m}\right\rangle\equiv\mathcal{F}_{3,4}\left|l\right\rangle\left|m\right\rangle\left|i\oplus
c\right\rangle\left|c_{4}\right\rangle$ (15)

where $l,m$ are measurement outcomes of the respective qubits and
$\mathcal{F}_{3,4}\equiv\left(\sigma^{3}_{x}\right)^{m}\left(\sigma^{3}_{z}\sigma^{4}_{z}\right)^{l}$
is the measurement based correction. The authors report a $\hat{C}_{z}$ gate
fidelity of $99.5\%$ with an evolution time of $\approx 0.05\mu s$ per gate.
Also, the readout and measurement process is estimated to have an error of
$2\%$ and a processing time of $\approx 2\mu s$ per measurement. Estimated
CNOT gate fidelity is therefore $(0.995^{3}-0.04)\times 100\approx 94.5\%$
with an evaluation time of $<5\mu s$, which is much smaller than Transmon
coherence times [8].

The authors further discuss an alternative entangling gate $\hat{U}_{Bell}$
for generating cluster states. The action of this gate is given in block
matrix form as

$\hat{U}_{Bell}\equiv\frac{1}{\sqrt{2}}\begin{bmatrix}\mathbb{I}&\sigma_{x}\\\
-\sigma_{x}&\mathbb{I}\\\ \end{bmatrix}$ (16)

With a cluster state made using a $\hat{U}_{Bell}$ and a $\hat{C}_{z}$ gate,
CNOT can be implemented with only 3 qubits (Fig. 9).

Figure 9:  CNOT using a 3 qubit cluster state. Qubits $1\leftrightarrow 2$ are
entangled with a $\hat{U}_{Bell}$ gate and qubits $2\leftrightarrow 3$ are
entangled with a $\hat{C}_{z}$ gate (Source: Ref. 8)

Qubits 1 and 2 are entangled with the $\hat{U}_{Bell}$ gate (Eq. (15)) and
qubits 2 and 3 are entangled with a $\hat{C}_{z}$ gate to form a 3 qubit
cluster state to implement CNOT. The initial state of the qubits is

$\left|\Psi_{0}\right\rangle\equiv\left|i_{1}\right\rangle\left|0\right\rangle\left|c_{3}\right\rangle$
(17)

On applying the $\hat{U}_{Bell}$ and $\hat{C}_{z}$ gates, this evolves into

$\left|\Psi_{e}\right\rangle=\left[\left|i_{1}\right\rangle\left|0\right\rangle+(-1)^{i+c}\left|i\oplus
1\right\rangle\left|1\right\rangle\right]\otimes\left|c_{3}\right\rangle$ (18)

Measurement of qubit 1 in Pauli-X basis followed by Hadamard operation on
qubit 2 yields

$\left|\Psi_{m}\right\rangle=\mathcal{F}_{2,3}\left|m\right\rangle\left|i\oplus
c\right\rangle\left|c_{3}\right\rangle$ (19)

where $m$ is the measurement outcome and
$\mathcal{F}_{2,3}\equiv\left(\sigma^{3}_{z}\sigma^{2}_{x}\sigma^{2}_{z}\right)^{m}$
is the measurement based correction. The authors estimate the fidelity of this
CNOT to be $\approx 96.5\%$ for an evaluation time of $2.5\mu s$ which is a
significant improvement over the 4 qubit CNOT (Eq. (14)) with a $25\%$
reduction in number of qubits. Beyond CNOT, the cluster state created using
only $\hat{U}_{Bell}$ gates has other useful characteristics of being - a)
Maximally connected (measuring all but 2 qubits of the cluster results in a
Bell state) and b) Maximally persistent (minimal product state decomposition
has $2^{N}$ terms for an N qubit cluster state) [8].

###  II.3 MBQC with Trapped Ions

In the article [Ref. 9], authors use strings of ${}^{40}\mathrm{Ca}^{+}$ ions
in a linear Paul trap to create one and two dimensional cluster states. They
employ MBQC on these cluster states to demonstrate universal one and two qubit
gates. Beyond quantum computation, they also demonstrate Quantum Error
Correction (QEC) on the generated cluster states using MBQC.

####  II.3.1 Cluster States with Trapped Ions

The electron states $\left|D_{5/2},m=+3/2\right\rangle$ and
$\left|S_{1/2},m=+1/2\right\rangle$ of ${}^{40}\mathrm{Ca}^{+}$ ions are used
as qubit states $\left|1\right\rangle$ and $\left|0\right\rangle$ respectively
($\lambda=729$ nm) [9]. The $n$ ionic qubits in a linear Paul trap are
initialized in state $\left|1\right\rangle^{\otimes n}$ via optical pumping.
The axial center of mass and stretch vibrational modes are initialized in
ground state using resolved sideband cooling. The cluster states are created
from the ion string using three types of interactions - a) Molmer Sorenson
interaction which is a long range qubit-qubit interaction of the form
$M(\theta)\equiv\exp{\left(-i\theta\sum_{a<b}X_{a}X_{b}\right)}$, b) Single
qubit phase flips
$G_{k}(\theta)\equiv\exp{\left(-i\frac{\theta}{2}Z_{k}\right)}$ and c) Hiding
pulses (in this case, hiding qubit state $\left|1\right\rangle$ in a different
Zeeman level $\left|D_{5/2},m=+5/2\right\rangle$) of the form
$F_{h}\equiv\exp{\left(-i\pi/4\sum_{k}X_{k}\right)}$.

Figure 10:  Quantum circuit to generate a 1-d cluster state with 4 trapped ion
qubits using the three types of interactions $(M,G,F)$. (Source: Ref. 9)

Fig. 10 [9] illustrates an equivalent quantum circuit to generate a 4 qubit
1-d cluster state using these interactions as gates. The resultant cluster
state, $\left|E_{LC_{4}}\right\rangle$, is equivalent to
$\left|{LC_{4}}\right\rangle$ (described by Eq. (1)) up to single qubit
unitary operations.

$\begin{split}\left|E_{LC_{4}}\right\rangle\equiv\frac{1}{\sqrt{8}}(&\left|0000\right\rangle-i\left|0011\right\rangle-\left|0101\right\rangle\\\
-i&\left|0110\right\rangle+i\left|1001\right\rangle-\left|1010\right\rangle\\\
-i&\left|1100\right\rangle-\left|1111\right\rangle)\end{split}$ (20)

On performing quantum tomography of the cluster state density matrix, authors
found its fidelity with respect to ideal state as being $0.841\pm 0.006$.

####  II.3.2 Universal Gates with Trapped Ion Cluster States

For implementation of single qubit gates, decomposition into Euler angles and
measurements, described by Eq. (5) and (6), is employed with the 1-d cluster
state $\left|E_{LC_{n}}\right\rangle$. Using quantum state tomography, the
authors obtained an average fidelity of $0.92\pm 0.01$ for single qubit gates.

For illustration of two qubit gates, qubits 1 and 4 of
$\left|{LC_{4}}\right\rangle$ act as inputs which are initially in state
$\left|++\right\rangle$. Measuring them in bases $\mathcal{B}(\alpha)$ and
$\mathcal{B}(\beta)$ (Eq. (6)) results in their rotations about the Pauli-Z
axis, followed by Hadamard transformation. These are subjected to the
teleported $\hat{C}_{z}$ gate and results are read out from qubits 2 and 3
(Fig. 11). The measurement based correction for this gate is
$\mathcal{F}=(\sigma^{2}_{x}\sigma^{3}_{z})^{s1}(\sigma^{3}_{x}\sigma^{2}_{z})^{s4}$,
where $s1$ and $s4$ are the measurement outcomes. Using this scheme, an
entangled state $(\alpha=\pi/2,\beta=-\pi/2)$ and a separable state
$(\alpha=0,\beta=0)$ were generated. Quantum state tomography yielded
respective fidelities of $0.88\pm 0.02$ and $0.83\pm 0.01$ [9].

Figure 11:  Two qubit quantum gate implemented using a
$\left|{LC_{4}}\right\rangle$ cluster state. (Source: Ref. 9)

These implementations of a $\hat{C}_{z}$ gate and single qubit rotations form
a universal gate set for quantum computation.

####  II.3.3 Quantum Error Correction with Cluster States

Using cluster states, it is possible to implement a phase flip code capable of
correcting full phase flips of $(n-1)/2$ of qubits forming the $n$-qubit code-
word ($n$ is odd) [9]. The cluster state employed for error correction (Fig.
12) has the form

$\begin{split}\left|EC_{n}\right\rangle\equiv&\left(\left|0\right\rangle_{A}\left|+\right\rangle^{\otimes
n}+\left|1\right\rangle_{A}\left|-\right\rangle^{\otimes
n}\right)\left|0\right\rangle_{B}\\\
+&\left(\left|0\right\rangle_{A}\left|-\right\rangle^{\otimes
n}+\left|1\right\rangle_{A}\left|+\right\rangle^{\otimes
n}\right)\left|1\right\rangle_{B}\end{split}$ (21)

Figure 12:  $\left|EC_{5}\right\rangle$ cluster state for implementing
$5$-qubit phase flip code. The state of qubit $A$ gets encoded in a code-word
formed by qubits $C_{1}\dots C_{5}$, which can be error corrected at the
output qubit $B$ based on the error syndrome. (Source: Ref. 9)

The input qubit $A$ is measured in the eigenbasis of the state to be encoded.
This is followed by a measurement of code-word qubits in the Pauli-X basis
which both a) teleports the encoded state to the output qubit $B$ and b)
reveals the error syndrome for correction of any phase flip errors before
measurement. From Eq. (20), it can be seen that if $>(n-1)/2$ of code-word
qubits are measured in $\left|+\right\rangle$ state, no recovery operation is
required. If, however, $>(n-1)/2$ of code-word qubits are measured in
$\left|-\right\rangle$ state, the output state needs to be corrected by
applying a $\sigma^{B}_{x}$ operation on qubit $B$.

##  III Discussion

MBQC achieves universal quantum computation through projective single qubit
measurements on a highly entangled cluster state. This simplicity of
computation comes at the expense of a large number of qubits forming the
cluster state and their coherent control. Trapped ion qubits have the highest
reported fidelities ($\approx 99\%$) for single and two qubit gates [11].
However, controlling a large number of such qubits in a single trap while
maintaining coherence is extremely challenging. The most number of trapped ion
qubits that have been coherently controlled so far are $\approx 20$ [10] which
can implement a maximum of 5 CNOT gates on a cluster state. Superconducting
qubits have reasonably good gate fidelities ($\approx 96\%$) [8] and have
better scalability ($\approx 127$ qubits [12]) than trapped ion qubits. While
this may be sufficient for proof of concept algorithms, it is far from being
useful in creating large enough cluster states for real world computations.
Also, larger superconducting quantum systems require some form of error
correction to reduce propagation of noise and effects of decoherence. This
increases the number of physical qubits required per implemented logical
qubit, further reducing the number of gates that can be faithfully implemented
with MBQC. Cluster states using continuous variable states of photon modes
have lower gate fidelities ($\approx 93\%$ for gate noise factor of 6 dB and
best reported initial squeezing variance of -17 dB with respect to vacuum) [4]
than trapped ion and superconducting qubits. However, there is no fundamental
limit to the size of squeezed photon cluster states with temporal mode
encoding ($\approx 10^{6}$ mode optical cluster state has been experimentally
realized [7]). Quantum error correction with GKP qubit encoding [6, 4] (not
yet experimentally realized in the optical spectrum) could make up for the
loss in individual gate fidelities and large scale deterministic quantum
computation could be achieved.

##  IV Conclusion

The past decade has seen significant advances in physical realizations of
qubits and the scale at which they can be coherently controlled on various
platforms ranging from the most commercially deployed - superconducting and
trapped ion quantum systems to those employing continuous variable states of
squeezed photons which have emerged only recently. Measurement based quantum
computation is an approach to build a programmable quantum computer by
classically adapting single qubit measurements, based on previous outcomes, on
a highly entangled cluster state comprised of a large number of qubits. In
this article, we review three MBQC implementations, each utilizing a different
quantum computing technology viz., superconducting qubits, trapped ion qubits
and spatio-temporal modes of squeezed photons. While the latter approach has
lower gate fidelities among the three, the ability to create a very large
photonic cluster state using such encoding allows error correction to be
employed efficiently on this platform. This could make large scale universal
MBQC possible in the long run.

## References

  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, A one-way quantum computer, Physical Review Letters 86, 5188–5191 (2001).
  * Wei [2021] T.-C. Wei, Measurement-based quantum computation, Oxford Research Encyclopedia of Physics 10.1093/acrefore/9780190871994.013.31 (2021).
  * Nielsen and Chuang [1997] M. A. Nielsen and I. L. Chuang, Programmable quantum gate arrays, Physical Review Letters 79, 321–324 (1997).
  * Larsen  _et al._ [2021] M. V. Larsen, X. Guo, C. R. Breum, J. S. Neergaard-Nielsen, and U. L. Andersen, Deterministic multi-mode gates on a scalable photonic quantum computing platform, Nature Physics 17, 1018–1023 (2021).
  * Larsen  _et al._ [2020] M. V. Larsen, J. S. Neergaard-Nielsen, and U. L. Andersen, Architecture and noise analysis of continuous-variable quantum gates using two-dimensional cluster states, Physical Review A 102, 10.1103/physreva.102.042608 (2020).
  * Gottesman  _et al._ [2001] D. Gottesman, A. Kitaev, and J. Preskill, Encoding a qubit in an oscillator, Physical Review A 64, 10.1103/physreva.64.012310 (2001).
  * Yoshikawa  _et al._ [2016] J.-I. Yoshikawa, S. Yokoyama, T. Kaji, C. Sornphiphatphong, Y. Shiozawa, K. Makino, and A. Furusawa, Invited article: Generation of one-million-mode continuous-variable cluster state by unlimited time-domain multiplexing, APL Photonics 1, 060801 (2016).
  * Albarrán-Arriagada  _et al._ [2018] F. Albarrán-Arriagada, G. A. Barrios, M. Sanz, G. Romero, L. Lamata, J. C. Retamal, and E. Solano, One-way quantum computing in superconducting circuits, Physical Review A 97, 10.1103/physreva.97.032320 (2018).
  * Lanyon  _et al._ [2013] B. P. Lanyon, P. Jurcevic, M. Zwerger, C. Hempel, E. A. Martinez, W. Dür, H. J. Briegel, R. Blatt, and C. F. Roos, Measurement-based quantum computation with trapped ions, Physical Review Letters 111, 10.1103/physrevlett.111.210501 (2013).
  * Friis  _et al._ [2018] N. Friis, O. Marty, C. Maier, C. Hempel, M. Holzäpfel, P. Jurcevic, M. B. Plenio, M. Huber, C. Roos, R. Blatt, and et al., Observation of entangled states of a fully controlled 20-qubit system, Physical Review X 8, 10.1103/physrevx.8.021012 (2018).
  * Ballance  _et al._ [2016] C. Ballance, T. Harty, N. Linke, M. Sepiol, and D. Lucas, High-fidelity quantum logic gates using trapped-ion hyperfine qubits, Physical Review Letters 117, 10.1103/physrevlett.117.060504 (2016).
  * Ball [2021] P. Ball, First quantum computer to pack 100 qubits enters crowded race, Nature 599, 542–542 (2021).