# On Aspects of Spontaneous Symmetry Breaking in Rindler and Anti-de Sitter
Spacetimes for the $O(N)$ Linear Sigma Model

Pallab Basu<EMAIL_ADDRESS>Mandelstam Institute for Theoretical
Physics, University of Witwatersrand, Johannesburg, South Africa  S R Haridev
<EMAIL_ADDRESS>Prasant Samantray
<EMAIL_ADDRESS>BITS- Pilani Hyderabad Campus,
Jawahar Nagar, Shamirpet Mandal, Secunderabad, 500078, India

###### Abstract

We investigate aspects of spontaneous breakdown of symmetry for $O(N)$
symmetric linear sigma model in the background of Rindler and Anti-de Sitter
spacetimes respectively. In the large $N$ limit, by computing the one-loop
effective action, we report that in three dimensional Rindler space, there is
a phase transition from the disordered phase to an ordered phase past a
certain critical Rindler acceleration parameter ‘$a$’. Connections with finite
temperature field theory results are established, thereby further reinforcing
the idea that Rindler space can indeed be a proxy for Minkowski spacetime with
finite temperature. We extend our calculations to Anti-de Sitter space in
various dimensions and observe that symmetry is broken in three dimensions,
but not in four dimensions. We discuss the implications of our results.

$O(N)$ Linear sigma model, Spontaneous symmetry breaking, Accelerated
observer, Anti-de Sitter space

††preprint: APS/123-QED

##  I Introduction

The study of Quantum field theory (QFT) in curved spacetimes has a long and
illustrative history of nearly half a century, including path-breaking works
like Hawking’s derivation of black hole radiation [1]. In these works, the
gravitational back-reaction of quantum fields is often neglected, and gravity
and the curved spacetime serve only as a classical arena where the quantum
field resides. We will call this approximation scheme: a probe limit. However,
even within the approximation scheme of a probe limit, important physics like
black hole radiation is demonstrated. Here in this work, following the same
general theme of QFT in a curved spacetime, we would take up certain
questions, namely in the context of spontaneous symmetry breaking and study
these questions [2, 3, 4]. Spontaneous symmetry breaking is not only the
central pillar in our state of the art understanding of standard model [5],
but the same physical mechanism serves as a bedrock for superconductivity and
other related phenomena in condensed matter physics [6]. Also, the breakdown
of spontaneous symmetry and associated phase transitions play important roles
in cosmology [7, 8, 9]. Details of such calculations in general curved
spacetimes can be found in [10, 11, 12, 13, 14].

The precise model we would concentrate on is a $O(N)$ symmetric linear sigma
model with $N$ (usally $N\gg 1$) scalar fields. The spontaneous symmetry
breaking in this model was studied analytically in flat spacetime [15]. It is
to be mentioned that large $N$ $O(N)$ sigma models are one of the few examples
where dynamical symmetry breaking could be studied non-perturbatively in the
$\phi^{4}$ coupling. Actually a large $N$ saddle point calculation shows a
breaking of $O(N)$ symmetry in three dimensional linear sigma models. Here, we
would like to study how the physics of large-$N$ sigma models are affected by
curved backgrounds and spacetimes with an event horizon.

To that end, we focus on Anti-de Sitter (AdS space) and Rindler space for
concreteness. AdS spaces have been used heavily in the context of gauge-
gravity correspondence, or holography [16]. Even in the context of holography,
QFT phenomena like superconductivity have already been modeled/discussed in a
probe limit [17]. Another spacetime we would look at is the Rindler space.
Despite not being curved, Rindler space is interesting in its own right as it
possesses an event horizon and, as an extension - a temperature as well
(Fulling–Davies–Unruh effect [18, 19]). Additionally, it is to be noted
Rindler space and AdS appear as a near-horizon geometry of non-extremal and
extremal black holes, respectively.

The plan of the paper is as follows: In section II, we outline the $O(N)$
symmetric sigma model in large $N$ limit for an arbitrary spacetime. In
sections III and IV, we calculate the one loop effective potential for Rindler
and in Anti-de Sitter spacetimes in various dimensions and consider scenarios
for spontaneous symmetry breaking/restoration and phase transitions. Finally,
we summarize our results in section V and discuss their implications.

##  II O(N) symmetric linear sigma model in the large $N$ limit

The $O(N)$ symmetric scalar field with $\lambda\phi^{4}$ type interaction is
described by the Euclidean action [15, 20, 21, 22, 23]

$\displaystyle S=\int
dv_{x}\;\left(\frac{1}{2}g^{\mu\nu}\partial_{\mu}\phi\partial_{\nu}\phi+\frac{1}{2}m_{0}^{2}\phi^{2}+\frac{\lambda_{0}}{8N}\left(\phi^{2}\right)^{2}\right),$
(1)

where $\phi$ is an $N$-component field, $\phi^{2}=\phi.\phi$ and
$dv_{x}=d^{d}x\sqrt{g}$ is the $d$ dimensional invariant measure. One can
introduce an auxiliary field to the theory which does not affect the dynamics
of the field as [20, 15]

$\displaystyle S=\int
dv_{x}\Bigg{(}\frac{1}{2}\phi\left(-\nabla^{2}+\sigma\right)\phi-\frac{N}{2\lambda_{0}}\sigma^{2}+\frac{Nm_{0}^{2}}{\lambda_{0}}\sigma\Bigg{)},$
(2)

where $\nabla^{2}$ is the $d$ dimensional Laplacian. Then the partition
function for the theory is

$\displaystyle Z$ $\displaystyle=\int D\phi D\sigma~{}e^{-S[\phi,\sigma]}.$
(3)

The path integral over $\phi$ in Eq. 3 can be evaluated using the standard
Gaussian integral, which gives

$\displaystyle Z$ $\displaystyle=\int
D\sigma\;e^{-\frac{N}{2}\log\left(\det\left(-\bar{\nabla}^{2}+\bar{\sigma}\right)\right)-\int
dv_{x}\left(-\frac{N}{2\lambda_{0}}\sigma^{2}+\frac{Nm_{0}^{2}}{\lambda_{0}}\sigma\right)}$
(4) $\displaystyle=\int D\sigma\;e^{-S_{eff}},$

where $\bar{O}=O/\mu^{2}$ for any symbol ‘$O$’ and with $\mu$ as some
arbitrary constant with the dimension of mass and $S_{eff}$ is the effective
action and is given as

$\displaystyle S_{eff}=$
$\displaystyle\frac{N}{2}\log\left(\det\left(-\bar{\nabla}^{2}+\bar{\sigma}\right)\right)$
(5) $\displaystyle+\int
dv_{x}\left(-\frac{N}{2\lambda_{0}}\sigma^{2}+\frac{Nm_{0}^{2}}{\lambda_{0}}\sigma\right)$
$\displaystyle=$ $\displaystyle\frac{N}{2}\int
dv_{x}\;\log\left(-\bar{\nabla}_{x}^{2}+\bar{\sigma}\right)$
$\displaystyle+\int
dv_{x}\left(-\frac{N}{2\lambda_{0}}\sigma^{2}+\frac{Nm_{0}^{2}}{\lambda_{0}}\sigma\right).$

If the theory consists of a large number of scalar fields
($N\rightarrow\infty$), the dominant contribution to $Z$ comes from the saddle
point of $S_{eff}$. One can evaluate the effective action and the
corresponding effective potential ($V_{eff}$) around the saddle point as

$\displaystyle V_{eff}$
$\displaystyle=\frac{N}{2}\log\left(-\bar{\nabla}_{x}^{2}+\bar{\sigma}\right)-\frac{N}{2\lambda_{0}}\sigma^{2}+\frac{Nm_{0}^{2}}{\lambda_{0}}\sigma.$
(6)

Note that quantum corrections does not involve $m_{0}$ or $\lambda_{0}$ in it.
We can rewrite the logarithm of an operator using the coincident limit of the
corresponding Euclidean Green’s function as [24, 25, 26, 27, 28]

$\displaystyle V_{1}$
$\displaystyle=\frac{N}{2}\log\left(-\bar{\nabla}_{x}^{2}+\bar{\sigma}\right)$
(7) $\displaystyle=\frac{N}{2}\int_{0}^{\sigma}dm^{2}\;\lim_{u\rightarrow
0}G\left(u;m^{2}\right).$

Here $G\left(u,m^{2}\right)$ is the Euclidean propagator of a massive scalar
field of mass $m$ in $d$ dimensional space and $u$ is the invariant distance.
In the coincident limit ($u\rightarrow 0$) propagator diverges. For a
renormalizable theory, looking at the classical action (Eq. 2) we can write
the renormalization conditions as

$\displaystyle\frac{dV_{eff}}{d\sigma}\Big{|}_{\sigma\rightarrow\mu^{2}}$
$\displaystyle=\frac{Nm^{2}}{\lambda},$ (8a)
$\displaystyle\frac{d^{2}V_{eff}}{d\sigma^{2}}\Big{|}_{\sigma\rightarrow\mu^{2}}$
$\displaystyle=-\frac{N}{\lambda},$ (8b)

where $\lambda$ and $m$ are the renormalized parameters. Here $\mu$ is an
arbitrary constant with dimensions of energy and in possible cases we take
$\mu=0$. After renormalization, the total potential ($V$) is

$\displaystyle V=\frac{1}{2}\sigma\phi^{2}+V_{eff}^{ren},$ (9)

where $V_{eff}^{ren}$ is the renormalized effective potential. The extreme of
the total potential is determined by stationary points of $V$, $i.e.$,

$\displaystyle\frac{\partial V}{\partial\sigma}$ $\displaystyle=0,$ (10a)
$\displaystyle\frac{\partial V}{\partial\phi}$ $\displaystyle=0.$ (10b)

We can use Eq. 10a for writing $\sigma$ as a function of $\phi$ and can use
the result to write $V$ as a function of $\phi$ alone. Then the condition for
extrema of the potential is

$\displaystyle\frac{dV}{d\phi}$ $\displaystyle=\frac{\partial
V}{\partial\phi}+\frac{\partial
V}{\partial\sigma}\frac{\partial\sigma}{\partial\phi}$ (11)
$\displaystyle=\frac{\partial V}{\partial\phi}=0,$

where in the second line of Eq. 11 we use Eq. 10a. Using Eq. 11 in Eq. 9 gives

$\displaystyle\frac{dV}{d\phi}=\sigma\phi.$ (12)

Now the minima of the potential can occur at $\phi=0$ or $\sigma=0$. The field
configuration corresponds to $\phi=0$ minima is $O(N)$ symmetric. But the
field configuration corresponds to $\sigma=0$ is not $O(N)$ symmetric. So, if
the global minima of the potential are at $\sigma=0$, then one says the theory
exhibits spontaneous symmetry breaking [29, 30, 31].

The formalism outlined here is generic. The $O(N)$ symmetric linear sigma
model at large $N$ limit in Minkowski spacetime is well studied in the
literature [20, 21, 22]. In flat spacetime, the $O(N)$ symmetric linear sigma
model exhibits spontaneous symmetry breaking in three dimensions [20], and
there is no spontaneous symmetry breaking in two, and four dimensions [20, 21,
22].

##  III Rindler space

We now focus on studying spontaneous symmetry breaking of $O(N)$ symmetric
linear sigma model in the large $N$ limit in Rindler space. Since Rindler
space is the spacetime, as perceived by an uniformly accelerated observer in
Minkowski spacetime, the idea is to check if observer dependence plays a role
in the effects of spontaneous symmetry breaking. For the case of $N=1$,
$\lambda\phi^{4}$ theory, the spontaneously broken $\mathrm{Z}_{2}$ symmetry
is restored for a uniformly accelerated observer at a certain critical
acceleration [8, 32, 33]. To check whether similar behavior persists in the
large $N$ limit for the linear sigma model, we start by considering the theory
in Rindler coordinates [34, 35]. The Rindler metric for a $d+2$ dimensional
space with Euclidean signature is given as

$\displaystyle
ds^{2}=\xi^{2}d\tau^{2}+d\xi^{2}+(dx^{1})^{2}+...+(dx^{d})^{2}.$ (13)

Note that in this choice of coordinates, $\tau$ is dimensionless. As we are
interested in the qualitative behavior of the effective potential, all one has
to do is to read off the results from [33] with $M^{2}$ replaced with $\sigma$
as

$\displaystyle V_{eff}^{ren}$
$\displaystyle=\frac{N}{2\lambda}\sigma^{2}+\frac{Nm^{2}}{\lambda}\sigma-\frac{2N\sigma^{\frac{d+1}{4}}}{\left(4\pi\right)^{\frac{d+2}{2}}\pi^{\frac{3}{2}}\xi^{\frac{d+3}{2}}}K_{\frac{d+1}{2}}\left(2\alpha\right),$
(14)

where $m$ and $\lambda$ are the renormalized parameters and
$\alpha=\xi\sqrt{\sigma}$ which is a dimensionless parameter. With the
effective potential in hand, one can study the symmetry behavior of the vacuum
configurations in different dimensions.

###  III.1 Four dimensions

In four dimensions, the near-horizon limit of the effective potential is

$\displaystyle\lim_{\alpha\rightarrow
0}V_{eff}^{ren}\Big{|}_{d=2}=-\frac{N}{2\lambda}\sigma^{2}+\frac{Nm^{2}}{\lambda}\sigma+\frac{Na^{2}}{16\pi^{3}}\sigma,$
(15)

where we choose the trajectory $\xi=1/a$. Also, one can use Eq. 14 with $d=2$
in renormalization condition (Eq. 8a) to see the effective mass as

$\displaystyle m_{eff}^{2}=m^{2}+\frac{a^{2}}{16\pi^{3}},$ (16)

where there is a correction to the mass squared due to acceleration. However,
the effective potential for the linear sigma model in large $N$ limit is
double valued in four dimensional Minkowski space and the global minima of the
potential is symmetric under $O(N)$ transformation for all values of $m$ and
$\lambda$ [21, 22]. So, there is no spontaneous symmetry breaking for linear
sigma model in large $N$ limit in standard flat space. Therefore, one can not
comment on the frame dependence of spontaneous symmetry breaking by naively
looking at Eq. 15 in four dimensions.

###  III.2 Three dimensions

It is known in the literature [20] that in three dimensions with $m^{2}<0$,
the vacuum configuration of the field is not symmetric under $O(N)$
transformations. This implies that $O(N)$ symmetry is spontaneously broken.
Similar to the $\lambda\phi^{4}$ theory [33], one can therefore expect the
restoration of $O(N)$ symmetry in accelerated frames. We can study symmetry
restoration by considering the near horizon limit of the effective potential.
In three dimensions ($d=1$ in Eq. 14), the near-horizon limit of the effective
potential is (leading order in $a$)

$\displaystyle\lim_{\alpha\rightarrow
0}V_{eff}^{ren}\Big{|}_{d=1}=-\frac{N}{2\lambda}\sigma^{2}+\frac{Nm^{2}}{\lambda}\sigma-\frac{N\sigma
a}{8\pi^{3}}\log\left(\frac{\sigma}{a^{2}}\right),$ (17)

where we choose the trajectory $\xi=1/a$. Now consider a theory with
spontaneous symmetry breaking in standard flat space ($m^{2}<0$). In
accelerated frames (from Eq. 17), the effective mass (from Eq. 8a) turns
positive after some critical acceleration or the symmetry violation disappear
for some high acceleration. Now one can try to calculate the effective mass
and the corresponding critical acceleration using Eq. 14 with $d=1$ in Eq. 8a.
But the critical acceleration will depend on some arbitrary scale $\mu$
(despite the fact that the normalized effective potential is independent of
any such scale). So, like in finite temperature field theory [36], Eq. 17 is
not very useful for predicting the critical acceleration. However, the
structure of Eq. 17 guarantees that symmetry is indeed restored for at least a
certain class of Rindler observers. Additionally, our techniques are general
and can be utilized to comment on the aspects of symmetry breaking in Rindler
space for arbitrary spacetimes.

##  IV Anti-de Sitter space

We now consider a different physical scenario. We inquire whether the
curvature of spacetime plays a role in the effects of phase transition or
symmetry breaking/restoration for the linear sigma model. To that end we
consider the $O(N)$ linear sigma model in the background of Anti-de Sitter
spacetime focusing on three and four dimensions. We consider Euclidean
$AdS_{d+1}$ with the metric

$\displaystyle
ds^{2}=\frac{L^{2}}{z^{2}}\left(dz^{2}+\sum_{i=1}^{d}dx_{i}^{2}\right),$ (18)

where $L$ is the $AdS$ scale. The bulk to bulk scalar Green’s function for
$AdS_{d+1}$ is well discussed in the literature [37, 26, 27], and we borrow
the results from [37] as

$\displaystyle G(W)$
$\displaystyle=\frac{\alpha_{0}}{L^{d-1}}W^{\Delta}\tensor{[}_{2}]{F}{{}_{1}}\left(\Delta,\Delta+\frac{1-d}{2},2\Delta-d+1;-4W\right),$
(19)

where

$\displaystyle W$ $\displaystyle=\frac{1}{2}\frac{1}{\cosh(\frac{u}{L})-1},$
(20) $\displaystyle\Delta$
$\displaystyle=\frac{d}{2}+\frac{1}{2}\sqrt{d^{2}+4m^{2}L^{2}},$
$\displaystyle\alpha_{0}$
$\displaystyle=\frac{\Gamma(\Delta)}{2\pi^{d/2}\Gamma\left(\Delta-\frac{d}{2}+1\right)},$

and $\tensor{[}_{2}]{F}{{}_{1}}$ is the usual Hypergeometric function. Note
that in the coincident limit (i.e., $u\rightarrow 0$), $W$ diverges, and
Green’s function is singular as expected. We now specialize to three and four
dimensions for our analysis.

###  IV.1 Four Dimensions

One can expand $G(W)$ around $u=0$, for the case of $d=3$ this gives

$\displaystyle\lim_{u\rightarrow 0}G(W)$
$\displaystyle=\frac{1}{12\pi^{2}}\left(\frac{3}{u^{2}}-\frac{16+3\Delta(\Delta-5)}{4L^{2}}+\frac{3}{4L^{2}}\times\right.$
(21)
$\displaystyle\left.\left(\Delta-2\right)\left(\Delta-1\right)\left(2H_{\Delta-3}+2\log\left(\frac{u}{2L}\right)\right)\right),$

where $H_{z}$ is the harmonic number. Using Eq. 21 we can calculate $V_{1}$
(see Eq. 7) as

$\displaystyle V_{1}$
$\displaystyle=\frac{N}{8L^{2}\pi^{2}}\left(\sigma\left(\gamma+\frac{L^{2}}{u^{2}}-\frac{5}{12}+\frac{\beta}{3}+\log\left(\frac{u}{2L}\right)\right.\right.$
(22)
$\displaystyle\left.\left.+\frac{1}{2}\log\left(\Gamma(\beta)\right)+\beta\log\left(\Gamma(\beta)\right)-3\psi\left(-2,\beta\right)\right)\right.$
$\displaystyle\left.+\frac{L^{2}\sigma^{2}}{4}\left(\log\left(\frac{u}{2L}\right)+\gamma-\frac{1}{2}\right)-\frac{13}{2L^{2}}\psi\left(-2,\beta\right)\right.$
$\displaystyle\left.+\frac{\beta}{L^{2}}\left(\frac{3}{4}+2\log\left(\Gamma(\beta)\right)+6\psi\left(-3,\beta\right)\right)\right.$
$\displaystyle\left.+\frac{1}{L^{2}}\left(\log\left(\Gamma(\beta)\right)-6\psi\left(-4,\beta\right)+3\psi\left(-3,\beta\right)\right)\right),$

where $\gamma$ is the Euler’s constant, $\psi$ is the polygamma function and
for notational simplicity we choose

$\displaystyle\beta=-\frac{1}{2}+\frac{1}{2}\sqrt{9+4L^{2}\sigma}.$ (23)

Eq. 22 regularizes the effective potential and the divergences in the
effective potential is in linear and quadratic powers of $\sigma$ [27, 26]
allowing us to renormalize the theory by redefining $m_{0}$ and $\lambda_{0}$.
Using the renormalization condition (Eq. 8a), we can write

$\displaystyle\frac{1}{48L^{2}\pi^{2}}+\frac{1}{8\pi^{2}u^{2}}+\frac{m_{0}^{2}}{\lambda_{0}}+\frac{1}{8L^{2}\pi^{2}}\log\left(\frac{u}{2L}\right)=\frac{m^{2}}{\lambda},$
(24)

and Eq. 8b gives

$\displaystyle\frac{1}{144}-\frac{1}{96\pi^{2}}-\frac{1}{\lambda_{0}}+\frac{1}{16\pi^{2}}\log\left(\frac{u}{2L}\right)=-\frac{1}{\lambda}.$
(25)

Using Eq. 24 and Eq. 25 one can write the renormalized effective potential as

$\displaystyle V_{eff}^{ren}$
$\displaystyle=\frac{Nm^{2}\sigma}{\lambda}-\frac{N\sigma^{2}}{2\lambda}+\frac{N}{8L^{2}\pi^{2}}\left(\frac{\sigma^{2}L^{2}}{4}\left(\gamma-\frac{1}{3}-\frac{\pi^{2}}{9}\right)\right.$
(26)
$\displaystyle\left.+\frac{\sigma}{2}\left(2\gamma+\frac{2\beta}{3}+\left(2\beta+1\right)\log\left(\Gamma(\beta)\right)-6\psi\left(-2,\beta\right)\right.\right.$
$\displaystyle\left.\left.-\frac{7}{6}\right)+\frac{\beta}{L^{2}}\left(\frac{3}{4}+2\log\left(\Gamma(\beta)\right)+6\psi\left(-3,\beta\right)\right)\right.$
$\displaystyle\left.+\frac{1}{L^{2}}\left(\log\left(\Gamma(\beta)\right)-6\psi\left(-4,\beta\right)+3\psi\left(-3,\beta\right)\right.\right.$
$\displaystyle\left.\left.-\frac{13}{2}\psi\left(-2,\beta\right)\right)\right).$

Now using Eq. 9 one can calculate the total potential. As a check, in the
limit $L\rightarrow\infty$, $V$ matches with the flat space potential as [20,
21, 22]

$\displaystyle\lim_{L\rightarrow\infty}V=\frac{1}{2}\sigma\phi^{2}+\frac{m^{2}N\sigma}{\lambda}-\frac{N\sigma^{2}}{2\lambda}+\frac{N\sigma^{2}}{64\pi^{2}}\log\left(\frac{\sigma}{\mu^{2}}\right),$
(27)

where we choose $\mu=1/L$ as the arbitrary energy scale.

####  IV.1.1 Ground state

In order to understand spontaneous symmetry breaking, we begin by determining
the stationary points of the potential $V$. Substituting Eq. 26 in Eq. 10a
gives

$\displaystyle\phi^{2}(\sigma)$
$\displaystyle=\frac{N}{72L^{2}\pi^{2}\lambda}\Bigg{(}-144\pi^{2}L^{2}m^{2}+3\lambda
L^{2}\sigma+\lambda\pi^{2}L^{2}\sigma$ (28)
$\displaystyle+144L^{2}\pi^{2}\sigma-9\lambda\left(\beta+1+L^{2}\sigma\right)H_{\beta-1}\Bigg{)}.$

Figure 1: A plot of $\phi^{2}$ versus $\sigma$ for $m^{2}>0$.

The variation of $\phi^{2}$ as a function of $\sigma$ is shown in Fig. 1. From
Fig. 1 we can see that $\phi^{2}$ attains a maximum value $\phi_{max}^{2}$ at
$\sigma=\sigma_{0}$ and monotonically decreases after that. This is similar to
the case in four dimensional flat space and it indicates that $V(\phi^{2})$ is
a double valued function of $\phi^{2}$ for $\phi^{2}<\phi^{2}_{max}$ [21, 22].

The field configuration with minimum potential determines the ground state of
the theory. One can find the ground state by comparing the values of the
potential at possible minima. Consider the minima at $\sigma=0$

$\displaystyle V(0)=-\frac{0.003N}{L^{4}}.$ (29)

But at this point

$\displaystyle\phi^{2}(0)=-\frac{2m^{2}N}{\lambda}.$ (30)

For $m^{2}>0$ the field becomes complex, therefore $\sigma=0$ requires
$m^{2}\leq 0$. From Fig. 1, we can see that $\phi=0$ for both $\sigma_{1}$ and
$\sigma_{2}$. For $m^{2}<0$, and $\phi^{2}(0)>0\implies\sigma_{1}<0$ which is
not in the possible range of $\sigma\in[0,\infty)$. So the only possible other
minima of the potential is at $\sigma_{2}$. From Eq. 9

$\displaystyle V(0)$ $\displaystyle=V_{eff}^{ren}(\sigma).$ (31)

For small values of $\sigma$

$\displaystyle\lim_{\sigma\rightarrow
0}V_{eff}^{ren}(\sigma)=V(0)+\frac{Nm^{2}\sigma}{\lambda}+O(\sigma^{2}).$ (32)

So for $m^{2}<0$, $V_{eff}$ decreases from $V(0)$ to $V(\sigma_{2})$. Then

$\displaystyle V(\sigma_{2})<V(0).$ (33)

So, for $m^{2}<0$ the global minima of the potential is at $\phi=0$.
Therefore, the global minima of the potential is a symmetric one and there is
no spontaneous symmetry breaking.

Now, if $m^{2}>0$ the minimum of the potential can only occur at $\phi=0$.
Subsequently, there is no spontaneous symmetry breaking in the system in this
case. Now the minimum of the potential can be at $\sigma_{1}$ or $\sigma_{2}$.
For $m^{2}>0$, as a function $V_{ren}^{eff}$ starts to increase from
$\sigma=0$ (from Eq. 32) and reaches its first extremum at $\sigma_{1}$ and
then decreases till $\sigma_{2}$. So

$\displaystyle V(\sigma_{2})<V(\sigma_{1}),$ (34)

which makes $\sigma_{2}$ the global minima. Now for $m^{2}=0$ we can repeat
the same arguments for $m^{2}<0$ and conclude that $\phi(\sigma_{2})$ is the
global minimum configuration of the field.

In conclusion, in four dimensional $AdS$ there is no spontaneous symmetry
breaking for any values of $m^{2}$ with $\lambda>0$.

###  IV.2 Three Dimensions

The computation for three dimensional case is similar to that of four
dimensions. In three dimension, we can expand the propagator near $u=0$ as
(from Eq. 19)

$\displaystyle\lim_{u\rightarrow 0}G(W)=\frac{1}{4\pi L}+\frac{1}{4\pi
u}-\frac{\Delta}{4\pi L}+O(u),$ (35)

where $\Delta$ is defined in Eq. 20. Substituting this in Eq. 7 one can
calculate $V_{1}$ as

$\displaystyle V_{1}=\frac{N\sigma}{8\pi
u}-\frac{N}{12L\pi}\left(\sigma+\frac{1}{L^{2}}\right)\sqrt{1+L^{2}\sigma}.$
(36)

The divergence in $V_{1}$ is proportional to linear power in $\sigma$. So, one
can renormalize it using Eq. 8a as

$\displaystyle\frac{1}{8\pi}\left(\frac{1}{u}+\frac{1}{L}\right)+\frac{m_{0}^{2}}{\lambda_{0}}=\frac{m^{2}}{\lambda}.$
(37)

Using this condition (Eq. 37), the renormalized effective potential is

$\displaystyle V_{eff}^{ren}$ $\displaystyle=\frac{N\sigma}{8\pi
L}+\frac{Nm^{2}\sigma}{\lambda}-\frac{N\sigma^{2}}{2\lambda}$ (38)
$\displaystyle-\frac{N}{12L\pi}\left(\sigma+\frac{1}{L^{2}}\right)\sqrt{1+L^{2}\sigma}.$

####  IV.2.1 Ground state

The stationary points of the potential is determined by Eq. 10. Using Eq. 10a
one can get

$\displaystyle\phi^{2}(\sigma)=-\frac{N}{4\pi
L}-\frac{2Nm^{2}}{\lambda}+\frac{2N\sigma}{\lambda}+\frac{N}{4\pi
L}\sqrt{1+L^{2}\sigma}.$ (39)

Here

$\displaystyle\frac{d\phi^{2}}{d\sigma}>0,$ (40)

which makes $\phi^{2}$ a monotonically increasing function of $\sigma$. From
Eq. 12, the stationary points of the potential $V$ occurs at $\phi=0$ or
$\sigma=0$. Consider the extremum at $\sigma=0$

$\displaystyle V(0)=-\frac{N}{12\pi L^{2}},$ (41)

For which we have

$\displaystyle\phi^{2}(0)=-\frac{2Nm^{2}}{\lambda}.$ (42)

So value of $\sigma=0$ is possible only if $m^{2}\leq 0$. If we consider
$m^{2}<0$ then from Eq. 42 $\phi^{2}(0)>0$. A monotonically increasing
function cannot reach zero starting from a positive value. Therefore, $\phi=0$
is not possible and the only possible extremum is at $\sigma=0$. As the global
minima is an asymmetric one, $O(N)$ symmetry is spontaneously broken. For
$m^{2}>0$ and $m^{2}=0$, only possible ground state is at $\phi=0$ which is a
symmetric one.

##  V Results and Discussion

We calculated the one loop effective potential for the $O(N)$ symmetric sigma
model in Rindler space in arbitrary dimensions in the large $N$ limit (Eq.
14). Interestingly we observe that in three dimensions, the broken $O(N)$
symmetry will be restored in accelerated frames after a critical acceleration
(Eq. 17). This result is analogous to that of the finite temperature results
[36, 38]. We also observe that in four dimensions, the effective mass squared
of the theory gets quantum corrected due to the existence of an acceleration
parameter ‘$a$’ having dimensions of mass. One can obtain similar conclusions
for $N=1$ theory as shown in [33]. The method for calculating the effective
potential in Rindler spacetime is for arbitrary dimensions. So one can use our
results for studying similar phenomenons in arbitrary dimensions.

These results are indicative of the fact that non-perturbative phenomena like
spontaneous symmetry breakdown/restoration is possibly observer-dependent, and
different Rindler observers report different critical values at which phase
transition occurs. Similar conclusions are obtained for standard model phase
transitions in [39]. These non-trivial results can also be mapped to the
presence of the event horizon in Rindler space which in itself is observer-
dependent, and has a temperature associated with it. In this sense, a lot of
field-theoretic results in Rindler space are in one-one correspondence with
finite temperature physics [8].

We performed similar calculations in the Anti-de Sitter space background, and
qualitative results are similar to that obtained in flat space [21, 22, 20].
In four dimensions, there is no spontaneous symmetry breaking for any values
of $m^{2}$. However, in three-dimensional AdS, we have spontaneous symmetry
breaking for $m^{2}<0$. Also, one loop quantum effects make corrections
proportional to $1/L$ and $1/L^{2}$ to the effective mass squared of the
theory in three and four dimensions, respectively. The effect of curvature,
therefore, in this context, was to essentially modify the effective mass
squared of the scalar fields. An interesting question immediately arises. If
one were to instead consider Rindler-AdS spacetime [40] which is both curved
as well as possesses an event horizon - what would be the fate of the ground
state of the linear $O(N)$ sigma model in such a spacetime? Especially
interesting would be the critical temperature at which symmetry restoration
might occur and the form of quantum mechanical corrections to the mass squared
terms. We of course reserve these questions for future work.

###### Acknowledgements.

Research of P.S is partially supported by CSIR grant 03(1350)/16/EMR-II Govt.
of India, and also by the OPERA fellowship from BITS-Pilani, Hyderabad Campus.
H. R is supported by CSIR grant 03(1350)/16/EMR-II Govt. of India.

## References

  * Hawking [1972] S. W. Hawking, Black holes in general relativity, Commun. Math. Phys. 25, 152 (1972).
  * Coleman and Weinberg [1973] S. Coleman and E. Weinberg, Radiative corrections as the origin of spontaneous symmetry breaking, Phys. Rev. D 7, 1888 (1973).
  * Parker and Toms [2009] L. Parker and D. Toms,  _Quantum Field Theory in Curved Spacetime: Quantized Fields and Gravity_, Cambridge Monographs on Mathematical Physics (Cambridge University Press, 2009).
  * Buchbinder  _et al._ [1992] I. L. Buchbinder, S. D. Odintsov, and I. L. Shapiro,  _Effective action in quantum gravity_ (1992).
  * Higgs [1964] P. W. Higgs, Broken symmetries, massless particles and gauge fields, Phys. Lett. 12, 132 (1964).
  * Anderson [1963] P. W. Anderson, Plasmons, gauge invariance, and mass, Phys. Rev. 130, 439 (1963).
  * Linde [1979] A. D. Linde, Phase transitions in gauge theories and cosmology, Reports on Progress in Physics 42, 389 (1979).
  * Padmanabhan [1983] T. Padmanabhan, Symmetry breaking in the early universe and accelerated frames, Journal of Physics A: Mathematical and General 16, 335 (1983).
  * Allen [1983] B. Allen, Phase transitions in de sitter space, Nuclear Physics B 226, 228 (1983).
  * Buchbinder and Odintsov [1985] I. L. Buchbinder and S. D. Odintsov, Effective potential and phase transitions induced by curvature in gauge theories in curved spacetime, Classical and Quantum Gravity 2, 721 (1985).
  * Markkanen  _et al._ [2018] T. Markkanen, S. Nurmi, A. Rajantie, and S. Stopyra, The 1-loop effective potential for the standard model in curved spacetime, Journal of High Energy Physics 2018, 40 (2018).
  * Moniz  _et al._ [1990] P. Moniz, P. Crawford, and A. Barroso, Spontaneous symmetry breaking in curved spacetime, Classical and Quantum Gravity 7, L143 (1990).
  * Kirsten  _et al._ [1993] K. Kirsten, G. Cognola, and L. Vanzo, Effective lagrangian for self-interacting scalar field theories in curved spacetime, Phys. Rev. D 48, 2813 (1993).
  * Elizalde and Odintsov [1994] E. Elizalde and S. Odintsov, Renormalization-group improved effective lagrangian for interacting theories in curved spacetime, Physics Letters B 321, 199 (1994).
  * Coleman [1985] S. Coleman,  _Aspects of Symmetry: Selected Erice Lectures_ (Cambridge University Press, 1985).
  * Maldacena [1999] J. Maldacena, International Journal of Theoretical Physics 38, 1113 (1999).
  * Hartnoll  _et al._ [2016] S. A. Hartnoll, A. Lucas, and S. Sachdev, Holographic quantum matter (2016).
  * Davies [1975] P. C. W. Davies, Scalar production in schwarzschild and rindler metrics, Journal of Physics A: Mathematical and General 8, 609 (1975).
  * Unruh [1976] W. G. Unruh, Notes on black-hole evaporation, Phys. Rev. D 14, 870 (1976).
  * Coleman  _et al._ [1974] S. Coleman, R. Jackiw, and H. D. Politzer, Spontaneous symmetry breaking in the $\mathrm{O}(n)$ model for large $n$, Phys. Rev. D 10, 2491 (1974).
  * Abbott  _et al._ [1976] L. F. Abbott, J. S. Kang, and H. J. Schnitzer, Bound states, tachyons, and restoration of symmetry in the $\frac{1}{N}$ expansion, Phys. Rev. D 13, 2212 (1976).
  * Kobayashi and Kugo [1975] M. Kobayashi and T. Kugo, On the Ground State of $O(N)-\lambda\phi^{2}$ Model, Progress of Theoretical Physics 54, 1537 (1975).
  * Elizalde  _et al._ [1994] E. Elizalde, K. Kirsten, and S. D. Odintsov, Effective lagrangian and the back-reaction problem in a self-interacting o(n) scalar theory in curved spacetime, Phys. Rev. D 50, 5137 (1994).
  * Candelas and Raine [1975] P. Candelas and D. J. Raine, General-relativistic quantum field theory: An exactly soluble model, Phys. Rev. D 12, 965 (1975).
  * Akhmedov and Diakonov [2022] E. T. Akhmedov and D. V. Diakonov, Free energy and entropy in rindler and de sitter space-times, Phys. Rev. D 105, 105003 (2022).
  * Inami and Ooguri [1985] T. Inami and H. Ooguri, One-Loop Effective Potential in Anti-de Sitter Space, Progress of Theoretical Physics 73, 1051 (1985).
  * Burgess and Lütken [1985] C. Burgess and C. Lütken, Propagators and effective potentials in anti-de sitter space, Physics Letters B 153, 137 (1985).
  * Birrell and Davies [1982] N. D. Birrell and P. C. W. Davies,  _Quantum Fields in Curved Space_, Cambridge Monographs on Mathematical Physics (Cambridge University Press, 1982).
  * Goldstone  _et al._ [1962] J. Goldstone, A. Salam, and S. Weinberg, Broken symmetries, Phys. Rev. 127, 965 (1962).
  * Nambu and Jona-Lasinio [1961] Y. Nambu and G. Jona-Lasinio, Dynamical model of elementary particles based on an analogy with superconductivity. i, Phys. Rev. 122, 345 (1961).
  * Zee [2003] A. Zee,  _Quantum field theory in a nutshell_ (2003).
  * Castorina and Finocchiaro [2012] P. Castorina and M. Finocchiaro, Symmetry restoration by acceleration, Journal of Modern Physics 03No.11, 6 (2012).
  * Basu  _et al._ [2023] P. Basu, H. S. R, and P. Samantray, On the observer dependence of the quantum effective potential (2023).
  * Rindler [1960] W. Rindler, Hyperbolic motion in curved space time, Phys. Rev. 119, 2082 (1960).
  * Fulling [1973] S. A. Fulling, Nonuniqueness of canonical field quantization in riemannian space-time, Phys. Rev. D 7, 2850 (1973).
  * Fujimoto  _et al._ [1987] Y. Fujimoto, A. Wipf, and H. Yoneyama, Finite temperature $\lambda$$\varphi$4 theory in two and three dimensions and symmetry restoration, Zeitschrift für Physik C Particles and Fields 35, 351 (1987).
  * Berenstein  _et al._ [1999] D. Berenstein, R. Corrado, W. Fischler, and J. Maldacena, Operator product expansion for wilson loops and surfaces in the large n limit, Phys. Rev. D 59, 105023 (1999).
  * Einhorn and Jones [1993] M. Einhorn and D. Jones, phi4 in three dimensions at finite temperature, Nuclear Physics B 398, 611 (1993).
  * Casado-Turrión and Dobado [2019] A. Casado-Turrión and A. Dobado, Triggering the qcd phase transition through the unruh effect: Chiral symmetry restoration for uniformly accelerated observers, Phys. Rev. D 99, 125018 (2019).
  * Parikh and Samantray [2018] M. Parikh and P. Samantray, Rindler-ads/cft, Journal of High Energy Physics 2018, 129 (2018).


In the near term, programming quantum computers will remain severely limited by low quantum volumes.
Therefore, it is desirable to implement quantum circuits with the fewest resources possible.
For the common Clifford+T circuits, most research is focused on reducing the number of T gates, since they are an order of magnitude more expensive than Clifford gates in quantum error corrected encoding schemes.
However, this optimization sometimes leads to more 2-qubit gates, which, even though they are less expensive in terms of fault-tolerance, contribute significantly to the overall circuit cost.
Approaches based on the ZX-calculus have recently gained some popularity in the field, but reduction of 2-qubit gates is not their focus.
In this work, we present an alternative for improving 2-qubit gate count of a quantum circuit with the ZX-calculus by using heuristics in ZX-diagram simplification.
Our approach maintains the good reduction of the T gate count provided by other strategies based on ZX-calculus, thus serving as an extension for other optimization algorithms.

Our results show that combining the available ZX-calculus-based optimizations with our algorithms can reduce the number of 2-qubit gates by as much as 40 % compared to current approaches using ZX-calculus.
Additionally, we improve the results of the best currently available optimization technique of Nam et. al <cit.> for some circuits  by up to 15 %.

§ INTRODUCTION

Many famous quantum algorithms, like Shor <cit.>, HHL <cit.> or Grover <cit.>, base upon techniques like Quantum Fourier Transformation, Quantum Phase Estimation or Amplification, respectively.
Although these algorithms provide significant (sometimes even exponential) speed-ups, current quantum chips can only execute toy problems, mostly due to the low gate fidelity.
Even for problems that can be easily solved on a state-of-the-art desktop PC, those algorithms require tens of thousands of gates, and are therefore infeasible to run on near-term quantum devices.

However, applications in quantum simulation are supposed to achieve significant improvements in quantum chemistry, material sciences, or high-energy physics on near-term devices.
With variational algorithms (e.g., QAOA <cit.> or VQE <cit.>), real-world applications like optimization problems on real quantum chips may become feasible.
While the associated speed-up is unknown for many use cases, they require only few qubits and quantum gates to achieve promising results.
Quantum Machine Learning (QML) is such an example:
Here, the combination of clever encoding strategies, variational algorithms, and classical pre- and post-processing achieves high accurate classification rates with fewer qubits compared to classical bits.

Still, even algorithms with smaller circuits cannot be executed on current devices and gate optimization is a vibrant research topic.
While global optimization of arbitrary quantum circuits is generally QMA-hard <cit.>, different algorithms like quantum optimal control <cit.> have been proposed to reduce the size of a quantum circuit.
In this context the so-called ZX-calculus <cit.> is considered a promising tool.
It provides an abstract graphical language for describing quantum systems and can be seen as an alternative to the predominant description in the Hilbert space.
We can transform any quantum circuit into a ZX-diagram equivalent, apply the rules of the ZX-calculus to simplify the diagram, and re-extract a quantum circuit from it.

§.§ Scope of this work

Our work is based on optimizing circuits with ZX-calculus, where several optimization strategies have been proposed recently <cit.>.
Currently, these strategies yield very good results for pure Clifford circuits, as well as for T gate elimination in Clifford+T circuits, which is worthwhile for fault-tolerant quantum computers with error-corrected gates.
For such devices, the cost of a T gate is sometimes estimated to be up to a hundred times higher than the cost of a CNOT gate <cit.> (even though recent studies suggest lower rates <cit.>).

However, reducing 2-qubit gates is generally of interest for quantum hardware that is not error corrected (e.g., NISQ devices) or in which quantum states do not tend to interact easily, e.g., in Photonic Quantum computing <cit.>.
A major drawback of the current ZX-calculus based strategies is that these gates in particular are not optimized very well; in fact, for many large Clifford+T circuits, the 2-qubit gate count even increases when using algorithms like the one in <cit.>.

We propose new optimization approaches especially for reducing 2-qubit gates.
To do so, we use heuristics for estimating the 2-qubit gate count in ZX-diagrams as cost functions for classical search algorithms like

* random selection and

* greedy algorithm.

By combining them with existing optimization approaches, we maintain the T gate count reduction rate and improve the total gate count and the 2-qubit gate count for most given circuits.
We evaluate the performance on circuits from the Tpar benchmark <cit.>.
We find that our optimizations can outperform existing ZX-based approaches and can additionally be used to further improve already optimized circuits.

§ BACKGROUND

Throughout this paper, we use the notation from <cit.> for quantum gates; the most essential ones are detailed in <ref> by name and matrix-, gate- and ZX-calculus-representation.
Every unitary operation can be decomposed into a combination of CNOTs and single-qubit gates <cit.>.

A well-studied example for a minimal gate set with which to approximate any unitary operation is the so-called Clifford+T set, i.e., the gate set generated by $\{H,T,CNOT\}$.
That is why many optimization algorithms target circuits generated with the Clifford+T set.

The Clifford set generated by $\{H,S,CNOT\}$ is also well-known and useful for quantum circuit simulations on classical computers, but not every unitary operation can be represented with it.
For convenience, we abbreviate some gates in the Clifford+T set, namely $X,Y,Z,S$, and $CZ$ (instead of writing, for example, $ Z = T\cdot T\cdot T\cdot T $).

§.§ ZX-Calculus

Since ZX-calculus and its optimization strategies rely on graph theory, we provide some background in <ref>.
The ZX-calculus <cit.> is a graphical language for expressing linear maps on qubits as ZX-diagrams. Relations in multi-qubit systems are often difficult to understand in Dirac notation, since the matrix size doubles with every qubit and the complex number space quickly becomes confusing.

\begin{equation}\label{eq:spiders}
\begin{aligned}
\tikzfig{greenSpider} \qquad& \tikzfig{redSpider}	\\
\text{\textit{Z-Spider}} \qquad& \text{\textit{X-Spider}}
\end{aligned}
\end{equation}

ZX-calculus provides a way to represent quantum circuits as 2-dimensional diagrams where nodes (spiders) and edges (wires) form an undirected graph.
In contrast to quantum circuits, the number of input- and output wires does not have to match, hence the resulting transformations are not necessarily unitary.
However, many important concepts in quantum mechanics follow very intuitively from this representation and we will briefly introduce the main principles.

§.§.§ Representing Quantum Circuits

\begin{equation}\label{eq:zx-circuit}
\begin{minipage}{0.5\linewidth}
\Qcircuit @C=0.5em @R=.5em @!R {
& \ctrl{1} & \qw & \qw  & \qw  & \qw \\
& \targ & \gate{Z} & \ctrl{1} & \gate{Z} & \qw \\
& \qw & \qw      & \targ    & \qw      & \qw
}\end{minipage} ~ = ~ \tikzfig{simplethreeq_zx} \\
\end{equation}

Any transformation on a single qubit can be described as a rotation around the $ X $ and $ Z $ axes.
Further, we can represent any quantum gate as a combination of $ X $- (red) and $ Z $-spiders (green) in ZX-diagrams (c.f. <ref>), of which the most important are shown in <ref>.
We call the wires on the left- and rightmost the input and output of the graph, respectively.
The three generators of the universal Clifford+T set are constructed with the H-wire, the Z-spider with phase $\pi/4$, and a combination of an empty $ X $- and $ Z $-spiders (phase $ \alpha = 0 $) representing a CNOT.
In general, we can read a ZX-diagram in any direction since only the connectivity of the spiders matters, but for comparison with common quantum circuits it is convenient to read ZX-diagrams horizontally as shown in <ref>.

Overview of important quantum gates and the respective ZX-Spiders.

§.§.§ Basic Rules

We introduce the most important transformation rules in the ZX language that are useful for optimization <cit.> in <ref>.
All ZX-rules can be applied in both directions and also apply with inverted colors.

\begin{equation*}
\tikzfig{all_rules}
\end{equation*}

The important rules in ZX-Calculus that can be used for optimization are: Identity- (i1,i2), Fusion- (f), Hadamard- (h), Bialgebra- (b), Pi- ($ \pi $), Copy- (c) and Hadamard-Decomposition (hd) rule. Each holds for all $ \alpha,\beta \in [0,2\pi] $. Due to (h) and (i2), all rules hold with the colours interchanged.

Any two Clifford diagrams (i.e., diagrams only containing spiders with a Clifford phase $ \alpha = k \cdot \frac{\pi}{2}; k \in \mathbb{Z} $) that represent the same linear map can be transformed into each other by some combination of those rules.
Recent developments have introduced rule sets where this is also possible for Clifford+T diagrams and for all ZX-diagrams <cit.>.

§ CIRCUIT OPTIMIZATION WITH ZX-CALCULUS

With the rules of ZX-calculus, the optimization of quantum circuits becomes a simplification problem on the ZX-diagram. By simplification we mean reducing the total number of either spiders or wires in a diagram in order to obtain a smaller diagram.
The general process is as follows:

* Transform the circuit to a ZX-diagram

* (optional:) transform to a graph-like diagram, i.e.:

* All spiders are Z-spiders.

* All connections are Hadamard wires.

* There are no loops.

* Inputs and outputs are the only non-Hadamard wires and are connected to at most one spider. Every spider has at most one input and one output.

* Simplify the diagram using ZX-rules.

* Extract a quantum circuit out of the ZX-diagram.

This allows powerful optimization of circuits, which are not obvious at a first glance (we provide an intuitive example in <ref>).

§.§ Diagram simplification

The presented ZX-rules allow many degrees of freedom, hence, simplification is still a difficult problem.
The term “simplification of diagrams” has to be taken with a grain of salt since decreasing the number of spiders in a diagram can also lead to more complex extracted circuits.
Since rules can be applied in both directions it is important to find terminating algorithms for diagram simplification.
A common approach has been to only use ZX-rules which decrease the total number of spiders in a diagram with every application, thus ensuring termination.

We present some common approaches, many of which are implemented in the PyZX-library <cit.>.

§.§.§ Clifford spider simplification

The core of most strategies are two rules from graph theory – namely local complementation and pivoting – which work on diagrams that are graph-like.
Both rules allow the elimination of interior Clifford spiders (phase $0,\pi/2,\pi,$ or $-\pi/2$; not connected to an input or output) from ZX-diagrams.

Local complementation ($ lc $)

\begin{equation}\label{eq:lcompRule}
%	\tikzfig{lcompRule}
\tikzfig{lcompRuleExample}
\end{equation}

In ZX-calculus, local complementation from <ref> is applicable on graph-like diagrams.
If the spider $ a $ in $ G \star a $ has a phase of $\pm\pi/2$, the phase is subtracted from those of the neighboring spiders and the spider is eliminated for simplification of the diagram as shown in <ref>.

Pivoting ($ p $)
Similarly we can eliminate a pair of spiders $uv$ with phase $0$ or $\pi$ by applying a graph-theoretic pivot $G \land uv$ (c.f. <ref>) on the diagram as in the following example ($ j,k \in \mathbb{Z} $):

\begin{equation}\label{eq:pivotRule}
\tikzfig{pivotRuleExample}
\end{equation}

§.§.§ Clifford simplification algorithm

These rules allow constructing an algorithm for graph-like diagrams which removes most interior Clifford spiders <cit.>. The procedure is as follows:

* Eliminate empty spiders with two wires using the identity rule and subsequently fuse the adjacent spiders in order to maintain a graph-like diagram.

* Apply local complementation on every spider of phase $\pm \pi/2$ and pivoting on every pair of connected spiders of phase $0$ or $\pi$ as often as possible.

* If step 2 modified the diagram, start again with step 1, else stop the iteration.

That allows us to remove every interior spider with phase $\pm \pi/2$ and every pair of connected spiders with phase $0$ or $\pi$.
However, after simplification some interior Clifford spiders with phase $0$ or $\pi$ may remain.

§.§.§ Phase gadget simplification (p2)

\begin{equation}\label{eq:pivot_phase_gadget}
\tikzfig{phase_gadget1}
\end{equation}

We can use phase gadgets to apply pivoting on a pair of spiders where one spider has a non-Clifford phase ($ \neq 0,\pi/2,\pi,-\pi/2$).
A phase gadget as defined in <cit.> is a parameterized spider with only one wire connected via Hadamard edge to a phaseless spider as in <ref>.

We can modify pivoting (<ref>) to exchange the spider with a non-Clifford phase to a phase gadget:

\begin{equation}\label{eq:pivotGadgetExample}
\tikzfig{pivotGadgetExample}
\end{equation}

With the additional rules in <ref>, we can eliminate every interior Clifford spider in a diagram <cit.>.

§.§ Circuit extraction

Extracting a quantum circuit from a simplified diagram can be challenging, since spiders with an arbitrary number of wires have no direct gate representation <cit.>.
The most general circuit extraction routine makes use of so called “flow properties” originating in measurement-based quantum computing (MBQC).
Graph-like ZX-diagrams can be seen as an extension of MBQC graph states where the phases of spiders represent measurements in either the XY, XZ or YZ plane of the Bloch sphere:

\begin{equation}\label{measurement_planes}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{l || c | c | c}
meas. plane & XY & XZ & YZ \\ \hline
meas. effect & \tikzfig{mbqc_xy} & \tikzfig{mbqc_xz} = \tikzfig{mbqc_xz-graphlike} & \tikzfig{mbqc_yz} = \tikzfig{mbqc_yz-graphlike}  \\
\end{tabular}
\renewcommand{\arraystretch}{1}
\end{equation}

Diagrams simplified with the Clifford simplification algorithm from <cit.> only contain spiders in the XY measurement plane and preserve a flow property called focused generalized flow (gflow).
Those diagrams can be extracted by converting every spider with phase $\alpha$ to an $R_z\left(\alpha\right)$ gate and a Hadamard wire as either a $H$ or $CZ$ gate or a combination of $CNOT$ gates.
As an example consider the diagrams from <ref>. Extracting the diagram on the left hand side yields the following circuit:

\begin{equation}\label{eq:extracted_circuit_unoptimized}\small
\Qcircuit @C=.25em @R=.25em @!R {
& \gate{R_Z(\alpha_1)} & \gate{H} & \ctrl{1}  & \qw  & \qw & \ctrl{1} & \gate{R_Z(j\pi)} & \gate{H} & \ctrl{1} & \qw & \qw & \ctrl{1} & \gate{R_Z(k\pi)} & \gate{H} & \gate{R_Z(\gamma_1)} & \qw \\
& \qw & \qw & \control\qw & \gate{R_Z(\alpha_2)} & \gate{H} & \control\qw & \qw & \qw & \control\qw & \gate{R_Z(\beta_1)} & \gate{H} & \control\qw & \gate{R_Z(\gamma_2)} & \qw & \qw & \qw \\
\end{equation}

whereas extracting the diagram after rule application yields the equivalent smaller circuit:

\begin{equation}\label{eq:extracted_circuit_optimized}\small
\Qcircuit @C=.5em @R=.5em @!R {
& \qw & \qw & \ctrl{1}  & \gate{R_Z(\alpha_1')}  & \gate{H} & \gate{R_Z(\beta_1')} & \gate{H} & \ctrl{1} & \gate{R_Z(\gamma_1')} & \qw \\
& \gate{R_Z(\alpha_2')} & \gate{H} & \control\qw & \qw & \qw & \qw & \qw & \targ & \gate{R_Z(\gamma_2')} & \qw \\
\end{equation}

However, ZX-diagrams simplified with <ref> may contain spiders in $XZ$ and $YZ$ plane as well.
While it has been shown that those diagrams still preserve generalized flow (gflow), the circuit extraction routine has to convert those spiders back into $XY$ spiders using either pivoting $\left(YZ\right)$ or a combination of local complementation and pivoting $\left(XZ\right)$ before extracting the diagram <cit.>.
An algorithm to efficiently extract diagrams that do not admit the gflow property is yet to be discovered; however, recent findings suggest that such an algorithm may not exist for general ZX-diagrams <cit.>.
Hence, even though the diagram may represent a unitary matrix, we cannot extract a quantum circuit from the diagram efficiently.

§ ENHANCING REDUCTION OF 2-QUBIT GATES

As seen in <ref> and <ref>, a Hadamard wire gets extracted to H, CNOT or CZ gates.
The number of Hadamard wires in a graph-like ZX-diagram therefore correlates with the number of 2-qubit gates in the extracted circuit.
The diagram simplification algorithms shown in <ref> focus on eliminating spiders while neglecting – or even increasing – the number of Hadamard wires.
Hence, this section introduces methods which additionally minimize the amount of Hadamard wires (ref. as  in the following).

\begin{equation}\label{eq:bad_cnot_reduction}
\tikzfig{bad_cnot_reduction}
\end{equation}

To do so, it is crucial to examine where and when local complementation and pivoting are applied.
Both rules can either increase or decrease , depending on the connectivity of the relevant neighbors.
<ref> and <ref> show examples in which  decreases.
However, as <ref> shows it can also increase  and we easily construct extreme cases like the one shown in <ref>.
Applying local complementation to the central spider with phase $\pi/2$ yields a diagram containing one spider less but a significantly higher .
Extracting the left diagram with the current version of the PyZX-library produces a circuit with six 2-qubit gates, while the diagram on the right gets extracted as a circuit with $ 21 $ 2-qubit gates.
Generally, applying local complementation on a spider with $ n $ unconnected neighbors leads to $ \frac{n(n+1)}{2} -n $ new wires.
As pivoting involves local complementation on two spiders, the effect usually even worsens for this rule.

To prevent such cases and to guide the simplification process towards a minimal , we introduce cost functions for local complementation and pivoting allowing us to calculate  after rule applications.
We take those as a heuristic for estimating how rule applications change the number of 2-qubit gates and implement decision strategies for diagram simpliciation based on the heuristics.

§.§ Pivoting and local complementation on spiders with arbitrary phases

\begin{equation}\label{eq:lcomp_on_gadget2}
\tikzfig{lcomp_on_gadget3}
\end{equation}

In contrast to the Clifford simplification algorithm from <ref>, we can apply local complementation and pivoting on spiders with arbitrary phases.
Similar to the Pivot Phase Gadget (p2) rule, we can change a spider with non-Clifford phase by a combination of the rules ($ f,i2,i1 $) as in <ref>.
With that we can apply local complementation on spiders with phase different from $\pm\pi/2$ (this introduces one $ XZ $-spider) and pivoting on pairs of spiders where one/no spider has a phase of $0$ or $\pi$ (this introduces one/two $ YZ $-spiders). Note that this does not change the gflow property (c.f. <cit.>).

§.§ Local Complementation Heuristic (LCH)

The costs for local complementation are calculated on the following proposition:

Let $G = \left(V,E\right)$ be an open graph; $u \in V$ an arbitrary vertex with neighbors ; $n = \left|N\left(u\right)\right|$ the number of neighbors; and $m$ the number of edges between the neighbors, i.e.,

\[m = \left|\left\{\left(a,b\right) \in E| a,b \in N\left(u\right)\right\}\right|.\]

For $G\star u$, $n$ remains the same, but $m$ changes to , where $\triangle_{n-1} = \frac{n\left(n-1\right)}{2}$.

Hence, the difference in the number of wires after application of the local complementation rule is:

\begin{equation}
\left(n+m\right) - \left(n + \left(\triangle_{n-1} - m\right)\right) = 2m - \triangle_{n-1}
\end{equation}

With respect to the phase $ \varphi(u) $ of the spider $ u $, the graph changes as follows:

* If $\varphi\left(u\right)=\pm\pi/2$: Remove $ u $ from the graph and eliminate all wires between $ u $ and $ N(u) $.

* If $\varphi\left(u\right)$ is non-Clifford:  All wires between $u$ and $N\left(u\right)$ remain and we get an additional wire for the phase gadget.

* If $\varphi\left(u\right)$ is $0$ or $\pi$: No phase gadget is needed and we can use the $ \pi $-copy rule.

The $ LCH $ is calculated as follows:

\begin{equation}
LCH\left(u\right) = \begin{cases}
2m - \triangle_{n-1} + n & \text{if } \varphi\left(u\right) = \pm\frac{\pi}{2} \\
2m - \triangle_{n-1} & \text{if } \varphi\left(u\right) = k\cdot\pi, k\in \mathbb{Z} \\
2m - \triangle_{n-1} - 1 & \text{otherwise }
\end{cases}
\end{equation}

§.§ Pivoting Heuristic (PH)

We calculate the upper bound of new connections with the sets $ A,B,C $ (see <ref>):

\begin{equation}C_{max} = |A|\cdot|B|+|A|\cdot|C|+|B|\cdot|C|\end{equation}

We denote the number of neighbors of $u$ and $v$ by $n_u = |N(u)|$ and $n_v = |N(v)|$, respectively,
and the number of edges between neighbors of different sets as $ m $.

The changes of the graph $ G $ to $ G\land uv $ have the following cases ($ j,k\in \mathbb{Z} $):

* $ \varphi\left(u\right) = j\cdot\pi, \varphi\left(v\right) = k\cdot\pi $:
If both spiders have a phase of $0$ or $\pi$, all connections between $\left\{u,v\right\}$ and $N\left(u\right) \cup N\left(v\right)$ are eliminated.

* $ \varphi\left(u\right) = j\cdot\pi, \varphi\left(v\right) \neq k\cdot\pi $:
If $v$ becomes a phase gadget and $u$ gets eliminated, all neighbors of $u$ get connected to $v$ and we have an additional wire for the phase gadget.

* $ \varphi\left(u\right) \neq j\cdot\pi, \varphi\left(v\right) = k\cdot\pi $:
If $u$ becomes a phase gadget and $v$ gets eliminated, all neighbors of $v$ get connected to $u$ and we have an additional wire for the phase gadget.

* $ \varphi\left(u\right) \neq j\cdot\pi, \varphi\left(v\right) \neq k\cdot\pi $:
If both spiders become phase gadgets, all neighbors of $u$ get connected to $v$ and all neighbors of $v$ get connected to $u$. Furthermore, $u$ gets connected to $v$ again and we have two more wires for the phase gadgets.

With these conditions, the $ PH $ is calculated as follows:

\begin{equation}\small
PH\left(u,v\right) = \begin{cases}
2m - C_{max}  + n_u + n_v - 1 & \text{for (C1)}\\
2m - C_{max}  + n_v - 1 & \text{for (C2)}\\
2m - C_{max}  + n_u - 1 & \text{for (C3)}\\
2m - C_{max} - 2 & \text{for (C4)} \\
\end{cases}
\end{equation}

§.§ Decision strategies

With the two heuristics ($ LCH, PH $) at hand we can now implement different strategies to decide where and when local complementation or pivoting are applied during the simplification.
A single simplification step in our procedure consists of the following actions:

* Filter all possible rule applications of the current ZX-diagram.

* Select rule according to selection strategy (see below).

* Apply rule on the ZX-diagram.

For filtering rule applications we can specify a lower bound for the heuristic, e.g., $ LCH\text{ or }PH =-5$ says that we do not consider rule applications which increase  by more than five.
We can also specify whether rule applications are allowed on boundary spiders (c.f. <ref>) and whether rules are allowed on arbitrary phased spiders.
For selecting a rule we implemented two different strategies:

* Random selection: Rules are chosen by a random coin flip.

* Greedy selection: Chooses the rule application which maximally decreases .

Each algorithm terminates if we allow only rule applications with a $ LCH/PH >0$ and when there is no rule left that decreases .
They also terminate if we allow negative gains ($ LCH/PH \leq 0 $) and restrict the matches to interior spiders that do not generate new spiders.
This is the case in standard local complementation on a spider with phase $\pm\pi/2$ and pivoting on a pair of spiders with phase $0$ or $\pi$.
The algorithm eliminates at least one spider in every step and terminates when neither interior spiders with phase $\pm\pi/2$ nor pairs with phase $0$ or $\pi$ are left.

On the other hand, allowing rule applications on spiders of arbitrary phases which increase  may result in loops and therefore no termination.

For such cases we only allow rule applications which increase  on spiders present since the very beginning of our simplification procedure. On newly generated spiders only rules which decrease  are allowed.

§ NEW OPTIMIZATION RULE: NEIGHBOR UNFUSION

As shown in <ref>, the application of local complementation ($ lc $) and pivoting ($ p $) on spiders with many neighbors can not only decrease but also increase .
The heuristics shown in <ref> may help to identify and prevent extreme cases as in <ref>.
However, spiders that are measured in $YZ$- or $XZ$-plane (c.f. <ref>) require special attention:
When extracting a spider in $ YZ $-plane (e.g., the empty spider of the phase gadget in <ref> and <ref>), pivoting has to be applied to maintain the focused gflow property.
The same happens for spiders in $ XZ $-plane, but they are resolved by local complementation <cit.>.

This affects  after the simplification and a simplified diagram containing some spiders in $YZ$- and $XZ$-plane may result in an expensive circuit.

However, when applying either rule on diagrams with arbitrary spiders as discussed in <ref>), spiders in  $YZ$- or $XZ$-plane are generated.
We introduce the neighbor unfusion ($ nu $) rule, which allows $ lc $ and $ p $ on such arbitrary-phase spiders without introducing spiders in  $YZ$- or $XZ$-plane.

\begin{equation}\label{eq:neighbor_unfusion_basic}
\tikzfig{neighbor_unfusion_basic}
\end{equation}

Neighbor unfusion combines the fusion ($ f $) and identity rules ($ i1,i2 $) as shown in <ref>.
If a spider with phase $\alpha$ is connected to a neighbor, we change its phase to an arbitrary phase $\gamma$ by inserting an empty spider and a spider with phase $\alpha-\gamma$ between the spider and its neighbor.
It allows changing the phase of an arbitrary spider to $\gamma=\pm\frac{\pi}{2}$ and thus local complementation and removal of spiders with arbitrary phases.

\begin{equation}\label{eq:lcompRuleNeighbors2}
\tikzfig{lcompRuleNeighbors3}
\end{equation}

For illustration, we apply neighbor unfusion ($ nu $) to the example of <ref>.
We can move the $ \beta $ spider to any direction (in <ref> towards $ \alpha_1 $), so it is then not affected by the application of local complementation ($ lc $).
Comparing  <ref> and <ref> we see that we not only reduce , but also prevent the generation of a spider in $ XZ $-plane.

However, the neighbor unfusion rule sometimes leads to diagrams which do not have focused gflow property. This is due to the insertion of the empty spider and the spider with phase $\alpha-\gamma$ in <ref>.

We observed that this problem does not occur if the spiders with phase $\alpha$ and $\beta$ get extracted to the same qubit.
Currently, we find such pairs of spiders by using the flow hierarchy of the maximally delayed gflow of the diagram (c.f. <cit.>), which is quite costly, because we need to recalculate the gflow at each simplification step. Therefore,  diagram simplification with neighbor unfusion has a much higher runtime than the other simplification procedures.
It is an open question whether neighbour unfusion can only destroy the focused gflow property, or also more general flow properties like gflow or Pauli flow.

Circuit metrics for original benchmark circuits, Post-optimization metrics of the standard Clifford simplification <cit.>,  PyZX <cit.>,  Nam et al.<cit.>, our heuristic-based simplification method, and the combined approach of Nam et al. and our heuristic-based methods.
Only our best optimization is presented: 1) Greedy, 2) Random, 3) Greedy with neighbor unfusion, 4) Random with neighbor unfusion, the lower bound for the heuristics is denoted in brackets.
If the best PyZX result is achieved by the  -library, the respective cell is marked with $ \star $.
The best results of each metric in each row are marked.

§ EVALUATION

We evaluate our heuristic-based simplification algorithms on a set of circuits first used in <cit.>.
They implement various arithmetic problems as quantum circuits and were used as a benchmark set for comparing different optimization strategies <cit.>.
We use it to compare our heuristic-based approaches with the Clifford simplification algorithm described in <cit.>, and some of the best results reported for circuit optimizations with <cit.> and without using ZX-calculus <cit.>.
We also investigate how ZX-calculus based approaches perform when using the TODD-algorithm <cit.> for additional T gate reduction.

§.§ Implementation

With the exception of <cit.> – which omits simplifying the diagram (step 3) and extraction (step 4) – we use the following pipeline for ZX-calculus based optimization algorithms:

* Optimize circuit using gate cancellation and commutation.

* Transform circuit to ZX-diagram and apply phase teleportation to reduce T-count (as in <cit.>).

* Simplify ZX-diagram (standard Clifford or heuristic-based simplification).

* Extract circuit from ZX-diagram.

* Optimize circuit as in step 1.

Since our heuristic-based algorithms do not reduce T gates, we always apply the phase teleportation in step 2 since this reduces T gates as far as currently possible with ZX-calculus.
This ensures comparable results regarding the 2-qubit gate count against non-ZX-calculus based approaches that optimize all types of gates.
We implemented our algorithms in a clone of the PyZX library which also contains our optimized circuits in the OpenQASM format[<https://github.com/mnm-team/pyzx-heuristics>]. All results were proven to be correct by checking whether the optimized circuit together with the adjoint of the original circuit can be reduced to the identity.

Circuit metrics for the original benchmark circuits, Post-optimization metrics for PyZX+TODD and of our heuristic-based algorithms+TODD.

§.§ Results

For each circuit we compare the total gate count $\Sigma$ and the 2-qubit gate count $2Q$. The results are summarized in <ref> and <ref>:
Their columns show circuit name, metrics of the original circuit of the benchmark, metrics of one (or more) existing optimization algorithms and the metrics of the best performing heuristic-based algorithm.
For the latter, we denote the simplification strategy achieving the best result in the last column:

* Greedy,

* Random,

* Greedy with neighbor unfusion,

* Random with neighbor unfusion.

As a very first result, the last column in the “Heuristic Algorithm” section of <ref> prominently indicates the great value of neighbor unfusion (Alg. 3 and 4), as it achieves the best performance of our heuristics in $ >70\% $ of the cases.

We now compare our heuristic-based simplifications following against other ZX-calculus based optimizations in <ref>.
For most circuits our heuristic-based simplification clearly outperforms the standard Clifford simplification <cit.>, both in total and 2-qubit gate reduction.
Moreover, while our approaches almost always decrease circuit metrics, the standard approach often yields circuits with higher metrics than the original circuit (e.g.,“CSLA-MUX$ _3 $”, “GF($ 2^6 $)-Mult”).
Especially for 2-qubit gates our approaches decrease 2-qubit gate count by $16\%$, while the standard approach even increases the count by $22\%$.
In a direct comparison our approaches have up to 33% (“Toff-NC${}_4$”) fewer total and 47% (“Mod-Mult${}_{55}$”) fewer 2-qubit gates than the standard Clifford approach.

Second, we compare against the best available PyZX implementation <cit.> and the recommended optimization pipeline of the -library <cit.> with the routines  and , which use similar strategies.
The column “PyZX/” in <ref> shows the best optimization results for both implementations and $\star$ indicates results from .
Except for two circuits (“Mod $5_4$” and “Toff-Barenco${}_3$”), our algorithms outperform all ZX-calculus based algorithms in terms of total gate count and 2-qubit gate count.

Third, <ref> also shows our result in comparison to the cutting-edge non-ZX-calculus based algorithm from Nam et al. <cit.>.
It can be seen that the algorithm from <cit.> outperforms any ZX-calculus based algorithm for most circuits.
Still, we were able to achieve better results for the circuits “VBE-Adder${}_3$” and “Mod-Mult${}_{55}$”.
Note that we did not compare for the “QCLA-Mod${}_7$” circuit, because <cit.> reports that the optimized circuit from  <cit.> does not correspond to the original.

Last, the rightmost columns of <ref> show a combination of Nam et al's approach with ours.
We use the output circuits from the Nam et al. optimization as input for our algorithms and observe that we achieve equally good or better results for almost all circuits.
The larger the circuit, the more significantly this combination improves the previous best known results.
Most notably, we improve the total count of the “Adder${}_8$” circuit by more than 15%
and the 2-qubit gate count by more than 12%.

Apart from the 2-qubit gate count, the T gate count of a quantum circuit is an important metric, since T-gates are more complex to implement for an error-corrected quantum computer.
Therefore, we compare our algorithms to the other ZX-calculus based approaches using the TODD algorithm as optimization step 1).
It is designed to reduce T gate count by introducing ancilla qubits, but sometimes also reduces T-gates in the ancilla-free case.
<ref> shows those benchmarks circuits where the combination of TODD and a ZX-calculus based algorithm reduces T gate count even more compared to the best result in <ref>.
We compare the best combination of our heuristic-based algorithm and TODD against the best combination of an existing ZX-calculus based algorithm and TODD.

While we observe a general increase in 2-qubit and total gates using TODD algorithm, our best algorithm yields better results than the existing ZX-calculus based algorithms in every case.

§ CONCLUSIONS AND FUTURE WORK

In this work we introduce two functions, namely the Local Complementation Heuristic LCH (for the local complementation rule) and the Pivot Heuristic PH (for the pivot rule).
The functions calculate the number of Hadamard wires that would be added or removed by applying the respective rule, thus serving as a heuristic for estimating the 2-qubit gate count of the underlying circuit.
This allows us to develop a more sophisticated strategy for ZX-diagram simplification: First, dismiss the applicable rules that cost too much and then either select a rule randomly or select the rule with the best wire count decrease.

Notably, the T gate count remains unchanged throughout this process, which is why our approach and others that mainly decrease the T gate count complement each other well.
Further, we introduce the new Neighbor Unfusion rule which combines the established fusion and identity rules. This rule allows introducing spiders with arbitrary phases into the circuit if needed, for example when the local complementation or pivot rule would be useful to reduce Hadamard wires.
As a side note, we also formally describe how to use the local complementation and the pivoting rule on spiders with non-Clifford phases, which is a common implementation practice but has never been mentioned in theory.

We measure the impact of aligning the optimization strategy with the heuristics and adding the neighbor unfusion rule by comparing our algorithm to four other approaches, some based on ZX-calculus and some not, on a set of 24 well-established benchmark circuits.
Our approaches show significant improvements compared to all other ZX-based approaches, especially in 2-qubit gate reduction.
On their own, non-ZX-based approaches still yield slightly better results than our ZX-based approaches. However, when combining both we are able optimize circuits better than the previously best known result, which seems to be a promising field for further research.

Using heuristics for ZX-diagram simplification also provides many possibilities for future improvement.
Regarding the selection of rules, both random and greedy strategy are non-optimal for finding a ZX-diagram with minimal number of wires.
Instead, we propose using a metaheuristic selection strategy like simulated annealing for escaping local minima during simplification.
Furthermore, since simplification with neighbor unfusion tends to yield the best results, we think it is important to further investigate in which cases neighbor unfusion generates $XY$ spiders and if we can preserve valid ZX-diagrams when allowing unfusion on spiders which get extracted on different qubits.

§ ACKNOWLEDGMENT

This work is partially supported by the German Federal Ministry of Education and Research (BMBF) under the funding programme Quantum Technologies - From Basic Research to Market under contract number 13N16077.

§ FURTHER RULES

In addition to the rules in <ref>, additional rules have been developed to eliminate every interior Clifford spider.

§.§ Pivoting Boundary Spiders (p1)

The pivoting rule can also be applied if one of the spiders is a boundary spider, i.e., connected to an input or output, using the following transformation:

\begin{equation}
\tikzfig{pivotBoundaryRule}
\end{equation}

Here $v$ gets transformed to an interior spider and both $u$ and $v$ can be removed using the pivoting rule.

\begin{equation}
\tikzfig{gadget_fuse_rule}
\end{equation}

§.§ Gadget Fusion (gf):

An important feature of phase gadgets is that we can fuse two phase gadgets connected to the same neighbors by summing up their phases.

This rule is used for eliminating non-Clifford spiders in a diagram, for instance, two phase gadgets with phase $\pi/4$ connected to the same set of neighbours can be fused into a single phase gadget with phase $\pi/2$.
Combining the Clifford simplification algorithm with those extended rules we can eliminate all interior Clifford spiders (in exchange for phase gadgets) and some interior non-Clifford spiders.

§ GRAPH THEORY

Since ZX-calculus and its optimization strategies rely on graph operations on undirected graphs, we provide some background on it:
An undirected graph is a tuple $G=(V,E)$ with vertices (or “nodes”) $V$ and edges $E \subseteq V\times V$.

§.§ Local Complementation

The local complementation $\star$ <cit.> of an undirected graph $G=\left(V,E\right)$ about a vertex $u$ is defined as follows ($\Delta$ is the symmetric set difference: $  A \mathrel{\Delta} B \coloneqq \left(A\cup B\right)\backslash \left(A\cap B\right)$):

\begin{equation}
G\star u \coloneqq \left(V,E \mathrel{\Delta} \left\{\left(a,b\right)| \left(a,u\right),\left(b,u\right) \in E, a\neq b\right\}\right)
\end{equation}

The following example shows a graph $ G $ and its local complementation about $ a $. Intuitively, local complementation connects two neighbours of $ a $ if they are not connected (e.g., $ b,c $) and disconnects them otherwise (e.g., $ c,d $).

\begin{equation}\label{eq:lcompGraph}
\tikzfig{lcompGraph}
\end{equation}

§.§ Pivoting <cit.>

Pivoting $ \land $ rewrites an edge $(u,v) \in E$ by triple local complementation:

\begin{equation}
G\land uv \coloneqq ((G\star u)\star v)\star u
\end{equation}

To derive the new graph, we consider three disjoint sets (where the neighborhood of vertex $ x $ is defined as   $ N(x) = \{y \in V|(x,y)\in E\} $):

* $A \coloneqq N(u) \cap N(v)$: Vertices connected to $u$ and $v$.

* $B \coloneqq N(u) \backslash N(v)$: Vertices connected to $u$ and not to $v$.

* $C \coloneqq N(v) \backslash N(u)$: Vertices connected to $v$ and not to $u$.

In a pivoted graph $G\land uv$, two vertices from different sets $ A,B$ or $ C $ are connected if, and only if, the two are not connected in $G$. Connections between vertices of the same set are not modified.
As an example, consider the following graphs $ G $ (left) and $ G\land uv $ (right), where $ A=\{b\}, B=\{a,d\}, C = \{c,e\}$. Intuitively, pivoting connects all vertices between $ A,B,C $ that are not connected in $ G $ (e.g., $a,b$) and disconnects them otherwise (e.g., $b,d$):

\begin{equation}
\tikzfig{pivotGraph}
\end{equation}

§ EXAMPLE FOR ZX OPTIMIZATION

The following circuit can be optimized as follows:

\begin{equation}
\begin{array}{c}
\Qcircuit @C=1em @R=.5em @!R {
& \ctrl{2} & \gate{Z} & \ctrl{1} & \gate{Z} & \qw \\
& \qw      & \ctrl{1} & \targ    & \gate{X} & \qw \\
& \targ    & \targ    & \qw      & \gate{X} & \qw
} \end{array}
\begin{array}{c}
\Qcircuit @C=1em @R=.5em @!R {
& \ctrl{1} & \qw      & \qw      & \qw \\
& \targ    & \gate{X} & \ctrl{1} & \qw \\
& \qw      & \qw      & \targ    & \qw
\end{array}
\end{equation}

We use the following rules[The example is inspired by a talk of Russ Duncan “Quantum Formal Methods” from 2021 (1h 35min) which is publicly available.] (the affected spiders/wires to which a rule is applied are framed):

* Eliminate the two Z-gates using spider fusion (f):

$ \tikzfig{example_circuit_1}  \xrightarrow{(\textbf{\textit{f}})} \tikzfig{example_circuit_3} $

* Reduce from 3 to 2 CNOTs with fusion (f) and bialgebra rule (b):

$ \xrightarrow{(\textbf{\textit{f}})}  \tikzfig{example_circuit_4}  \xrightarrow{(\textbf{\textit{f}})}  \tikzfig{example_circuit_5} \xrightarrow{(\textbf{\textit{b}})}  \tikzfig{example_circuit_8} $

* Eliminate one X by the $ \pi $ copy rule:

$  \xrightarrow{(\mathbf{\pi})}  \tikzfig{example_circuit_9} \xrightarrow{(\textbf{\textit{f}})}  \tikzfig{example_circuit_10} $


# Memory Sharing with CXL: Hardware and Software Design Approaches

Sunita Jain, Nagaradhesh Yeleswarapu, Hasan Al Maruf, Rita Gupta  AMD, Inc.
sunita.jain, nagardh, hasan.maruf<EMAIL_ADDRESS>
###### Abstract.

Compute Express Link (CXL) is a rapidly emerging coherent interconnect
standard that provides opportunities for memory pooling and sharing. Memory
sharing is a well established software feature that improves memory
utilization by avoiding unnecessary data movement. In this paper, we discuss
multiple approaches to enable memory sharing with different generations of CXL
protocol (i.e., CXL 2.0 and CXL 3.0) considering the challenges with each of
the architectures from the device hardware and software viewpoint.

††copyright: none††footnotetext: Presented at the 3rd Workshop on
Heterogeneous Composable and Disaggregated Systems (HCDS 2024)

##  1\. Introduction

In today’s server architecture, compute node and memory are tightly coupled
and memory technology is completely dictated by the CPUs. Tight coupling
between CPU and memory subsystem restricts flexible server system design with
different memory hierarchies which leads to stranded compute, network, and/or
memory resources (osr-disaggregation, ). This, eventually, increases a
datacenter’s Total Cost of Ownership (TCO). With the increasing push towards
decoupling CPU and memory resources, a new paradigm shift is taking place for
memory access and data movement in next-generation server architectures (tpp,
; pond-azure, ). CXL (cxl, ) is an open, industry-supported interconnect based
on the PCI Express (PCIe) interface that enables high-speed, low latency
communication between the host processor and end devices (e.g., accelerators,
memory expanders, smart I/O devices, etc.). CXL allows cache-line granular
access to the connected devices with a byte addressable memory in the same
physical address space. From an OS point of view, CXL-Memory appears to the
system as a separate NUMA node where memory access latency is slightly higher
(50—100 ns) over remote NUMA access latency (tpp, ; pond-azure, ). This NUMA-
like behavior with main memory-like access semantics makes CXL-Memory a good
candidate for the slow-tier in datacenter memory hierarchies.

CXL 1.0/1.1 enables a point-to-point link between CPU and end device. CXL 2.0
allows one-hop switching that enables multiple end-devices to be configured to
a single host and supports memory pooling. CXL 3.0 adds multi-hop hierarchical
switching – one can have any complex types of networks through cascading and
fan-out. This expands the number of connected devices and the complexity of
the fabric to include non-tree topologies, like Spine/Leaf, mesh- and ring-
based architectures. CXL 3.0 supports PCIe 6.0 (64 GT/s i.e., up to 256 GB/s
of throughput for a x16 duplex link) and expands the horizon of very complex
and composable rack-scale server design with varied memory technologies.
Besides memory pooling, CXL 3.0 enables memory sharing across multiple hosts
on multiple end-devices where hardware can manage coherency of the shared
memory regions through Back Invalidation (BI). Connected devices (i.e.,
accelerators, memory expanders, NICs, etc.) can do peer-to-peer communication
bypassing the host CPUs.

Figure 1. Memory sharing with CXL 3.0 (Type-3 HDM-DB/FAM)

From CXL 2.0 onward, devices can be hot-plugged or removed. Device-attached
memory is mapped to the system’s coherent address space and accessible to the
host using standard writeback semantics. Memory located on a CXL device can
either be mapped as Host-managed Device Memory (HDM) or Private Device Memory
(PDM). To update the memory address space for connected devices to different
host devices, a system reset is needed; traffic towards the device needs to
stop to alter device address mapping during this reset period. An alternate
solution to avoid this system reset is to map the whole physical address space
to each host when a CXL device is added to the system. The VMM or fabric
manager in the CXL switch will be responsible for maintaining isolation during
address-space management. In case of memory sharing, as CXL 2.0 doesn’t
provide hardware support, the software layer needs to ensure all the coherency
and consistency.

CXL 3.0 adds support for BI to maintain hardware coherency for HDM. This
allows the device to implement a snoop filter to track HDM lines that are
cached in peer caches. As the HDM or shared Fabric Attached Memory (FAM) size
is expected to grow, a precise snoop filter that tracks every 64B cache line
may turn out to be an impractical solution. On the other hand, using an
imprecise snoop filter that tracks at a higher granularity (e.g., 4KB) may
issue unnecessary BI snoops and degrade performance. In this regard, one can
use a hybrid mechanism – employ a precise snoop filter to track certain
region(s) of HDM memory (these shared regions are hardware coherent and can be
used for atomics, semaphore, or metadata like queue-pairs, etc.) and the
coherency for the rest of the regions can be maintained through the software.
This hybrid model allows one to use BI snoop mechanism for a critical portion
of memory within a reasonable performance degradation. Figure 1 shows the
hybrid mechanism for memory sharing in a CXL 3.0-enabled system.

From the above discussion, CXL 2.0 does not provide hardware support for
memory sharing – memory sharing is only possible through software-based
solutions. Although CXL 3.0 has hardware support, for the sake of performance,
for a large shared address-space, a significant portion of the memory regions
require software support for efficient enablement of memory sharing. In the
next sections of this paper, we present different approaches for software only
and software-hardware co-design for the enablement of memory sharing over
upcoming CXL systems.

##  2\. Software-Enabled Memory Sharing

Figure 2. Dual-headed topology for memory sharing

The concept of shared memory is well established in Linux where it is used for
Inter-Processor Communication (IPC) and widely deployed in debuggers. It
enables efficient data exchange and synchronization between processes without
the need for complex data transfer methods such as message passing or file
I/O. Shared memory provides a fast and direct means of communication, making
it ideal for scenarios where processes need to share large amounts of data or
collaborate closely. In Linux, shared memory is implemented through special
system calls and functions where processes create shared memory segments,
attach them to their virtual address-space with appropriate permissions, read
from and write to them, and detach from them when they are no longer needed.

Linux provides several methods for creating and managing shared memory
segments, such as the System V shared memory API, which includes functions
like shmget, shmat, shift, and shmctl. Besides, the POSIX shared memory API
offers similar functionality through functions such as shm_open, mmap, and
munmap. However, these Linux mechanisms are limited to multiple processes
within a single host and cannot be directly used for memory sharing on a
multi-headed CXL-system as presented on Figure 2.

The prototype proposed in Figure 2 uses multi-headed memory expansion CXL
devices (Type-3 device) connected to multiple hosts. In a software-managed
shared memory management solution, memory sharing across multiple hosts can be
done either through a custom framework (custom applications/drivers) or an
extension of sophisticated libraries like OpenSHMEM (openshmem, ).

### Custom Framework.

In such a solution, applications or kernel device drivers need to be re-
designed considering the memory sharing feature for underlying CXL devices.
Participating hosts (Host 1 and 2 in Figure 2) will run their own instances of
application/kernel driver. These instances will communicate with each other to
maintain the sharing semantics. For example, during the initial memory
allocation, instances running on both hosts will agree upon the address range
of fixed memory locations in shared region to allocate common data structures.
Later, they can access or modify the agreed upon memory addresses to maintain
the sharing semantics (e.g., semaphore, synchronized remote memory access,
etc.). All the instances will use reserved memory addresses in shared region
to exchange information between them.

Figure 3. Software stack for custom memory sharing framework

Figure 3 presents the software stack for designing such a custom framework.
The CXL Driver at the OS layer provides support for enabling CXL devices in
the system including bringing up the device, populating the memory address-
space for the hardware, low-level CXL protocol implementation, support for
multi-headed devices, etc. The Verb layer (custom modified for CXL support) in
the user-space provides an abstraction of the underlying CXL protocols. It
exposes a low-level API to the application developers to implement higher-
level sharing-semantics, such as, atomic operations, synchronizations, message
orderings and scheduling, etc. The Upper Layer Protocol provides the
applications a runtime for memory sharing.

It creates contexts for each application that provides a conceptual separation
between multiple processes along with a support for isolation of communication
resources to avoid any interference. Within a context, there can be multiple
workers that are responsible for the shared-memory access request generations,
message queueing, resource monitoring, memory address-space management, etc.
The workers can communicate between each other locally and remotely to track
the progress of any shared memory operation. At the initialization of a
context, the shared memory regions across different hosts are defined and the
workers maintain the global/local memory heaps.

Figure 4. Objects in OpenSHMEM framework

### OpenSHMEM-based Implementation.

OpenSHMEM is an open-source and widely used Partitioned Global Address Space
(PGAS) library interface specification that aims to provide a standard API for
applications to communicate across shared memory regions. OpenSHMEM
implementation provides the interfaces for Atomics, Remote Memory Access
(RMA), Collectives, Symmetric Memory, and Utils components that are
responsible for all data transfer over the shared memory network. Objects
within OpenSHMEM implementation can be either private to each Processing
Engine (PE) or globally sharable across all the PEs running in remote hosts
(Figure 4).

(a)

(b)

Figure 5. Memory sharing on a dual-headed system

Remotely accessible objects are symmetric across all hosts – all PEs have
corresponding objects with the same name, type, and size. It provides pointer
routines to query a local address to a remotely accessible data object.
OpenSHMEM implementation exposes fencing and barrier functionalities that can
be used to implement different programming functionalities for atomic
operations over the shared memory region. OpenSHMEM-based shared memory
implementation over CXL can be a generic and widely adoptable solution as a
lot of details with respect to shared region have already been handled by the
framework.

##  3\. Hardware-Enabled Memory Sharing

In this section, we will discuss a hardware approach for shared memory
management. Our proposed hardware-based prototype design considers dual-headed
CXL Type-3 devices based on a test chip. A dual-headed device has two CXL
ports that can connect to two different hosts through appropriate connectors
and cabling. Hardware atomics (Test & Set or Compare & Swap opcodes) are
implemented for shared memory access control via CXL.io Memory Mapped IO
(MMIO) region. By design, for a shared memory region, a requester is not
expected to issue writes till it grabs the permission for write access. Read
is allowed without atomics, i.e., a single writer and multiple reader profile
is supported.

CXL controllers and shared memory management mechanisms can be implemented
through an FPGA (Figure 5a). Each CXL port has its own set of atomics
registers implemented in the MMIO space on CXL.io. The Access Control Logic
layer provides additional hardware logic that is responsible for granting
locks, semaphore, and other access control functionalities.

The hardware design also provides address remap support per controller to map
the host physical address to device HDM address. Same address remap scheme
applies to addresses in shared memory region for hardware atomics. In such a
hardware-assisted shared memory implementation, the driver is responsible for
the address management and providing abstraction over the hardware logic.
Figure 5b shows the control flow between the application, device driver, and
the FPGA during a shared memory operation. When an application appears to the
system, the shared memory driver registers it and exposes access to the
interfaces for hardware functionalities. It then grants access to the memory
region that can be shareable to the application and stores all the metadata
including virtual to physical address translation, access granularity,
permission type, etc.

When an application appears to the system, the shared memory driver registers
it and exposes access to the interfaces for hardware functionalities. It then
grants access to the memory region that can be shareable to the application
and stores all the metadata including virtual to physical address translation,
access granularity, permission type, etc. When the user space application
requests for a write access permission, the driver sends a message to the
hardware to initiate hardware atomics. Once the access permission is acquired
and the corresponding flag is set, the driver returns to the application. All
the write access requests are ordered and served based on the arrival
sequence. The write access release mechanism follows a similar routine –
hardware atomics is issued and the flag is reset, the application is notified,
and the next write access request can be executed.

##  4\. Discussion

### Sharing Granularity.

Memory sharing improves application-level performance by reducing unnecessary
data movement and improves memory utilization. Sharing a large memory address
space, however, may result in significant overhead and complexity in the
system. For example, in a terabyte or even larger system, sharing the whole
address space across multiple hosts with high access frequency may cause high
overhead due to consistency management. Continuously invalidating and updating
the memory regions across all the hosts can be extremely expensive operations.
Besides, cache line or page granular lock management can be impractical
because of the memory overhead due to metadata management. This overhead can
be reduced if we consider larger memory regions (e.g., 1GB region). However,
if multiple hosts have frequent write request rate, such large granular
regions may add high wait time for other hosts to grab the lock. CXL-enabled
multi-headed shared memory systems will be ideal for applications that have
high read and low write demands.

### Security.

Furthermore, sharing memory across multiple devices increases the security
threat in the presence of any malicious application run on the same hardware
space. When an application disappears from the system, assigning a fraction of
its previously shared memory space to a newly arrived application may leak
sensitive information if proper encoding, isolation, and clean up mechanism is
not exercised. Hardware assists can be deployed to zeroize the memory region
before assigning the same to a new application.

##  5\. Conclusion

In this paper, we present different approaches for enabling CXL-based memory
sharing with different generations of CXL protocol and discuss their trade-
off. With CXL 3.0 features the entire rack can share memory. This becomes very
powerful with Global Integrated Memory (GIM). In addition, near data
processing with memory sharing will open up new use-cases for CXL at rack-
scale.

## References

  * [1] Compute Express Link (CXL).  https://www.computeexpresslink.org/.
  * [2] OpenSHMEM Specification.  https://openshmem.org/site/specification.
  * [3] H. Al Maruf and M. Chowdhury.  Memory disaggregation: Advances and open challenges.  ACM SIGOPS OSR, 2023.
  * [4] H. Li, D. S. Berger, S. Novakovic, L. Hsu, D. Ernst, P. Zardoshti, M. Shah, S. Rajadnya, S. Lee, I. Agarwal, M. D. Hill, M. Fontoura, and R. Bianchini.  Pond: CXL-Based Memory Pooling Systems for Cloud Platforms.  In ASPLOS, 2023.
  * [5] H. A. Maruf, H. Wang, A. Dhanotia, J. Weiner, N. Agarwal, P. Bhattacharya, C. Petersen, M. Chowdhury, S. Kanaujia, and P. Chauhan.  TPP: Transparent page placement for CXL-enabled tiered-memory.  In ASPLOS, 2023.