# Measuring Neutron Star Radius with second and third generation Gravitational
Wave Detector Networks

Ananya Bandopadhyay<EMAIL_ADDRESS>Department of Physics, Syracuse
University, Syracuse, NY 13244, USA  Keisi Kacanja<EMAIL_ADDRESS>Department of Physics, Syracuse University, Syracuse, NY 13244, USA  Rahul
Somasundaram<EMAIL_ADDRESS>Department of Physics, Syracuse University,
Syracuse, NY 13244, USA  Theoretical Division, Los Alamos National Laboratory,
Los Alamos, NM 87545, USA  Alexander H. Nitz<EMAIL_ADDRESS>Department of
Physics, Syracuse University, Syracuse, NY 13244, USA  Duncan A. Brown
<EMAIL_ADDRESS>Department of Physics, Syracuse University, Syracuse, NY
13244, USA

###### Abstract

The next generation of ground-based interferometric gravitational wave
detectors will observe mergers of black holes and neutron stars throughout
cosmic time. A large number of the binary neutron star merger events will be
observed with extreme high fidelity, and will provide stringent constraints on
the equation of state of nuclear matter. In this paper, we investigate the
systematic improvement in the measurability of the equation of state with
increase in detector sensitivity by combining constraints obtained on the
radius of a $1.4\,\mathrm{M}_{\odot}$ neutron star from a simulated source
population. Since the measurability of the equation of state depends on its
stiffness, we consider a range of realistic equations of state that span the
current observational constraints. We show that a single 40km Cosmic Explorer
detector can pin down the neutron star radius for a soft, medium and stiff
equation of state to an accuracy of 10m within a decade, whereas the current
generation of ground-based detectors like the Advanced LIGO-Virgo network
would take $\mathcal{O}(10^{5})$ years to do so for a soft equation of state.

  * February 2023

##  1 Introduction

Cosmic Explorer is a groundbreaking next-generation gravitational wave
detector, representing a significant leap in our capacity to explore a
plethora of compact binary merger events. The development of Cosmic Explorer
and other advanced gravitational wave detectors, such as Einstein Telescope
[1, 2], will allow us to understand neutron stars and their internal
structure. Cosmic Explorer will detect hundreds of signals with high signal-
to-noise ratios (SNR), greater than 100 [3, 4]. With the improvement in
sensitivity of the detectors, it will be possible to measure the radius of a
neutron star with unprecedented accuracy. Inference from simulated populations
performed by combining information from a large number of observed events,
allows us to obtain improved constraints on the equation of state [5, 6, 7, 8,
9, 10]. Previous works have demonstrated the feasibility of combining
constraints from multiple observations using statistical tools, to obtain a
tighter constraint on the equation of state.

In particular, Finstad et al. [10] combined $\mathcal{O}(300)$ signals in an
Advanced LIGO-Virgo network and compared it to the constraints obtained by
stacking observations for one year of operation of a single Cosmic Explorer
detector, showing the order of magnitude improvement in measurement accuracy
achieved by a singular Cosmic Explorer. However, Cosmic Explorer will operate
as a network which calls for the need to systematically investigate different
detector configurations in order to fully gauge the improvement in sensitivity
that Cosmic Explorer would accomplish. Therefore, in this paper, we extend the
work of Finstad et al. [10] to systematically study the improvement in the
measurability of the equation of state with the increase in network
sensitivity from the current generation of Advanced LIGO-Virgo detectors at
design sensitivity to the planned Cosmic Explorer detectors, which are
expected to begin operations in 2030s. We simulate an astrophysical population
of neutron stars consistent with current observational constraints on the rate
of binary neutron star mergers in the universe [11]. We perform a full
Bayesian parameter estimation to obtain a forecast on the expected number of
years of observation at different detector sensitivities required to measure
the radius of a neutron star accurate to 10m, by simulating different
realizations of the universe from the above population. We present our results
for an Advanced LIGO-Virgo network, a post O5 network comprised of three LIGO
detectors at $\rm A^{\sharp}$ 111https://dcc.ligo.org/LIGO-T2300041/public
sensitivity, a 20km and a 40km Cosmic Explorer detector
222https://dcc.cosmicexplorer.org/CE-T2000017, and two other next generation
detector networks. The first of these is comprised of a 40km Cosmic Explorer
along with two detectors at $\rm A^{\sharp}$ sensitivity, and the second
consists of a 40km Cosmic Explorer, a 20km Cosmic Explorer and one detector at
$\rm A^{\sharp}$ sensitivity. For each of the networks, we combine equation of
state constraints (in terms of measurement of radius of a $1.4\,\rm M_{\odot}$
neutron star) from multiple events, observed across a given observing period
for each detector (network). We study the measurability of the neutron star
radius for three different equation of state models drawn from [12] that are
calibrated with nuclear theory at lower densities and span the current
observational constraints at densities relevant for neutron stars. We find
that, while the current generation of ground-based gravitational wave detector
network would require thousands of years to accurately measure the neutron
star radius even for a stiff equation of state (i.e. relatively more
measurable), a single 40km Cosmic Explorer can do so within a year. Multi-
detector networks including at least one Cosmic Explorer detector could
constrain the radius to 10m accuracy within a few years for even the softest
equation of state considered here. Our result clearly demonstrates the
potential of next generation detector networks to constrain the equation of
state of dense nuclear matter to a higher accuracy than is possible for any
existing experimental facility.

The rest of this article is organized as follows. In Section 2, we describe
the properties of the population of neutron stars that we are examining for
our study. In Section 3, we describe the Bayesian inference framework that is
used to obtain combined constraints on the equation of state from the
measurement of neutron star radius across an observed population. In Section
4, we present the results of our analysis, i.e. the projected constraints on
the radius of a $1.4\,\rm M_{\odot}$ neutron star for different detector
networks, and conclude the study in Section 5.

##  2 Neutron Star Population

To study the measurability of tidal deformability from the gravitational wave
signals of inspiralling binary neutron star systems, we generate a population
of binary neutron star systems with component masses drawn from a Gaussian
centered at $1.4\,\rm M_{\odot}$ and having a standard deviation
$\sigma_{m}=0.05\,\rm M_{\odot}$. The spins are chosen to be aligned with the
orbital angular momentum, and are drawn from a Gaussian distribution with zero
mean and $\sigma_{\chi}=0.02.$ The events are chosen to be isotropically
distributed across sky locations, and the inclination and orientation of the
binary systems are distributed uniformly on the sphere. The luminosity
distances of the systems are drawn from a uniform distribution in the range
$d_{L}\in[20\,\rm Mpc,20\,\rm Gpc].$ Events at larger distances, i.e. having
low values of signal-to-noise ratios, contain roughly the same amount of
information about the measured parameters, thus drawing events uniformly in
distance reduces the amount of computational resources spent on sampling over
the parameters of a large number of “uninformative” events occurring at higher
distances in the simulated astrophysical population. It also gives us a
greater selection of “informative” events (occurring at nearby distances) to
choose from, in constructing different realizations of the universe, as
compared to what we would have had if our simulated population of neutron
stars was the true astrophysical population. We use the median merger rate for
binary neutron stars $\mathcal{R}=320_{-240}^{+490}\,\rm Gpc^{-3}yr^{-1}$ from
[11] to normalize the astrophysical population, and reweight our neutron star
population to a uniform in volume distribution. Our final distribution is
uniform in volume. The uniform in volume assumption is reasonable for sources
which contribute substantially to the equation of state measurement, since
only the close by sources would be detected with signal-to-noise ratios high
enough to extract equation of state information from them.

Figure 1: Neutron star mass-radius curves for the soft (blue), medium (orange)
and stiff (green) equations of state used in our analysis. The curves shown in
grey depict the full set of 2000 equations of state used as the prior for the
Bayesian analysis. The equation of state set is constructed in such a way that
the distibution of radii for a $1.4\,\rm M_{\odot}$ neutron star is roughly
uniform.

Since the measurability of the tidal deformability depends strongly on the
equation of state, we choose a set of three equations of state representing a
soft, a medium and a stiff one, for this study. These are then used to assign
tidal deformabilities to the individual neutron stars in each simulated
signal. They are chosen from a set of 2000 equations of state also used in
[10], calibrated with chiral effective field theory calculations up to nuclear
saturation density, $n_{\rm sat}$. Beyond this point, their construction is
based on general considerations of thermodynamic stability and causality, and
employing a general extension scheme in the speed of sound $c_{\rm s}^{2}$ for
densities between $[n_{\rm sat},12n_{\rm sat}]$ [12]. Fig. 1 shows the full
set of 2000 equations of state, which we use as the prior for our parameter
estimation runs, with the soft, medium and stiff equations of state labelled
in blue, green and orange respectively.
Parameter estimation runs are performed for the simulated population
separately for each equation of state. The waveform model used for generating
the simulated signals is the IMRPhenomD_NRTidal approximant. This is a
frequency domain approximant that is based on a phenomenological inspiral-
merger-ringdown model IMRPhenomD, originally constructed to model binary black
hole systems with spins aligned with their angular momentum axis [13, 14].
Tidal effects are superposed on the binary black hole waveforms and calibrated
with Numerical Relativity simulations of binary neutron star systems to obtain
the binary neutron star waveform approximant [15, 16]. For high SNR signals,
which will be detected abundantly by the next generation gravitational wave
detectors, waveform systematics can become a dominant source of error in the
extraction of parameters [9]. Earlier works have shown that tidal parameters
can be recovered reliably using the IMRPhenomD_NRTidal waveform for systems
with small mass ratios and spins [17]. Stiffer equations of state have been
shown to introduce a bias in the recovery of non-tidal parameters, which in
turn would affect the measurement of the equation of state [18, 17]. Systems
with unequal mass ratios and highly spinning systems also show an increased
bias in the estimation of tidal parameters [19], thus indicating the need for
improved waveform modelling for binary neutron star systems for the next
generation of ground based detectors.

##  3 Injection Study

To quantify the improvement in measurability of the equation of state through
neutron star radius and tidal deformability measurements with increase in
detector sensitivity, we perform a Bayesian Inference based parameter
estimation for the injected signals, which are projected onto simulated
detector noise. We consider six different detector networks for the purpose of
this study. The LIGO-Virgo network consists of the LIGO Handford, LIGO
Livingston [20, 21] and Virgo detectors [22] simulated at design sensitivity
[23]. The post-O5 network is also comprised of three detectors, LIGO Handford,
LIGO Livingston and LIGO India, at A♯ sensitivity [24]. The two Cosmic
Explorer detectors are considered as single detector networks, a 40km Cosmic
Explorer detector off the coast of Washington, and a 20km Cosmic Explorer
detector off the coast of Texas. Additionally, we consider two more next
generation detector networks. The first of these is comprised of a 40km Cosmic
Explorer detector off the coast of Washington, and two detectors at Livingston
and India, operating at A♯ sensitivity (henceforth referred to as CE40+2$\rm
A^{\sharp}$). The final network consists of a 40km Cosmic Explorer, a 20km
Cosmic Explorer and LIGO India operating at A♯ sensitivity (henceforth
referred to as CE40+CE20+$\rm A^{\sharp}$). Since the site locations for the
Cosmic Explorer detectors are yet to be determined, the aforementioned
fiducial locations are chosen as being close enough to a wide range of
potential sites for the detectors to be representative from the point of view
of the science goals that we address here.
To assess the performance of each detector network, we simulate a population
of binary neutron star sources and apply a lower bound of 30 on the signal-to-
noise ratio (SNR) to determine the events for which parameter estimation runs
are performed to infer source parameters. For signals observed with lower
signal-to-noise ratio than the threshold value, the error bars associated with
radius measurement are large, implying that these signals contribute
negligibly to the combined equation of state inference.
Parameter estimation for the injected signals is based on the Bayes theorem.
Here we briefly review the theorem in the context of its application to
gravitational wave astronomy. It states that for a set of parameters
$\vec{\theta}$ that can be used to construct a model $M$ for the gravitational
waveform, and given $\vec{d}(t)$, the gravitational wave strain data from the
detectors,

$p(\vec{\theta}|\vec{d}(t),M)=\frac{\pi(\vec{\theta}(t)|M)\mathcal{L}(\vec{d}(t)|\vec{\theta},M)}{\mathcal{Z}},$
(1)

where $p(\vec{\theta}|\vec{d}(t),M)$ is the data-informed posterior
distribution of the parameter $\vec{\theta}$, $\pi(\vec{\theta}(t)|M)$ is our
prior knowledge of the parameter vector $\vec{\theta}$, conditional on the
model, and $\mathcal{L}(\vec{d}(t)|\vec{\theta},M)$ is the likelihood of
obtaining data $\vec{d}(t)$ given the waveform model $M$ and the parameters
$\vec{\theta}$. Assuming that each detector produces stationary, Gaussian
noise that is uncorrelated between different detectors in the network, the
likelihood function is given by [25]

$\displaystyle\mathcal{L}(\vec{d}|\vec{\theta},M)=\exp\left(-\frac{1}{2}\sum\limits_{i=1}^{N}\langle
n_{i}|n_{i}\rangle\right)$
$\displaystyle=\exp\left(-\frac{1}{2}\sum\limits_{i=1}^{N}\langle
d_{i}-h_{i}(\vec{\theta})|d_{i}-h_{i}(\vec{\theta})\rangle\right)$ (2)

where

$\langle a|b\rangle=4\mathbb{R}\int\limits_{f_{\rm min}}^{f_{\rm
max}}{\frac{\tilde{a}^{*}(f)\tilde{b}(f)}{S_{n}(f)}}$ (3)

is the noise-weighted inner product of two functions.

$\mathcal{Z}=\int{\pi(\vec{\theta}(t)|M)\mathcal{L}(\vec{d}(t)|\vec{\theta},M)d\vec{\theta}}$
is the Bayesian evidence, which acts as a normalization constant. We use
ensemble samplers, like Markov Chain Monte Carlo samplers, that sample the
parameter space of interest, and trace out the posterior probability
distribution. For this work, we use the parallel-tempered emcee sampler [26],
invoking it through the PyCBC Inference library [27], to estimate posterior
distributions of all of the parameters used to model the binary neutron star
signals, as described in Section 2. We use the heterodyne likelihood model
[28, 29, 30] in PyCBC for likelihood estimation, which evaluates the
likelihood in discrete bins close to the peak value, to speed-up sampler
convergence.
In the process of recovering the signal parameters through Markov-Chain Monte
Carlo sampling, the sampling parameters are chosen to be the source frame
chirp mass and mass ratio, component spins along the direction of the angular
momenta, sky location, distance, geocentric time of coalescence, inclination,
polarization angle, and the equation of state. We sample over the equations of
state in the same procedure as [10]. The equations of state are indexed in
increasing order of radii for a $1.4\,\rm M_{\odot}$ neutron star, and each
index corresponds to a unique mass-radius (or equivalently, mass-tidal
deformability) curve in the equation of state parameter space. The lower
frequency cutoff for the signals analyzed are chosen to be higher than the
seismic frequency limit for the detectors. For the LIGO-Virgo network at
design sensitivity, we use a lower frequency cutoff of 20 Hz, for the
detectors at $\rm A^{\sharp}$ sensitivity, we use 10 Hz, and for the Cosmic
Explorer detectors, the lower frequency cutoff is chosen to be 7 Hz. The high
frequency cutoff for all signals is 2048 Hz.
Once the sampler converges, we obtain the full set of posterior samples for
the parameters of each of the analyzed events. This represents our knowledge
of the source parameters for the gravitational wave event, conditioned on the
data. We then combine multiple events hierarchically, to obtain a
hyperposterior for the neutron star radius, that represents our integrated
knowledge of the equation of state from the observed population of neutron
stars. To do this, we first convert the equation of state samples to radius
samples for a $1.4\,\rm M_{\odot}$ neutron star (denoted as $\rm R_{1.4}$).
This is done by using the mass-radius curve corresponding to each equation of
state sample to determine the radius value for that sample. We then use a
Gaussian Kernel Density Estimation [31] to obtain the posterior distribution
on the radius for each event. The combined posterior for $N$ events
$\\{s_{1},s_{2},...s_{N}\\}$ is then obtained as

$p(\mathrm{R}_{1.4}|s_{1},...s_{N})=p(\mathrm{R}_{1.4})^{(1-N)}\prod\limits_{i=1}^{N}p(\mathrm{R}_{1.4}|s_{i})$
(4)

where $p(\mathrm{R}_{1.4})$ is the radius prior, uniform across all events.

Figure 2: Combined constraints on the measurement of $R_{1.4}$ for the six
different detector networks considered in this study. The blue, orange and
green colors represent the constraints for the soft, medium and stiff
equations of state respectively. The shaded regions in the figures represent
the 90$\%$ credible intervals for the combined radius posteriors obtained
using Eqn. 4. The dotted lines depict the fractional error bars on radius
measurement after a given number of years of observation. The dashed lines are
the injected radius values.

Figure 3: Distribution of the number of years of observation at different
network sensitivities required to constrain the radius of a
$1.4\,\mathrm{M}_{\odot}$ neutron star down to an accuracy of 10m. The blue,
orange and green histograms depict the expected distributions for the soft,
medium and stiff equations of state respectively. The vertical dashed lines
represent the median and $90\%$ credible intervals for each histogram.

##  4 Results

We simulate a realistic observing scenario for binary neutron star mergers by
creating a population of neutron stars distributed uniformly in distance
(details in Section 2) and re-weighting our events to a population distributed
uniformly in volume. We then make random draws from this population to
construct different realizations of the universe. We also randomize the
sequence of detection of the events and combine the posteriors for $\rm
R_{1.4}$ using Eq. 4 to obtain the projected accuracy in the measurement of
neutron star radius for a given observation period for each detector network.
In Fig. 2, we show the projected constraints on the radius of a $1.4\rm
M_{\odot}$ neutron star for a given random drawn population for the four
detector networks described in Section 3. For all of the detector networks, we
find that the combined radius posterior converges towards the injected value.
We find that a next generation detector configuration with one 40km Cosmic
Explorer, one 20km Cosmic Explorer and one A♯ detector converges to the
injected radius the fastest. Even one Cosmic Explorer detector converges
faster to the radius than a three-detector Advanced LIGO-Virgo configuration.

As pointed out in [10], the loudest events have the most significant
contribution towards lowering the fractional error bars on radius measurement.
Thus, the exact time required to measure the radius of a neutron star to a
certain accuracy will be affected by the order of occurrence of the events. To
mitigate the effect of the ordering of events used in obtaining the projected
constraints in Fig. 2, we draw different populations of the universe for each
detector network 500 times and plot the distribution of the number of years of
operation it would take to constrain the radius of a $1.4\,\mathrm{M}_{\odot}$
neutron star to an accuracy of $10\,\rm m$. These results are shown in Fig. 3
and a summary is also shown in Table 1. From these, we can see that even for
the stiffest equation of state, the current generation of ground based
detectors like the Advanced LIGO-Virgo network would take several thousand
years to measure the radius of a neutron star to an accuracy of 10m, and this
improves only slightly with the A♯ upgrade. For a very stiff equation of state
which gives a radius of $~{}\sim 13\,\rm km$ for a $1.4\,\rm M_{\odot}$
neutron star, the A♯ network may be able to constrain radius to an accuracy of
10m within 20 years, but this worsens significantly if the true equation of
state is moderately soft. On the other hand, a single 40km Cosmic Explorer
detector will be able to constrain radius to an accuracy of 10m within 12
years for the softest equation of state considered here, and within a year for
the stiffest. In order to measure the equation of state for a neutron star in
a viable time-frame, building Cosmic Explorer is absolutely essential.

Detector network | Soft EoS | Medium EoS | Stiff EoS
---|---|---|---
LIGO-Virgo | $2\rm e5_{-4e4}^{+4e4}$ | $5\rm e4_{-1e4}^{+1e4}$ | $7000_{-900}^{+900}$
$3\,\rm A^{\sharp}$ | $300_{-50}^{+50}$ | $100_{-40}^{+40}$ | $20_{-4}^{+4}$
CE20 | $21_{-10}^{+10}$ | $15_{-7}^{+7}$ | $3_{-1}^{+1}$
CE40 | $12_{-3}^{+3}$ | $8_{-1}^{+1}$ | $1_{-0.6}^{+0.6}$
CE40+$2\,\rm A^{\sharp}$ | $9_{-4}^{+4}$ | $6_{-2}^{+2}$ | $0.4_{-0.2}^{+0.2}$
CE40+CE20+$\rm A^{\sharp}$ | $5_{-2}^{+2}$ | $3_{-1}^{+1}$ | $0.2_{-0.07}^{+0.07}$
Table 1:  A summary of the result of drawing 500 random realizations of the
universe from our simulated population for each detector network and each
equation of state. For each realization of the universe, the events are
shuffled to randomize order of occurrence, and then used to determine the
average number of years required to measure the radius of a $1.4\,\rm
M_{\odot}$ neutron star to an accuracy of 10m.

##  5 Conclusion

In this paper, we have performed a comparative study of the potential of
different second and third generation gravitational wave detector networks to
precisely constrain the nuclear equation of state. We perform a full Bayesian
inference on a simulated population of neutron stars to be observed at
different network sensitivities. The equation of state models used in the
analysis span the plausible range of stiffness allowed by current
observational constraints for densities relevant for neutron stars, and are
calibrated with chiral effective field theory at the low density regime. We
combine constraints from individual events, and show that this procedure can
be used to obtain a stringent constraint on the radius of a $1.4\,\rm
M_{\odot}$ neutron star.
Our results demonstrate the systematic improvement in the measurability of the
nuclear equation of state with improvement in sensitivity of gravitational
detectors, from the current generation of Advanced LIGO-Virgo detectors, to
the A♯ upgrade, and subsequently the next generation of detectors like Cosmic
Explorer. The constraints obtained on the equation of state follow the
expected hierarchy of measurability, with the stiffest equations of state
giving the most stringent constraints, and the softer models leading to weaker
constraints. Based on the current estimate for the merger rate from [11], we
find that the Advanced LIGO-Virgo detectors operating at design sensitivity
would take $2\rm e5_{-4e4}^{+4e4}$, $5\rm e4_{-1e4}^{+1e4}$ and
$7000_{-900}^{+900}$ years respectively to constrain the radius of a $1.4\,\rm
M_{\odot}$ to an accuracy of 10m, for the soft, medium and stiff equations of
state respectively. With the detectors operating at A♯ sensitivity, the same
accuracy can be reached in $300_{-50}^{+50}$, $100_{-40}^{+40}$ and
$20_{-4}^{+4}$ years. However, with the next generation of ground based
detectors like the Cosmic Explorer, the radius of a $1.4\,\rm M_{\odot}$
neutron star can be measured to an accuracy of 10m well within a human
lifetime, with a single 20km detector doing it in $21_{-10}^{+10}$,
$15_{-7}^{+7}$ and $3_{-1}^{+1}$ years, and a 40km detector requiring only
$12_{-3}^{+3}$, $8_{-1}^{+1}$ and $1_{-0.6}^{+0.6}$ years respectively for the
soft, medium and stiff equations of state. The multi-detector network
comprised of a 40km Cosmic Explorer and 2 detectors at $\rm A^{\sharp}$ does
it in $9_{-4}^{+4}$, $6_{-2}^{+2}$ and $0.4_{-0.2}^{+0.2}$ years, whereas the
network comprised of a 40km Cosmic Explorer, a 20km Cosmic Explorer and an
$\rm A^{\sharp}$ takes $5_{-2}^{+2}$, $3_{-1}^{+1}$ and $0.2_{-0.07}^{+0.07}$
years respectively to measure the radius to an accuracy of 10m for the soft,
medium and stiff equations of state. Thus, the next generation of ground based
detectors will be instrumental in constraining the nuclear equation of state
to a level of accuracy that can not be reached with any existing facilities.

Some of the source bias in the process of obtaining combined constraints by
this method are pointed out in [10]. These biases include the imperfect
knowledge of the mass distribution of neutron stars and the potential absence
of an electromagnetic counterpart, posing challenges in distinguishing a
binary neutron star system from a neutron star black hole system. In this
study, we circumvent the bias caused by the imperfect knowledge of mass
distribution by choosing the mass prior used in our analysis to be the same as
the one used to simulate the neutron star population. However, in practical
applications, as more and more signals from binary neutron star mergers are
detected, the mass distribution used in the inference should also be
simultaneously updated to mitigate this bias. Another source of bias in
obtaining constraints on the equation of state, particularly in terms of the
neutron star radius, is that we do not measure radius directly from
gravitational wave signals, but use the measurement of tidal deformability to
obtain an estimate of the radius. Since the love number $k_{2}$ (as defined in
e.g., [32, 33, 34]), relating tidal deformability to radius, is also a
function of radius, even an extremely precise measurement of the tidal
deformability leads to a multimodal distribution for measured radius, which
can ultimately tend to bias the median value of the measured radius away from
its true value. Future works can extend this work to constrain the radius not
only for a $1.4\,\rm M_{\odot}$ neutron star but for the whole mass range
allowed by plausible equations of state. In conclusion, our work highlights
the imperative need to build Cosmic Explorer in order to be able to accurately
constrain the radius of a neutron star within a human lifetime.

Supporting data for this manuscript is available at github.com/sugwg/bns-eos-
nggw.

## Acknowledgements

The authors acknowledge support from National Science Foundation Awards
PHY-2011655 (AB and DAB), PHY-2207264 (DAB), and PHY-2309240 (AHN, KK and
DAB). RS acknowledges support from the Nuclear Physics from Multi-Messenger
Mergers (NP3M) Focused Research Hub which is funded by the National Science
Foundation under Grant Number 21-16686, and by the Laboratory Directed
Research and Development program of Los Alamos National Laboratory under
project number 20220541ECR. This research was supported through computational
resources provided by Syracuse University.

## References

  * [1] Stefan Hild et al.  “A Xylophone Configuration for a third Generation Gravitational Wave Detector”  In _Class. Quant. Grav._ 27, 2010, pp. 015003  DOI: 10.1088/0264-9381/27/1/015003
  * [2] B. Sathyaprakash  “Scientific Objectives of Einstein Telescope” [Erratum: Class.Quant.Grav. 30, 079501 (2013)]  In _Class. Quant. Grav._ 29, 2012, pp. 124013  DOI: 10.1088/0264-9381/29/12/124013
  * [3] Benjamin P Abbott  “Exploring the Sensitivity of Next Generation Gravitational Wave Detectors”  In _Class. Quant. Grav._ 34.4, 2017, pp. 044001  DOI: 10.1088/1361-6382/aa51f4
  * [4] Matthew Evans et al.  “A Horizon Study for Cosmic Explorer: Science, Observatories, and Community”  In _arXiv e-prints_ , 2021, pp. arXiv:2109.09882  DOI: 10.48550/arXiv.2109.09882
  * [5] Benjamin D. Lackey and Leslie Wade  “Reconstructing the neutron-star equation of state with gravitational-wave detectors from a realistic population of inspiralling binary neutron stars”  In _Phys. Rev. D_ 91.4, 2015, pp. 043002  DOI: 10.1103/PhysRevD.91.043002
  * [6] Michalis Agathos et al.  “Constraining the neutron star equation of state with gravitational wave signals from coalescing binary neutron stars”  In _Phys. Rev. D_ 92.2, 2015, pp. 023012  DOI: 10.1103/PhysRevD.92.023012
  * [7] Francisco Hernandez Vivanco et al.  “Measuring the neutron star equation of state with gravitational waves: The first forty binary neutron star merger observations”  In _Phys. Rev. D_ 100.10, 2019, pp. 103009  DOI: 10.1103/PhysRevD.100.103009
  * [8] Costantino Pacilio, Andrea Maselli, Margherita Fasano and Paolo Pani  “Ranking Love Numbers for the Neutron Star Equation of State: The Need for Third-Generation Detectors”  In _Phys. Rev. Lett._ 128.10, 2022, pp. 101101  DOI: 10.1103/PhysRevLett.128.101101
  * [9] Katerina Chatziioannou  “Uncertainty limits on neutron star radius measurements with gravitational waves”  In _Phys. Rev. D_ 105.8, 2022, pp. 084021  DOI: 10.1103/PhysRevD.105.084021
  * [10] Daniel Finstad, Laurel V. White and Duncan A. Brown  “Prospects for a Precise Equation of State Measurement from Advanced LIGO and Cosmic Explorer”  In _ApJ_ 955.1, 2023, pp. 45  DOI: 10.3847/1538-4357/acf12f
  * [11] R. Abbott  “Population Properties of Compact Objects from the Second LIGO-Virgo Gravitational-Wave Transient Catalog”  In _Astrophys. J. Lett._ 913.1, 2021, pp. L7  DOI: 10.3847/2041-8213/abe949
  * [12] Collin D. Capano et al.  “Stringent constraints on neutron-star radii from multimessenger observations and nuclear theory”  In _Nature Astron._ 4.6, 2020, pp. 625–632  DOI: 10.1038/s41550-020-1014-6
  * [13] Sascha Husa et al.  “Frequency-domain gravitational waves from nonprecessing black-hole binaries. I. New numerical waveforms and anatomy of the signal”  In _Phys. Rev. D_ 93.4, 2016, pp. 044006  DOI: 10.1103/PhysRevD.93.044006
  * [14] Sebastian Khan et al.  “Frequency-domain gravitational waves from nonprecessing black-hole binaries. II. A phenomenological model for the advanced detector era”  In _Phys. Rev. D_ 93.4, 2016, pp. 044007  DOI: 10.1103/PhysRevD.93.044007
  * [15] Kevin Barkett  “Gravitational waveforms for neutron star binaries from binary black hole simulations”  In _Phys. Rev. D_ 93.4, 2016, pp. 044064  DOI: 10.1103/PhysRevD.93.044064
  * [16] Tim Dietrich, Sebastiano Bernuzzi and Wolfgang Tichy  “Closed-form tidal approximants for binary neutron star gravitational waveforms constructed from high-resolution numerical relativity simulations”  In _Phys. Rev. D_ 96.12, 2017, pp. 121501  DOI: 10.1103/PhysRevD.96.121501
  * [17] Tim Dietrich, Tanja Hinderer and Anuradha Samajdar  “Interpreting Binary Neutron Star Mergers: Describing the Binary Neutron Star Dynamics, Modelling Gravitational Waveforms, and Analyzing Detections”  In _Gen. Rel. Grav._ 53.3, 2021, pp. 27  DOI: 10.1007/s10714-020-02751-6
  * [18] Reetika Dudi et al.  “Relevance of tidal effects and post-merger dynamics for binary neutron star parameter estimation”  In _Phys. Rev. D_ 98.8, 2018, pp. 084061  DOI: 10.1103/PhysRevD.98.084061
  * [19] Anuradha Samajdar and Tim Dietrich  “Waveform systematics for binary neutron star gravitational wave signals: effects of the point-particle baseline and tidal descriptions”  In _Phys. Rev. D_ 98.12, 2018, pp. 124030  DOI: 10.1103/PhysRevD.98.124030
  * [20] B.. Abbott  “GW150914: The Advanced LIGO Detectors in the Era of First Discoveries”  In _Phys. Rev. Lett._ 116.13, 2016, pp. 131103  DOI: 10.1103/PhysRevLett.116.131103
  * [21] A. Buikema et al.  “Sensitivity and performance of the Advanced LIGO detectors in the third observing run”  In _Phys. Rev. D_ 102.6, 2020, pp. 062003  DOI: 10.1103/PhysRevD.102.062003
  * [22] F. Acernese  “Advanced Virgo: a second-generation interferometric gravitational wave detector”  In _Class. Quant. Grav._ 32.2, 2015, pp. 024001  DOI: 10.1088/0264-9381/32/2/024001
  * [23] B.. Abbott  “Prospects for observing and localizing gravitational-wave transients with Advanced LIGO, Advanced Virgo and KAGRA”  In _Living Rev. Rel._ 21.1, 2018, pp. 3  DOI: 10.1007/s41114-020-00026-9
  * [24] Peter Fritschel et al.  “Report from the LSC Post-O5 Study Group”, 2022  URL: https://dcc.ligo.org/LIGO-T2200287/public
  * [25] L.. Wainstein and V.. Zubakov  “Extraction of Signals from Noise”, 1970
  * [26] Daniel Foreman-Mackey, David W. Hogg, Dustin Lang and Jonathan Goodman  “emcee: The MCMC Hammer”  In _Publ. Astron. Soc. Pac._ 125, 2013, pp. 306–312  DOI: 10.1086/670067
  * [27] C.. Biwer et al.  “PyCBC Inference: A Python-based parameter estimation toolkit for compact binary coalescence signals”  In _Publ. Astron. Soc. Pac._ 131.996, 2019, pp. 024503  DOI: 10.1088/1538-3873/aaef0b
  * [28] Neil J. Cornish  “Heterodyned likelihood for rapid gravitational wave parameter inference”  In _Phys. Rev. D_ 104.10, 2021, pp. 104054  DOI: 10.1103/PhysRevD.104.104054
  * [29] Barak Zackay, Liang Dai and Tejaswi Venumadhav  “Relative Binning and Fast Likelihood Evaluation for Gravitational Wave Parameter Estimation”, 2018  arXiv:1806.08792 [astro-ph.IM]
  * [30] Daniel Finstad and Duncan A. Brown  “Fast Parameter Estimation of Binary Mergers for Multimessenger Follow-up”  In _Astrophys. J. Lett._ 905.1, 2020, pp. L9  DOI: 10.3847/2041-8213/abca9e
  * [31] Murray Rosenblatt  “Remarks on Some Nonparametric Estimates of a Density Function”  In _The Annals of Mathematical Statistics_ 27.3 Institute of Mathematical Statistics, 1956, pp. 832–837  DOI: 10.1214/aoms/1177728190
  * [32] Thibault Damour and Alessandro Nagar  “Relativistic tidal properties of neutron stars”  In _Phys. Rev. D_ 80, 2009, pp. 084035  DOI: 10.1103/PhysRevD.80.084035
  * [33] Eanna E. Flanagan and Tanja Hinderer  “Constraining neutron star tidal Love numbers with gravitational wave detectors”  In _Phys. Rev. D_ 77, 2008, pp. 021502  DOI: 10.1103/PhysRevD.77.021502
  * [34] Tanja Hinderer, Benjamin D. Lackey, Ryan N. Lang and Jocelyn S. Read  “Tidal deformability of neutron stars with realistic equations of state and their gravitational wave signatures in binary inspiral”  In _Phys. Rev. D_ 81, 2010, pp. 123016  DOI: 10.1103/PhysRevD.81.123016


# Small $k$-pairable states

Nathan Claudet  Inria Mocqua, LORIA, CNRS, Université de Lorraine, F-54000
Nancy, France  Mehdi Mhalla  Université Grenoble Alpes, CNRS, Grenoble INP,
LIG, F-38000 Grenoble, France  Simon Perdrix  Inria Mocqua, LORIA, CNRS,
Université de Lorraine, F-54000 Nancy, France

###### Abstract

A $k$-pairable $n$-qubit state is a resource state that allows Local
Operations and Classical Communication (LOCC) protocols to generate EPR-pairs
among any $k$-disjoint pairs of the $n$ qubits. Bravyi et al. introduced a
family of $k$-pairable $n$-qubit states, where $n$ grows exponentially with
$k$. Our primary contribution is to establish the existence of ‘small’
pairable quantum states. Specifically, we present a family of $k$-pairable
$n$-qubit graph states, where $n$ is polynomial in $k$, namely
$n=O(k^{3}\ln^{3}k)$. Our construction relies on probabilistic methods.

Furthermore, we provide an upper bound on the pairability of any arbitrary
quantum state based on the support of any local unitary transformation that
has the shared state as a fixed point. This lower bound implies that the
pairability of a graph state is at most half of the minimum degree up to local
complementation of the underlying graph, i.e.,
$k(|{G}\rangle)\leqslant\lceil\delta_{loc}(G)/2\rceil$.

We also investigate the related combinatorial problem of $k$-vertex-minor
universality: a graph $G$ is $k$-vertex-minor universal if any graph on any
$k$ of its vertices is a vertex-minor of $G$. When a graph is $2k$-vertex-
minor universal, the corresponding graph state is $k$-pairable. More
precisely, one can create not only EPR-pairs but also any stabilizer state on
any $2k$ qubits through local operations and classical communication. We
establish the existence of $k$-vertex-minor universal graphs of order
$O(k^{4}\ln k)$.

Finally, we explore a natural extension of pairability in the presence of
errors or malicious parties and show that vertex-minor universality ensures a
robust form of pairability.

##  1 Introduction

In the realm of quantum communication networks, we often rely on classical
communication along with shared entanglement. Since classical communication
cannot create entanglement, we must rely on pre-existing entangled states to
perform non-trivial operations. For example, an EPR-pair
$\frac{1}{\sqrt{2}}(|{00}\rangle+|{11}\rangle)$ shared between two parties
allows the quantum teleportation of a qubit [3]. In this context, a highly
pertinent problem is to explore which resource states enable a group of $n$
parties, equipped with the capability of employing Local Operations and
Classical Communication (LOCC), to create entangled EPR pairs among any $k$
pairs of qubits. It is only recently that Bravyi et al. addressed this
fundamental inquiry and provided both upper and lower bounds for what they
call the $k$-pairability of quantum states, in terms of the number of parties
and the number of qubits per party needed for a quantum state to be
$k$-pairable [5]. However, before their work, numerous variations of this
problem had surfaced in the literature, some in the context of entanglement
routing [24, 15, 23], and some about problems that can be described as
variants of $k$-pairability, for example to prepare resource states by
clustering and merging [22]; starting from a particular network [13, 7];
creating one EPR pair hidden from other parties [19]; studying the complexity
and providing algorithms for generating EPR pairs within a predetermined set
[10, 9]; or taking into account the cost of distributing a graph state in
terms of EPR pairs [21, 14] (see [5] for a more detailed review).

Formally, an $n$-party state $|{\psi}\rangle$ is said to be $k$-pairable if,
for every $k$ disjoint pairs of parties
$\\{a_{1},b_{1}\\},\ldots,\\{a_{k},b_{k}\\}$, there exists a LOCC protocol
that starts with $|{\psi}\rangle$ and ends up with a state where each of those
$k$ pairs of parties shares an EPR-pair. Bravyi et al. studied $n$-party
states in the case where each party holds $m$ qubits, with $m$ ranging from 1
to $\ln(n)$. In the case where each party holds at least $10$ qubits, they
showed the existence of $k$-pairable states where $k$ is of the order of
$n/\text{polylog}(n)$, which is nearly optimal when $m$ is constant. They also
showed that if one allows a logarithmic number of qubits per party, then there
exist $k$-pairable states with $k=n/2$.

In the present paper, we focus on the scenario that is both the most natural
and challenging: when each party possesses precisely one qubit, i.e. $m=1$.
Bravyi et al. proved some results in this particular case. First, using Reed-
Muller codes, they were able to construct, for any $k$, a $k$-pairable state
of size exponential in $k$, namely $n=2^{3k}$, leaving the existence of a
$k$-pairable state of size $n=poly(k)$ as an open problem. They found a
2-pairable graph state of size $10$ and proved that there exists no stabilizer
state on less than 10 qubits that is 2-pairable using LOCC protocol based on
Pauli measurements.

Our contributions rely on the graph state formalism and the ability to
characterize properties of quantum states using tools from graph theory. In
particular, the pairability of a graph state is related to the standard notion
of vertex-minors. A graph $H$ is a vertex-minor of $G$ if one can transform
$G$ into $H$ by means of local complementations111Local complementation
according to a vertex $u$ consists in toggling the edges in the neighbourhood
of $u$. and vertex deletions. If $H$ is a vertex-minor of a $G$ then the graph
state $|{H}\rangle$ can be obtained from $|{G}\rangle$ using only single-qubit
Clifford operations, single-qubit Pauli measurements and classical
communications (we call these protocols CLOCC222In [10] this fragment of
operations is called LC + LPM + CC, and in [5] this corresponds to “LOCC
protocols based on Pauli measurements”. for Clifford LOCC). Dahlberg, Helsen,
and Wehner proved that the converse is also true when $H$ has no isolated
vertices [11]. In [10], they proved that it is NP-complete to decide whether a
graph state can be transformed into a set of EPR-pairs on specific qubits
using CLOCC protocols. In [9] they showed that it is also NP-complete to
decide whether a graph state can be transformed into another one using CLOCC
protocols.

We prove here the existence of an infinite family of $k$-pairable $n$-qubit
graph states, where the number of qubits $n$ is polynomial in $k$
(specifically $n=O(k^{3}\ln^{3}k)$), while the construction from Bravyi et al.
results in $k$-pairable states with an exponential number of qubits. For this
purpose, we first point out that a graph state $|{G}\rangle$ is $k$-pairable
if any matching of size $k$ (graph consisting of a set of $k$ disjoint edges)
is a vertex-minor of $G$. We then use probabilistic methods to prove the
existence of such $k$-pairable graph states with a number of qubits polynomial
in $k$.

We also provide an upper bound on the $k$-pairability of a graph state
$|{G}\rangle$, namely $k$ is at most half of the local minimum degree
$\delta_{\text{loc}}(G)$. The local minimum degree [6] refers to the minimum
degree of a vertex of $G$ subject to any sequence of local complementation.
The local minimum degree is related to the size of the smallest local set in a
graph [17], which we put to use here. Note, however, that the decision problem
associated with the computation of the local minimum degree of a graph has
been proven to be NP-complete and hard to approximate [20].

This bound is not directly comparable to the bound proposed by Bravyi et al.
[5], which, roughly speaking, implies that $k=O(n\frac{\ln\ln n}{\ln n})$. The
new bound is significantly better in certain cases; for instance, it directly
implies that graph states whose underlying graph has a vertex of constant
degree have constant pairability (as opposed to almost linear). However, it is
worth noting that there are graphs with a local minimum degree linear in their
number of vertices [20], although no explicit construction for such graphs is
known to our knowledge. In such cases, the bound provided by [5] can be better
than the one based on the local minimum degree by a logarithmic factor. In the
process of proving this bound on the pairability of graph state, we prove a
bound on the pairability of arbitrary quantum states, which depends on the
support of local unitaries that the state is a fixed point of.

From a combinatorial perspective, it is natural to consider graphs that
contain any graph of a given order as a vertex-minor, rather than solely
focusing on matchings. This leads us to introduce the notion of vertex-minor
universality. We say that a graph $G$ is $k$-vertex-minor universal if any
graph on any $k$ of its vertices is a vertex-minor of $G$. If a graph $G$ is
$k$-vertex-minor universal then one can create any stabilizer state on any $k$
qubits of the graph state $|{G}\rangle$ by CLOCC protocols. As a consequence,
if $G$ is $2k$-vertex-minor universal then $|{G}\rangle$ is $k$-pairable. We
prove the existence of an infinite family of $k$-vertex-minor universal
graphs, where the number of vertices $n$ is polynomial in $k$, namely
$n=O(k^{4}\ln k)$ using probabilistic methods. Moreover, a counting argument
implies that $n$ is at least quadratic in $k$, and we show that $k$ is upper-
bounded by the local minimum degree. Furthermore, we present minimal examples
of graphs that are $2$-, $3$-, and $4$-vertex-minor universal.

In the context of quantum networks, it is important to study robustness to
errors or malicious parties. For this purpose, we introduce a robust version
of pairability. We say that a $k$-pairable state $|{\psi}\rangle$ on a set of
qubits is $m$-robust if for any set of size at most $m$ of malicious partners,
the trusted partners can create $k$ EPR pairs among any $2k$ of them with an
LOCC protocol. We prove that vertex-minor universality ensures robust
pairability.

In Section 2, we define the pairability of a quantum state through the graph
state formalism. In Section 3, we prove upper bounds on the pairability of a
graph state, using in particular the local minimum degree. In Section 4, we
prove the existence of polynomial-size $k$-pairable graph states. In Section
5, we introduce the notion of $k$-vertex-minor universality and prove the
existence of polynomial-size $k$-vertex-minor universal graphs. We also
provide a table with a few examples of $k$-pairable states and $k$-vertex-
minor universal graphs for small values of $k$. Finally, in Section 6, we
define robust pairability and show how vertex-minor universality implies
robust pairability.

##  2 Quantum state pairability

We review in this section basic definitions of $k$-pairability and exemplify
this concept with existing and new illustrating instances. We extensively use
the graph state formalism [16], which is a standard family of quantum states
that can be represented using simple undirected graphs. Given a graph
$G=(V,E)$, the corresponding graph state $|{G}\rangle$ is the $|V|$-qubit
state:

$|{G}\rangle=\frac{1}{\sqrt{2}^{|V|}}\sum_{x\in
2^{V}}(-1)^{|G[x]|}|{x}\rangle$

where $|G[x]|$ is the size (number of edges) of the subgraph induced by $x$
(333With a slight abuse of notation we identify a subset (say
$x=\\{u_{2},u_{4}\\}$) of the set of qubits $V=\\{u_{1},\ldots u_{5}\\}$ with
its characteristic binary word ($x=01010$).).

A graph state $|{G}\rangle$ can be prepared as follows: initialize every qubit
in $|{+}\rangle=\frac{|{0}\rangle+|{1}\rangle}{\sqrt{2}}$ then apply for each
edge of the graph a $CZ:|{ab}\rangle\mapsto(-1)^{ab}|{ab}\rangle$ gate on the
corresponding pair of qubits. Notice that the graph state $|{G}\rangle$ is the
unique quantum state (up to a global phase) which is, for every vertex $u\in
V$, a fixed point of the Pauli operator $X_{u}Z_{N(u)}$ (444It consists in
applying $X:|{a}\rangle\mapsto|{1{-}a}\rangle$ on $u$ and
$Z:|{a}\rangle\mapsto(-1)^{a}|{a}\rangle$ on each of its neighbours in $G$.).

A matching $\pi$ of size $k$ and order $n$ is a graph on $n$ vertices made of
$k\leqslant\frac{n}{2}$ pairwise non-adjacent edges. The associated graph
state $|{\pi}\rangle$ is nothing but $k$ pairs of maximally entangled qubits
together with $n-2k$ fully separable qubits. Notice that there are
$\frac{n!2^{-k}}{k!(n-2k)!}$ matchings of size $k$ and order $n$.

A protocol that transforms an $n$-party state $|{\psi}\rangle$ into a state
$|{\varphi}\rangle$ is LOCC (resp. CLOCC) if it uses only local operations
(resp. local Clifford unitaries and Pauli measurements) and classical
communications between the parties. In this paper we consider only protocols
where each party is made of a single qubit.

######  Definition 1.

An $n$-qubit quantum state $|{\psi}\rangle$ is _$k$ -pairable_ if for every
matching $\pi$ of size $k$ and order $n$ there is an LOCC protocol
transforming $|{\psi}\rangle$ into $|{\pi}\rangle$.

######  Remark 1.

Here we only consider the case where each party is made of a single qubit,
please refer to [5] for a more general definition. Notice that in [5],
$k$-pairability is defined as the ability to produce any $k$ EPR pairs, which
is equivalent to Definition 1 since given a matching $\pi$ of size $k$,
$|{\pi}\rangle$ is, up to local Clifford unitaries, nothing but $k$ EPR pairs
together with $n-2k$ qubits in the $|{0}\rangle$-state.

For instance the GHZ state $\frac{|{0^{n}}\rangle+|{1^{n}}\rangle}{\sqrt{2}}$
is $1$-pairable. More generally, a graph state $|{G}\rangle$ is $1$-pairable
if and only if $G$ is connected. Bravyi et al. showed that the graph state –
they call the “wheel” – on $10$ qubits is $2$-pairable (Fig. 1.Left).

Figure 1: (Left) “Wheel” graph. (Right) Petersen graph

This example is somehow _minimum_ in the sense that there is no graph state on
at most $9$ qubits that are $2$-pairable using a CLOCC protocol. We introduce
a new example of $2$-pairable state on 10 qubits, namely the graph state
associated with the Petersen graph (Fig. 1.Right). We provide also an example
of $3$-pairable graph state associated with the 29-Paley graph555Given a prime
$q=1\bmod 4$, the $q$-Paley graph is a graph which vertices are elements of
the finite field $GF(q)$, such that two vertices share an edge if their
difference is a square in $GF(q)$. (on 29 vertices) which improves on the
$3$-pairable state on 32 qubits introduced in [5] (see Table 1).

Since pairability is defined by means of LOCC protocols, two quantum states
that are equal up to local unitaries (LU-equivalent for short) have the same
pairability.

A useful graph transformation to describe equivalent graph states by local
Clifford unitaries is local complementation. Given a graph $G$, a local
complementation according to a given vertex $u$ consists in complementing the
subgraph induced by the neighbourhood of $u$, leading to the graph $G\star
u=G\Delta K_{N(u)}$ where $\Delta$ is the symmetric difference and $K_{A}$ is
the complete graph on the vertices of $A$. It has been shown in [12] that if
two graphs are equivalent up to local complementation then the corresponding
graph states are LU-equivalent and hence have the same pairability.

Notice that the graph states associated with the “wheel” and the Petersen
graph are not LU-equivalent. Notice also that the Petersen graph has already
been pointed out as the smallest examples in various properties related to
local complementations [4, 16].

##  3 Upper bounds

It is known that the pairability of quantum states is sublinear in their
number of qubits, roughly speaking $k=O(n\frac{\ln\ln n}{\ln n})$ [5]. In this
section, we provide an alternative upper bound on the pairability of arbitrary
quantum states, depending on the support of local unitaries that the state is
a fixed point of. When applied to graph states, this upper bound can be
expressed in terms of graph parameters: local minimum degree (Corollary 1) and
vertex cover number (Corollary 2). Recall that the support of a local unitary
$U=\bigotimes_{v\in V}U_{v}$ is the set of qubits on which $U$ acts not
trivially: $supp(U)=\\{v\in V~{}|~{}U_{v}\not\propto I\\}$ (666We note
$U\propto V$ when $U=e^{i\phi}V$ for some angle $\phi$, and $U\not\propto V$
otherwise.).

######  Proposition 1.

If $|{\psi}\rangle$ is $k$-pairable and $U$ is a local unitary such that
$U\neq I$ and $U|{\psi}\rangle=|{\psi}\rangle$, then $2k\leqslant|supp(U)|$.

###### Proof.

By contradiction, assume there exist a $k$-pairable state $|{\psi}\rangle$ of
a register $V$ of qubits and a local unitary $U$ s.t.
$U|{\psi}\rangle=|{\psi}\rangle$ and $2k>|supp(U)|>0$. We consider a matching
$\pi$ such that every vertex in the support of $U$ is covered by an edge and
at least one edge has one vertex inside and one vertex outside $supp(U)$, i.e.
$\pi=(V,E)$ with $E=\\{(u_{i},v_{i})\\}_{i=1\ldots k}$, $u_{1}\in supp(U)$ and
$v_{1}\notin supp(U)$, and $supp(U)\subseteq C$ where
$C:=\\{u_{i}\\}_{i=1\ldots k}\cup\\{v_{i}\\}_{i=1\ldots k}$ is the set of
vertices covered by the matching. By hypothesis, the state $|{\pi}\rangle$ can
be obtained from the state $|{\psi}\rangle$ by an LOCC protocol (with non-zero
probability). Any LOCC protocol can be described by a completely trace-
preserving map, with separable Kraus operators. So there exists a product
Kraus operator $M=M_{1}\otimes M_{2}\otimes\dots\otimes M_{n}$ such that
$M|{\psi}\rangle=c_{\pi}|{\pi}\rangle$ for some $c_{\pi}\neq 0$. Notice that
$M_{u}$ is invertible when $u\in C$. Indeed, let $|{\varphi_{0}}\rangle$ and
$|{\varphi_{1}}\rangle$ be two independent eigenvectors of $M_{u}$. We have
$|{\psi}\rangle=|{\varphi_{0}}\rangle_{u}\otimes|{\psi_{0}}\rangle_{V\setminus
u}+|{{\varphi_{1}}}\rangle_{u}\otimes|{{\psi_{1}}}\rangle_{V\setminus u}$.

So $M|{\psi}\rangle=M_{u}|{\varphi_{0}}\rangle_{u}\otimes M_{V\setminus
u}|{\psi_{0}}\rangle_{V\setminus u}+M_{u}|{{\varphi_{1}}}\rangle_{u}\otimes
M_{V\setminus u}|{{\psi_{1}}}\rangle_{V\setminus u}=c_{\pi}|{\pi}\rangle$.
Since $u$ is entangled in $|{\pi}\rangle$ and $c_{\pi}\neq 0$, we have
$M_{u}|{\varphi_{0}}\rangle_{u}\neq 0$ and $M_{u}|{\varphi_{1}}\rangle_{u}\neq
0$, so $M_{u}$ is invertible. As a consequence, $M_{C}:=(\bigotimes_{u\in
C}M_{u})\otimes I_{V\setminus C}$ is invertible. We consider also
$M_{\overline{C}}:=M_{C}^{-1}M$ which commutes with $U$ by construction. We
show that $|{\pi}\rangle$ is a fixed point of $M_{C}UM_{\overline{C}}^{-1}$.
Indeed,
$c_{\pi}|{\pi}\rangle=MU|{\psi}\rangle=M_{C}M_{\overline{C}}U|{\psi}\rangle=M_{C}UM_{\overline{C}}|{\psi}\rangle=M_{C}UM_{C}^{-1}M_{C}M_{\overline{C}}|{\psi}\rangle=M_{C}UM_{C}^{-1}M|{\psi}\rangle\\\
=c_{\pi}M_{C}UM_{C}^{-1}|{\pi}\rangle$.

It implies on the pair of qubits $u_{1}(\in supp(U))$, $v_{1}(\notin
supp(U))$, that $|{\Phi}\rangle_{u_{1},v_{1}}$ is an eigenstate of
$M_{u_{1}}U_{u_{1}}M_{u_{1}}^{-1}\otimes I_{v_{1}}$, so there exists
$\lambda\in\mathbb{C}$ s.t.
$M_{u_{1}}U_{u_{1}}M_{u_{1}}^{-1}|{0}\rangle=\lambda|{0}\rangle$ and
$M_{u_{1}}U_{u_{1}}M_{u_{1}}^{-1}|{1}\rangle=\lambda|{1}\rangle$, as a
consequence $M_{u_{1}}U_{u_{1}}M_{u_{1}}^{-1}=\lambda I$, so
$U_{u_{1}}=\lambda I$. Since $U_{u_{1}}$ is unitary, we have $U_{u_{1}}\propto
I$ which contradicts the hypothesis $u_{1}\in supp(U)$. ∎

In the particular case of graph states, we can express this bound in terms of
an already-studied graph parameter on the corresponding graph, namely the
local minimum degree, which is the minimum degree up to local complementation:
$\delta_{loc}(G):=\min_{G\equiv_{LC}H}\delta(H)$ where $G\equiv_{LC}H$ means
that $G$ can be transformed into $H$ using a series of local complementations.
Indeed, the minimum support of a Pauli operator stabilizing a graph state
$|{G}\rangle$ is equal to $\delta_{loc}(G)+1$ [17]. It leads to the following
upper bound:

######  Corollary 1.

A graph state $|{G}\rangle$ is not
$\left(\left\lceil\delta_{\text{loc}}(G)/2\right\rceil+1\right)$-pairable.

###### Proof.

Since for any $u\in V$, $|{G}\rangle$ is a fixed point of $X_{u}Z_{N(u)}$,
$|{G}\rangle$ is also a fixed point of $\prod_{u\in D}X_{u}Z_{N(u)}=\pm
X_{D}Z_{\textup{Odd}({D})}$ for any $D\subseteq V$, where
$\textup{Odd}({D}):=\\{v\in V~{}|~{}|N(v)\cap D|=1\bmod 2\\}$. The support
$D\cup\textup{Odd}({D})$ of $X_{D}Z_{\textup{Odd}({D})}$ is called a local
set. The minimum size of a non-empty local set is known to be equal to
$\delta_{loc}(G)+1$ [17]. Thus, according to Proposition 1, $|{G}\rangle$ is
not $\left(\left\lceil\delta_{\text{loc}}(G)/2\right\rceil+1\right)$-pairable.
∎

This bound is tight, for instance the two graphs of Fig. 1 have local minimum
degree $3$ and the corresponding graph states are both $2$-pairable. We
believe that Corollary 1 generally provides a useful upper bound on the
pairability of a graph state as it is challenging to find a constructive
family of graphs with large local minimum degree. The family of hypercubes,
for example, has a logarithmic local minimum degree [17]. Paley graphs
provide, up to our knowledge, the best777‘Best’ here means with the largest
ratio local minimum degree divided by order of the graph. known constructive
family with graphs of order quadratic in their local minimum degree (see Table
1 for small Paley graphs).

However, it has been proved, using non-constructive probabilistic methods,
that for any (large enough) $n$ there is exists a graph of order $n$ and local
minimum degree greater than $0.189n$ [20], hence the upper bound provided by
Corollary 1 is not tight for such graphs as it is known that the pairability
of a quantum state is sublinear in its number of qubits ($k=O(n\frac{\ln\ln
n}{\ln n})$) [5].

Finally, the local minimum degree is related to the vertex cover number888I.e.
the size of the smallest set $S$ such that if $u$ and $v$ share an edge, then
$u\in S$ or $v\in S$. $\tau(G)$. Namely, the pairability of a graph state is
at most a quarter of its vertex cover number up to logarithmic terms:

######  Corollary 2.

A graph state $|{G}\rangle$ is not
$\left(\left\lceil\frac{\tau(G)+\log_{2}(\tau(G))}{4}\right\rceil+1\right)$-pairable.

###### Proof.

It is known that $2\delta_{\text{loc}}(G)\leqslant\tau(G)+\log_{2}(\tau(G))+1$
[6], and that we can remove the constant term when $\tau(G)\neq 1$. When
$\tau(G)=1$, we have
$\left\lceil\frac{\tau(G)+\log_{2}(\tau(G))}{4}\right\rceil=\left\lceil\frac{1+0}{4}\right\rceil=1=\left\lceil\frac{1+0+1}{4}\right\rceil=\left\lceil\frac{\tau(G)+\log_{2}(\tau(G))+1}{4}\right\rceil$.
∎

##  4 Existence of a polynomial-size $k$-pairable graph state

In this section, we prove the existence of an infinite family of $k$-pairable
graph states with a number of qubits that is polynomial in $k$. For this
purpose we describe a sufficient vertex-minor-based condition on a graph $G$
for the corresponding graph state $|{G}\rangle$ to be $k$-pairable.

_Vertex-minor_ is a standard notion in graph theory [18, 8]: Given two graphs
$H=(V_{H},E_{H})$ and $G=(V_{G},E_{G})$ such that $V_{H}\subseteq V_{G}$, $H$
is a vertex-minor of $G$ when $H$ can be obtained from $G$ by means of local
complementations and vertex deletions. It is well known that one can actually
transform $H$ into $G$ by applying first the local complementations and then
the vertex deletions. In other words, $H$ is the subgraph induced by $V_{H}$
in the graph $G\star u_{1}\star u_{2}\ldots\star u_{m}$ for some sequence of
vertices $u_{1},\ldots,u_{m}$.

If a graph $H$ is a vertex-minor of a graph $G$ then the graph state
$|{H}\rangle$ can be obtained from $|{G}\rangle$ by CLOCC protocols, the
converse is also true when $H$ has no isolated vertices [11]. Notice that a
perfect matching999A perfect matching is a graph where each vertex appears in
exactly one edge. has by definition no isolated vertices. Then,

######  Proposition 2.

A graph state $|{G}\rangle$ is $k$-pairable by CLOCC protocols if and only if
any perfect matching on any $2k$ vertices is a vertex-minor of $G$.

To prove the existence of ‘small’ graphs which admit any perfect matching on
any $2k$ vertices as vertex-minors we use probabilistic methods.

We consider a random Erdös Rényi graph $G(n,p)$ of order $n$ and such that
each edge is included in the graph with probability $p$, independently of
every other edge. The objective is to choose appropriate values of $p$ and $n$
to guarantee that the random graph admits, with a non-zero probability, every
perfect matching of size $k$ as a vertex-minor.

To do so, we are going to use the following lemma, which derives directly from
the union bound:

######  Lemma 1.

Let $\mathcal{A}=\\{A_{1},\dots,A_{d}\\}$ be a set of bad events in an
arbitrary probability space. If for all $A_{i}$, $Pr(A_{i})\leq p$ and $dp<1$,
then with a non-zero probability, none of the bad events occur:
$Pr(\overline{A_{1}},\dots,\overline{A_{d}})>0$.

###### Proof.

$Pr(\overline{A_{1}},\dots,\overline{A_{d}})=1-Pr(A_{1}\cup\dots\cup
A_{d})\geq 1-\sum_{i\in\llbracket 1,d\rrbracket}Pr(A_{i})\geq 1-dp>0$. ∎

In our context, a bad event is when the strategy described below fails to
induce a given perfect matching on a given set of vertices. Intuitively, in
order to induce a given perfect matching on a fixed set $K$ of vertices, one
has to toggle some edges, say $r$ edges. Such an edge $(a,b)$ can be toggled
by means of a local complementation on a vertex $u_{a,b}\notin K$ if $u_{a,b}$
is connected to both $a$ and $b$ but none of the other vertices of $K$. To
guarantee that each of the $r$ edges can be toggled independently, it is also
desirable that the corresponding $r$ vertices $u_{a,b}$ form an independent
set (see Fig. 2).

We first prove a technical lemma to upper bound the probability of the bad
event that such a configuration does not exist in a random graph:

$\boldsymbol{K}$$\boldsymbol{M}$$\boldsymbol{S}$$\boldsymbol{u_{i}}$$\boldsymbol{a_{i}}$$\boldsymbol{b_{i}}$
Figure 2: Illustration of the strategy of Lemma 2: we want to construct an
independent set $S$ of vertices in $M$ such that for any pair
$\\{a_{i},b_{i}\\}\in R$, there is a $u_{i}\in S$ s.t. $N_{K\cup
S}(u_{i})=\\{a_{i},b_{i}\\}$.

######  Lemma 2.

Given a random graph $G(n,p)$, let $K$ (of size $k$) and $M$ (of size $m$) be
two non-intersecting subsets of vertices, and $R\subseteq{K\choose 2}$ be a
set of $r$ pairs of vertices in $K$. The probability that for any independent
set $S\subseteq M$, $\exists\\{a,b\\}\in R$, s.t. $\forall u\in S$, $N(u)\cap
K\neq\\{a,b\\}$, is upper bounded by $re^{-(m-r)p^{2}(1-p)^{k+r-2}}$.

###### Proof.

Let $R=\\{\\{a_{1},b_{1}\\},\ldots\\{a_{r},b_{r}\\}\\}$. We consider the
complementary event $\overline{B}$: $\exists S\subseteq
M\text{~{}s.t.~{}}\forall i\in\llbracket 1,r\rrbracket,\exists u_{i}\in
S~{}s.t.~{}N_{K\cup S}(u_{i})=\\{a_{i},b_{i}\\}$, where $N_{A}(u):=N(u)\cap
A$. We describe in the following a greedy algorithm to find such a set $S$,
and then upper bound $Pr(B)$ by the probability that the algorithm fails.
First initialize $S$ as the empty set, and consider an arbitrary ordering on
the vertices of $M$. We will consider vertices $u$ of $M$ one after the other.
At each step, if $\exists i\in\llbracket 1,r\rrbracket$, $N_{K\cup
S}(u)=\\{a_{i},b_{i}\\}$, then we add $u$ to $S$, and we remove
$\\{a_{i},b_{i}\\}$ from $R$. When $R$ is empty, we are done. We note
$p(m,r,s)$ the probability that the algorithm fails if we start with a set $S$
of size $s$ (then the probability that the algorithm fails in general is
$p(m,r,0)$). We have $p(m,r,s)=1$ when $r>m$ and $p(m,0,s)=0$. More generally,
we show that:

$p(m,r,s)=rp^{2}(1-p)^{k+s-2}p(m-1,r-1,s+1)+\left(1-rp^{2}(1-p)^{k+s-2}\right)p(m-1,r,s)$

Indeed, at a given step of the algorithm, say that we consider the vertex
$u\in M$.

$\begin{split}&p(m,r,s)\\\ &=Pr(\text{the algorithm fails given m,r,s})\\\
&=\sum_{i\in\llbracket 1,r\rrbracket}Pr(\text{the algorithm fails given
m,r,s}|N_{K\cup S}(u)=\\{a_{i},b_{i}\\})Pr(N_{K\cup
S}(u)=\\{a_{i},b_{i}\\})\\\ &+Pr(\text{the algorithm fails given
m,r,s}|\forall i\in\llbracket 1,r\rrbracket,N_{K\cup
S}(u)\neq\\{a_{i},b_{i}\\})\\\ &\times Pr(\forall i\in\llbracket
1,r\rrbracket,N_{K\cup S}(u)\neq\\{a_{i},b_{i}\\})\\\
&=p(m-1,r-1,s+1)rp^{2}(1-p)^{k+s-2}+p(m-1,r,s)\left(1-rp^{2}(1-p)^{k+s-2}\right)\\\
&\text{using}~{}Pr(\forall i\in\llbracket 1,r\rrbracket,N_{K\cup
S}(u)\neq\\{a_{i},b_{i}\\})=1-\sum_{i\in\llbracket 1,r\rrbracket}Pr(N_{K\cup
S}(u)=\\{a_{i},b_{i}\\})\end{split}$

We will now prove by induction that for all $m,r,s\in\mathbb{N}\text{~{}such
that~{}}m\geqslant r$, $p(m,r,s)\leqslant re^{-(m-r)p^{2}(1-p)^{k+r+s-2}}$.
For the initialization, we need to prove that this is true for $p(r,r,s)$, for
any $r$ and $s$, as well as for $p(m,0,s)$, for any $m$ and $s$. We have
$p(m,0,s)=0$, so we just need $p(r,r,s)\leqslant r$ for any $r\geqslant 1$,
which is trivially true. Then, consider some
$s\in\mathbb{N},m,r\in\mathbb{N^{*}}\text{~{}such that~{}}m\geqslant r$, and
suppose that for $p(m-1,r-1,s+1)$ and $p(m-1,r,s)$, the property is true.

Then,

$\begin{split}&p(m,r,s)\\\
&=rp^{2}(1-p)^{k+s-2}p(m-1,r-1,s+1)+\left(1-rp^{2}(1-p)^{k+s-2}\right)p(m-1,r,s)\\\
&\leqslant rp^{2}(1-p)^{k+s-2}(r-1)e^{-(m-r)p^{2}(1-p)^{k+s+r-2}}\\\
&+\left(1-rp^{2}(1-p)^{k+s-2}\right)re^{-(m-r-1)p^{2}(1-p)^{k+s+r-2}}\\\
&=re^{-(m-r)p^{2}(1-p)^{k+s+r-2}}\left(p^{2}(1-p)^{k+s-2}(r-1)+\left(1-rp^{2}(1-p)^{k+s-2}\right)e^{p^{2}(1-p)^{k+s+r-2}}\right)\\\
&\leqslant
re^{-(m-r)p^{2}(1-p)^{k+s+r-2}}e^{p^{2}(1-p)^{k+s+r-2}}\left(p^{2}(1-p)^{k+s-2}(r-1)+\left(1-rp^{2}(1-p)^{k+s-2}\right)\right)\\\
&=re^{-(m-r)p^{2}(1-p)^{k+s+r-2}}e^{p^{2}(1-p)^{k+s+r-2}}\left(1-p^{2}(1-p)^{k+s-2}\right)\\\
&\leqslant
re^{-(m-r)p^{2}(1-p)^{k+s+r-2}}e^{p^{2}(1-p)^{k+s+r-2}}e^{-p^{2}(1-p)^{k+s-2}}\\\
&\leqslant re^{-(m-r)p^{2}(1-p)^{k+s+r-2}}\text{~{}~{}~{}~{} as $r\geqslant
0$}\end{split}$

At the end of the day, the probability that the algorithm fails is $p(m,r,0)$.
So $1-Pr(\exists S=\\{u_{1},\dots,u_{r}\\}\subseteq M\text{~{}s.t.~{}}\forall
i\in\llbracket 1,r\rrbracket,N_{K\cup S}(u_{i})=\\{a_{i},b_{i}\\})\leqslant
p(m,r,0)\leqslant re^{-(m-r)p^{2}(1-p)^{k+r-2}}$. ∎

We are now ready to prove the existence of $k$-pairable graph states on a
number of qubits cubic in $k$ (up to a logarithmic factor):

######  Proposition 3.

For any constant $c>\frac{125e^{2}}{4}\approx 231$, there exists $k_{0}$ s.t.
for any $k>k_{0}$, there exists a $k$-pairable graph state on $\lfloor
ck^{3}ln(k)^{3}\rfloor$ qubits.

###### Proof.

For this proof we will generate a random graph, and we will apply Lemma 1 to
show that with non-zero probability, such a graph satisfies the property of
Proposition 2, i.e. for any $k$ disjoint pairs
$\\{a_{1},b_{1}\\},...,\\{a_{k},b_{k}\\}$ of vertices, there exists a sequence
of local complementations that maps $G$ to a graph $G^{\prime}$ such that
$\pi$ is an induced subgraph of $G^{\prime}$, $\pi$ being the perfect matching
with vertices $V_{\pi}=\bigcup_{i\in[k]}\\{a_{i},b_{i}\\}$ and edges
$E_{\pi}=\bigcup_{i\in[k]}\\{(a_{i},b_{i})\\}$. That will allow us to claim
that the corresponding graph state is $k$-pairable, thus proving the
proposition. Let $m\in\mathbb{N}$ and $p\in[0,1]$ to be fixed later on. The
graph $G=(V,E)$, of order $n=m+2k$, will be generated by the Erdös Rényi
protocol: two vertices in $G$ are connected with probability $p$.

For some perfect matching $\pi$ represented by
$\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}$, the corresponding bad event
$A_{\pi}$ is: “We cannot induce the perfect matching $\pi$ by means of local
complementations on vertices from $V\setminus V_{\pi}$”. The first step of
this proof is to bound $Pr(A_{\pi})$. In order to be able to induce some
subgraph on $V_{\pi}$, it is sufficient to find an independent set $S\subseteq
V\setminus V_{\pi}$ of size ${2k\choose 2}$ such that for any $\\{a,b\\}\in
E_{\pi}$, $\exists u_{a,b}\in S$ s.t. $N_{V_{\pi}}(u_{a,b})=\\{a,b\\}$.
Indeed, one can induce any subgraph $H$ on $V_{\pi}$ by toggling each edge
$(a,b)$ of $G[V_{\pi}]\Delta H$ by means of a local complementation on
$u_{a,b}$. In our case, we do not always need to be able to flip all edges of
$V_{\pi}$, because we only want to induce one particular subgraph (the perfect
matching $\pi$). So the independent set that we look for might be of size less
than ${2k\choose 2}$. Let’s bound the probability of being able to construct
such an independent set $S$ (which will give a direct bound for
$Pr(A_{\pi})$). We will use the fact that, as $p$ will be chosen to be small
(not $1/2$), the number of edges to toggle will be linear in the vast majority
of cases. We will be calling $r$ the number of edges to toggle in $V_{\pi}$.
Let $t\in\mathbb{N}$ to be fixed later on. We will handle separately the cases
where $r\leqslant t$ and $r\geqslant t+1$.

$Pr(A_{\pi})=Pr(r\leqslant t).Pr(A_{\pi}|r\leqslant t)+Pr(r\geqslant
t+1).Pr(A_{\pi}|r\geqslant t+1)$

Let’s bound $Pr(r\leqslant t)$ and $Pr(A_{\pi}|r\geqslant t+1)$ by $1$, as
they are supposed to be very close to 1.

$Pr(A_{\pi})\leqslant Pr(A_{\pi}|r\leqslant t)+Pr(r\geqslant t+1)$

Using Lemma 2, $Pr(A_{\pi}|r\leqslant t)\leqslant
te^{-(m-t)p^{2}(1-p)^{2k+t-2}}$.

To bound $Pr(r\geqslant t+1)$, we’ll use some property of the binomial
distribution. To simplify, we’ll suppose we will always have to toggle the k
edges corresponding to the pairs of $K$. Let’s introduce a random variable $X$
that follows the distribution $B({2k\choose 2}-k,p)$. What we just said
amounts to writing: $Pr(r\geqslant t+1)\leqslant Pr(X\geqslant t+1-k)$.
Indeed, the edges that are not the pairs of $K$ have to be removed, and some
such edge exists with probability $p$. We’ll use the Chernoff bound: With
$\mu=\mathbb{E}[X]=p({2k\choose 2}-k)=2pk(k-1)$, for any $\delta>0$,
$Pr(X\geqslant(1+\delta)\mu)\leqslant e^{-\frac{\delta^{2}}{2+\delta}\mu}$. As
we need $(1+\delta)\mu=t+1-k$, we take $\delta=\frac{t+1-k-\mu}{\mu}$. The
Chernoff bound then gives

$Pr(X\geqslant t+1-k)\leqslant
e^{-\frac{\left(\frac{t+1-k-\mu}{\mu}\right)^{2}}{\left(\frac{t+1-k+\mu}{\mu}\right)}\mu}=e^{-\frac{\left(t+1-k-\mu\right)^{2}}{\left(t+1-k+\mu\right)}}$

At the end of the day, $Pr(A_{\pi})\leqslant
te^{-(m-t)p^{2}(1-p)^{2k+t-2}}+e^{-\frac{\left(t+1-k-2pk(k-1)\right)^{2}}{\left(t+1-k+2pk(k-1)\right)}}$.

The number of bad events is $d=\dfrac{n!}{k!(n-2k)!2^{k}}$. Using
$k!\geqslant\dfrac{k^{k}}{e^{k-1}}$, it’s upperbounded by
$\dfrac{n^{2k}e^{k-1}}{(2k)^{k}}=\dfrac{1}{e}\left(\dfrac{n^{2}e}{2k}\right)^{k}$.
To apply Lemma 1, we need $dp_{0}<1$, where
$p_{0}=te^{-(m-t)p^{2}(1-p)^{2k+t-2}}+e^{-\frac{\left(t+1-k-2pk(k-1)\right)^{2}}{\left(t+1-k+2pk(k-1)\right)}}$
is the upper bound on the probability of the bad events.

It’s sufficient to have:

$\textbf{(1)}~{}~{}e^{-\frac{\left(t+1-k-2pk(k-1)\right)^{2}}{\left(t+1-k+2pk(k-1)\right)}}\left(\dfrac{n^{2}e}{2k}\right)^{k}<\dfrac{e}{2}\text{~{}~{}and~{}~{}}\textbf{(2)}~{}~{}\left(te^{-(m-t)p^{2}(1-p)^{2k+t-2}}\right)\left(\dfrac{n^{2}e}{2k}\right)^{k}<\dfrac{e}{2}$

Let’s show that these equations are satisfied for any large enough $k$ by
choosing: $n=\left\lfloor c_{2}k^{3}\ln(k)^{3}\right\rfloor$, $t=\left\lfloor
c_{1}k\ln(k)\right\rfloor$ and $p=\frac{2}{2k+t}$ with $c_{1}>5$ and
$c_{2}>\frac{5e^{2}{c_{1}}^{2}}{4}>\frac{125e^{2}}{4}\approx 231$.

(1): The equation translates to
$k(2ln(n)+1-\ln(2k))<\frac{\left(t+1-k-2pk(k-1)\right)^{2}}{\left(t+1-k+2pk(k-1)\right)}+\ln(e/2)$.
$k(2ln(n)+1-\ln(2k))=k(2ln(\lfloor
c_{2}k^{3}\ln^{3}(k)\rfloor)+1-\ln(2k))\leqslant
k(2ln(c_{2})+6ln(k)+3\ln(\ln(k))+1-\ln(k)-\ln(2))\sim_{k\to\infty}5kln(k)$.
And
$\frac{\left(t+1-k-2pk(k-1)\right)^{2}}{\left(t+1-k+2pk(k-1)\right)}+\ln(e/2)\sim_{k\to\infty}t=\lfloor
c_{1}k\ln(k)\rfloor$. The choice of $c_{1}$ guarantees that for any large
enough $k$, (1) is satisfied.

(2): Using Lemma 3 (in the appendix), we get
$e^{-(m-t)p^{2}(1-p)^{2k+t-2}}\leqslant e^{-(m-t)\frac{4e^{-2}}{(2k+t)^{2}}}$,
so it’s sufficient to prove
$k(2ln(n)+1-\ln(2k))<(m-t)\frac{4e^{-2}}{(2k+t)^{2}}-\ln(t)+\ln(e/2)$. We just
saw that $k(2ln(n)+1-\ln(2k))\sim_{k\to\infty}5k\ln(k)$. Similarly, $m=n-2k$
so
$(m-t)\frac{4e^{-2}}{(2k+t)^{2}}-\ln(t)+\ln(e/2)\sim_{k\to\infty}c_{2}k^{3}\ln(k)^{3}\frac{4e^{-2}}{(c_{1}k\ln(k))^{2}}=\frac{c_{2}4e^{-2}kln(k)}{{c_{1}}^{2}}$.
The choice of $c_{2}$ guarantees that for any large enough $k$, (2) is
satisfied.

Then, according to Lemma 1, there exists a $k$-pairable graph state on $n$
qubits. ∎

##  5 Vertex-minor universality

In the previous section, we considered graphs on which we can induce any
perfect matching on any $2k$ vertices by means of local complementations. In
this section we introduce the natural combinatorial problem of being able to
induce any graph on any set of $k$ vertices:

######  Definition 2.

A graph $G$ is _$k$ -vertex-minor universal_ if any graph on any $k$ vertices
is a vertex-minor of $G$.

The associated property on quantum states is the ability to induce not only
EPR pairs, but any graph state on a given number of qubits by means of LOCC
protocols. As any stabilizer state is equivalent to a graph state under local
Clifford operations [12], it leads to the following generalization of
$k$-pairability:

######  Proposition 4.

If $G$ is a $k$-vertex-minor universal graph, then one can induce any
stabilizer state of on any set of $k$ qubits in the corresponding graph state
$|{G}\rangle$, by $CLOCC$ protocols.

Contrary to the pairability case (Proposition 2), the existence of CLOCC
protocols to induce any stabilizer states on $k$ qubits from a given graph
state $|{G}\rangle$ does not imply in general that $G$ is $k$-vertex-minor
universal. For instance, $K_{2}$ (graph with two vertices and one edge) is not
$2$-vertex-minor universal since no local complementation can turn it into an
empty graph. However, using CLOCC protocol (e.g. an X-measurement on each
qubit), one can map the corresponding graph state (a maximally entangled pair
of qubits) to the graph state composed a tensor product of two qubits.

Obviously, $2k$-vertex-minor universality implies $k$-pairability:

######  Corollary 3.

If $G$ is a $2k$-vertex-minor universal graph, then $|{G}\rangle$ is a
$k$-pairable graph state.

As pointed out by Sergey Bravyi101010Personal communication., a counting
argument leads to an upper bound on the vertex-minor universality:

######  Proposition 5.

If a graph $G$ of order $n$ is $k$-vertex-minor universal then
$k<\sqrt{2n\log_{2}(3)}+2$.

###### Proof.

If $H$ of order $k$ is a vertex-minor of $G$ of order $n$, then $|{H}\rangle$
can be obtained from $|{G}\rangle$ by means of local Pauli measurements on
$n-k$ qubits and local Clifford unitaries on $k$ qubits. There are 3 possible
Pauli measurements per qubit, so $3^{n-k}$ in total. Notice that for a fixed
choice of Pauli measurements, different local Clifford transformations on the
remaining $k$ qubits can only generate graph states which correspond to graphs
that are equivalent up to local complementation. Moreover, it is known that
there are at least $2^{\frac{k^{2}-5k}{2}-1}$ different graphs on $k$ vertices
up to local complementation [2]. As a consequence, if $G$ is $k$-vertex-minor
universal, we must have $3^{n-k}\geqslant 2^{\frac{k^{2}-5k}{2}-1}$. Using
numerical analysis, this implies $k<\sqrt{2n\log_{2}(3)}+2$. ∎

Another upper bound, based on the local minimum degree, can be obtained:

######  Proposition 6.

If a graph $G$ is $k$-vertex-minor universal then
$k<\delta_{\text{loc}}(G)+2$.

###### Proof.

By contradiction, assume there exists a graph $G$ that is
$(\delta_{\text{loc}}(G)+2)$-vertex-minor universal. $G$ contains a local set
$L=D\cup\textup{Odd}({D})$ of size $\delta_{\text{loc}}(G)+1$. By hypothesis,
there exists a sequence of local complementations that maps $G$ to a graph
$G^{\prime}$ such that $G^{\prime}[V(H)]=H$, where $H$ is the graph defined on
$L\cup v$ ($v$ being an arbitrary vertex of $V\setminus L$), such that its
only edge is between $v$ and an arbitrary vertex $u\in L$. Note that a local
set is invariant by local complementation [17]. This means $L$ is still a
local set in $G^{\prime}$, i.e. there exists $D^{\prime}$ s.t.
$L=D^{\prime}\cup\textup{Odd}({D^{\prime}})$. If $u\in D^{\prime}$ then $v\in
Odd(D^{\prime})$. If $u\notin D^{\prime}$ then $u\notin Odd(D^{\prime})$
because it’s not connected to any other vertex of $L$. This contradicts that
$L$ is still a local set. ∎

To illustrate the concept of vertex-minor universality, we provide minimal
examples of $k$-vertex-minor universal graphs for $k$ up to $4$. The vertex-
minor universality (and pairability) of the graphs below and in table Table 1
was observed by numerical analysis. The code consists of an exploration of the
orbit of a given graph by local complementation (either by using essentially a
breadth-first search, or by applying local complementations on random
vertices, which yields results faster), to find the ${n\choose k}2^{k\choose
2}$ possible induced subgraphs of order $k$.

### 2-vertex-minor universality.

As we saw above, $K_{2}$ is 1-pairable but not 2-vertex-minor universal:
$K_{3}$ is actually the smallest 2-vertex-minor universal graph, because every
edge can be toggled by a local complementation on the opposite vertex.

### 3-vertex-minor universality.

We observed that $C_{6}$ (the cycle of order 6) is a 3-vertex-minor universal
graph, and there exist no 3-vertex-minor universal graphs of order smaller or
equal to $5$. Indeed, using the database from [1] along with Proposition 6, it
appears that the only graph of order smaller or equal to $5$ having a local
minimum degree larger or equal to 2 (thus being a candidate for 3-vertex-minor
universality) is $C_{5}$. We have observed however that $C_{5}$ is not
3-vertex-minor universal by exploring its orbit by local complementation
composed of 132 graphs, and checking that none of them contains an independent
set of size 3.

### 4-vertex-minor universality.

We observed that the 10-vertex “wheel” graph from [5] (see Fig. 1) whose
corresponding graph state has been proven to be 2-pairable, is also 4-vertex-
minor universal. Bravyi et al. showed that no graph state with $9$ or less
qubits was 2-pairable using CLOCC protocols. Besides, any graph state
corresponding to a 4-vertex-minor universal graph is 2-pairable using CLOCC
protocols. Thus, there is no 4-vertex-minor universal graph of order smaller
than $10$. We also observed that the Petersen graph (of order 10) is 4-vertex-
minor universal (and thus 2-pairable).

These practical results, along with results for small Paley graphs, are
summarized in Table 1.

graph $G$ | order | $\delta_{\text{loc}}(G)$ | 1-p? | 2-vmu? | 3-vmu? | 2-p? | 4-vmu? | 5-vmu? | 3-p?
---|---|---|---|---|---|---|---|---|---
$K_{2}$ | 2 | 1 | yes | no |  |  |  |  |
$K_{3}$ | 3 | 2 | yes | yes | no |  |  |  |
$C_{6}$ | 6 | 2 | yes | yes | yes | no [cor 1] | no [prop 6] | no [prop 6] | no [cor 1]
“Wheel” graph | 10 | 3 | yes | yes | yes | yes | yes | no [prop 6] | no [cor 1]
Petersen graph | 10 | 3 | yes | yes | yes | yes | yes | no [prop 6] | no [cor 1]
13-Paley graph | 13 | 4 | yes | yes | yes | yes | yes | no | no [cor 1]
17-Paley graph | 17 | 4 | yes | yes | yes | yes | yes | yes | no [cor 1]
29-Paley graph | 29 | 10 | yes | yes | yes | yes | yes | yes | yes

Table 1: A table summarizing the pairability of some graph states, and the
vertex-minor universality of some graphs. “$k$-p?” is to be understood as “is
the graph state $|{G}\rangle$ $k$-pairable?” and “$k$-vmu?” is to be
understood as “is the graph $G$ $k$-vertex-minor universal?”. “yes” results
were obtained by numerical analysis, by exploring the orbit of the graphs by
local complementation, so we were able to check that each graph has the
required vertex-minors. “no [$\cdot$]” results are direct applications of
Corollary 1 and Proposition 6 (we had to compute the local minimum degree of
each graph: this was done by brute force by computing every local set).
$K_{2}$ not being 2-vertex-minor universal and $K_{3}$ not being 3-vertex-
minor universal can be verified by checking the (very small) orbit by local
complementation of these two graphs. The orbit by local complementation of the
13-Paley graph is, however, too big to be computed. To prove that this graph
is not $5$-vertex-minor universal, we showed, using a slightly modified
version of the program used in [5], that no fully separable quantum state can
be induced on the first 5 qubits by means of CLOCC protocols (which implies
that the independent set on the first 5 vertices is not a vertex-minor of the
graph).

We prove the existence of an infinite family of $k$-vertex-minor universal
graphs whose order is polynomial in $k$:

######  Proposition 7.

For any constant $c>\frac{3e^{2}}{4}\approx 5.54$, there exists $k_{0}$ s.t.
for any $k>k_{0}$, there exists a $k$-vertex-minor universal graph of order at
most $ck^{4}\ln(k)$.

###### Proof.

For this proof we will generate a random $(k+1)$-partite graph, and we will
apply Lemma 1 to show that with non-zero probability, such a graph is
$k$-vertex-minor universal. Let $m\in\mathbb{N}$ to be fixed later on. The
graph $G=(V,E)$, of order $n=m(k+1)$, will be generated as follows. Consider
$k+1$ sets of $m$ vertices $V_{0}$, $V_{1}$, $\dots$, $V_{k}$ that form a
partition of $V$. Two vertices $u\in V_{i}$ and $v\in V_{j}$ in $G$ are not
connected if $i=j$ (so any $V_{i}$ is an independent set), and are connected
with probability $p\in[0,1]$ if $i\neq j$.

For any $K\in{V\choose k}$, let $V^{(K)}\in\\{V_{0},\ldots,V_{k}\\}$ s.t.
$K\cap V^{(K)}=\emptyset$. Notice that if for any pair $\\{a,b\\}\in{K\choose
2}$ there exists a vertex $u_{a,b}\in V^{(K)}$ s.t. $N(u_{a,b})\cap
K=\\{a,b\\}$ then one can induce any subgraph $H$ on $K$ by toggling each edge
$(a,b)$ of $G[K]\Delta H$ by means of a local complementation on $u_{a,b}$.

Given $K\in{V\choose k}$ and $\\{a,b\\}\in{K\choose 2}$, let $A_{K,a,b}$ be
the bad event: “$\forall u\in V^{(K)}$, $N_{K}(u)\neq\\{a,b\\}$”. Since the
probability for a given $u\in V^{(K)}$ to satisfy $N_{K}(u)=\\{a,b\\}$ is
$p^{2}(1-p)^{k-2}$ we have:

$\displaystyle Pr(A_{K,a,b})$ $\displaystyle=$
$\displaystyle\left(1-p^{2}(1-p)^{k-2}\right)^{m}$ $\displaystyle\leqslant$
$\displaystyle e^{-mp^{2}(1-p)^{k-2}}$

We fix $p=\frac{2}{k}$, as it minimizes $e^{-mp^{2}(1-p)^{k-2}}$ (see Lemma 3
in the appendix), and get

$Pr(A_{K,a,b})\leqslant e^{-4e^{-2}mk^{-2}}$

The number of bad events is $d={m(k+1)\choose k}{k\choose 2}$ which is
upperbounded by ${m(k+1)\choose k+1}$ when $m>{k\choose 2}$ (see Lemma 4 in
the appendix). To apply Lemma 1, we need $dp_{0}<1$, where
$p_{0}=e^{-4e^{-2}mk^{-2}}$ is the upper bound on the probability of the bad
events.

$\displaystyle dp_{0}$ $\displaystyle\leqslant$ $\displaystyle{m(k+1)\choose
k+1}e^{-4e^{-2}mk^{-2}}$ $\displaystyle\leqslant$ $\displaystyle
2^{m(k+1)H(\frac{1}{m})}e^{-4e^{-2}mk^{-2}}$ $\displaystyle=$ $\displaystyle
e^{m(k+1)H(\frac{1}{m})\ln(2)-4e^{-2}mk^{-2}}$

where $H(x)=-x\log_{2}(x)-(1-x)\log_{2}(1-x)$ is the binary entropy.

By choosing $m=\left\lfloor c\frac{k^{4}}{k+1}\ln(k)\right\rfloor$ with
$c>\frac{3e^{2}}{4}\approx 5.54$, we have
$m(k+1)H(\frac{1}{m})\ln(2)\sim_{k\to\infty}3k\ln(k)$ and
$4e^{-2}mk^{-2}\sim_{k\to\infty}4e^{-2}ck\ln(k)$. The choice of $c$ guaranteed
that for any large enough $k$,

$e^{m(k+1)H(\frac{1}{m})\ln(2)-4e^{-2}mk^{-2}}<1,$

and thus, according to Lemma 1, there exists a graph of order $m(k+1)$ which
is $k$-vertex-minor universal. ∎

##  6 Robust pairability

In this section, we explore a natural extension of pairability in the presence
of errors or malicious parties. We say that a $k$-pairable state is $m$-robust
if one can create any $k$ pairs of maximally entangled qubits, independently
of the actions of any set of $m$ identified malicious parties:

######  Definition 3.

A $k$-pairable state $|{\psi}\rangle$ on a set $V$ of qubits is _$m$ -robust_
if for any set $M\subseteq V$ of size at most $m$ and any matching $\pi$ of
size $k$ on the vertices $V\setminus M$, there is an LOCC protocol that
transforms $\rho=Tr_{M}(|{\psi}\rangle\left\langle\psi\right|)$ into
$|{\pi}\rangle$.

Vertex-minor universal graphs provide robust pairable quantum states:

######  Proposition 8.

If $G$ is a $k$-vertex-minor universal graph then for any
$k^{\prime}\leqslant\frac{k}{2}$, $|{G}\rangle$ is a $(k-2k^{\prime})$-robust
$k^{\prime}$-pairable state.

###### Proof.

Let $G$ be a $k$-vertex-minor universal graph, $M$ a set of at most
$k-2k^{\prime}$ vertices and $K$ a (disjoint) set of $2k^{\prime}$ vertices.
We consider any matching $\tau$ of size $k^{\prime}$ on the vertices $K\cup
M$, such that each vertex of $K$ is of degree 1, and those of $M$ are of
degree $0$. It is enough to show that there is an LOCC protocol transforming
$Tr_{M}(|{G}\rangle\left\langle G\right|)$ into $|{\tau[K]}\rangle$.

As $\tau$ is of order $|K|+|M|\leqslant k$, $\tau$ is a vertex-minor of $G$,
hence there exists a sequence of local complementations transforming $G$ into
$G^{\prime}$ such that $G^{\prime}[K\cup M]=\tau$. In terms of graph state, it
means that there are local (Clifford) unitaries $U_{M}$ (acting on the qubits
of $M$) and $U_{\overline{M}}$ (acting on the other qubits) s.t.
$U_{M}U_{\overline{M}}|{G}\rangle=|{G^{\prime}}\rangle$. Notice that applying
$U_{\overline{M}}$ on $\rho=Tr_{M}(|{G}\rangle\left\langle G\right|)$ leads to
the state $\rho^{\prime}=U_{\overline{M}}Tr_{M}(|{G}\rangle\left\langle
G\right|)U^{\dagger}_{\overline{M}}=Tr_{M}(U_{\overline{M}}U_{M}|{G}\rangle\left\langle
G\right|U^{\dagger}_{\overline{M}}U^{\dagger}_{M})=Tr_{M}(|{G^{\prime}}\rangle\left\langle
G^{\prime}\right|)$. Thus, from now on, we assume that the overall state is
$|{G^{\prime}}\rangle$, and we show that $|{G^{\prime}}\rangle$ can be turned
into $|{\tau[K]}\rangle$ without the help of the parties in $M$.

Vertex deletions can be implemented by means of standard basis measurements
and local corrections, more precisely, to transform $|{G^{\prime}}\rangle$
into $|{G^{\prime}\setminus u}\rangle$, one can measure $u$ leading to the
state $Z_{N(u)}^{s_{u}}|{G^{\prime}\setminus u}\rangle$ where
$s_{u}\in\\{0,1\\}$ is the classical outcome of the measurement. As a
consequence, the measurements of the qubits $V\setminus(K\cup M)$ of
$|{G^{\prime}}\rangle$ lead to the state $|{G^{\prime}[K\cup
M]}\rangle=|{\tau}\rangle$ up to some $Z$ corrections which depends on the
classical outcomes of the measurements, thus the state is before any classical
communications and corrections, of the form $Z_{A}Z_{B}|{\tau}\rangle$ for
some subsets $A\subseteq K$, $B\subseteq M$. The parties of $V\setminus(K\cup
M)$ send their classical outcomes to the parties of $K$ so that the correction
$Z_{A}$ can be applied leading to the state $Z_{B}|{\tau}\rangle$. As the
qubits of $M$ are separable for those of $K$ in $|{\tau}\rangle$ (the only
edges of $\tau$ are inbetween vertices of $K$), tracing out the qubits of $M$
in the state $Z_{B}|{\tau}\rangle$ leads to $|{\tau[K]}\rangle$. ∎

##  7 Conclusion

We showed here that there exist polynomial size $k$-pairable quantum states
and provided new upper bounds for $k$-pairability. We also introduced a new
related combinatorial notion called vertex-minor universality, for which we
gave similar properties, showing the existence of polynomial size graphs that
are $k$-vertex-minor universal and providing lower bounds for $k$-vertex-minor
universality based on the minimum degree by local complementation. We also
provided minimal examples of $k$-vertex-minor universal graphs for small
values of $k$. Finally, we initiated the study of a robust version of
$k$-pairability, in the presence of errors or malicious parties.

This leaves open some questions for future work.

  * •

Our proof for the existence of polynomial-size $k$-pairable quantum states is
non-constructive, and their size might be far from optimal. Explicit
constructions of polynomial-size $k$-pairable quantum states in the same
manner as the Reed-Muller CSS states from Bravyi et al., would be the logical
next step. Paley graphs, thanks to their ‘large’ local minimum degrees, are
candidates to provide good $k$-pairable states, using potentially even less
qubits than those exhibited by non-constructive probabilistic methods in this
paper. Similar questions also naturally apply to the explicit constructions of
$k$-vertex-minor universal graphs.

  * •

Pairability of graph states, when restricted to CLOCC protocols, is fully
characterized by the combinatorial properties of the associated graph (see
Proposition 2). Does it extend to pairability with arbitrary LOCC protocols?
Does there exist a $k$-pairable graph state which is not $k$-pairable by means
of CLOCC protocols?

  * •

Even though $2k$-vertex-minor universality is a stronger requirement than
$k$-pairability, it is not clear whether there exist $k$-pairable graph states
on more than $2$ vertices whose underlying graphs are not $2k$-vertex-minor
universal.

  * •

The $k$-pairable graph states that exist with non-zero probability - as shown
in the proof of Proposition 3 \- satisfy the following property: in order to
create $k$ particular EPR-pairs, one can compute the local operations to be
applied on the graph state (or, equivalently, the local complementation to be
applied on the underlying graph: there are $O(k^{2})$ of them) in polynomial
time. This is a consequence of the fact that the independent set in the proof
is found using a greedy algorithm. This raises the question of which
$k$-pairable states possess this property. Furthermore, we could study how to
generate graphs where the greedy algorithm works for every EPR-pair with high
probability (whereas in this work we only show the existence of one such
graph). A similar discussion is pertinent in the case of $k$-vertex-minor
universal graphs.

## Acknowledgements

We thank Sergey Bravyi and Ronald de Wolf for fruitful comments on an early
version of this paper. This work is supported by the PEPR integrated project
EPiQ ANR-22-PETQ-0007 part of Plan France 2030, by the STIC-AmSud project
Qapla’ 21-STIC-10, by the QuantERA grant EQUIP ANR-22-QUA2-0005-01, and by the
European projects NEASQC and HPCQS.

## References

  * [1] Jeremy C. Adcock, Sam Morley-Short, Axel Dahlberg, and Joshua W. Silverstone.  Mapping graph state orbits under local complementation.  Quantum, 4:305, Aug 2020.  arXiv:1910.03969, doi:10.22331/q-2020-08-07-305.
  * [2] Mohsen Bahramgiri and Salman Beigi.  Enumerating the classes of local equivalency in graphs.  2007\.  arXiv:math/0702267.
  * [3] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters.  Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.  Physical Review Letters, 70:1895–1899, Mar 1993.  doi:10.1103/PhysRevLett.70.1895.
  * [4] André Bouchet.  Recognizing locally equivalent graphs.  Discrete Mathematics, 114(1):75–86, 1993.  doi:10.1016/0012-365X(93)90357-Y.
  * [5] Sergey Bravyi, Yash Sharma, Mario Szegedy, and Ronald de Wolf.  Generating $k$ EPR-pairs from an $n$-party resource state.  Quantum Information Processing, 2023.  arXiv:2211.06497.
  * [6] David Cattanéo and Simon Perdrix.  Minimum degree up to local complementation: Bounds, parameterized complexity, and exact algorithms.  In Khaled Elbassioni and Kazuhisa Makino, editors, Algorithms and Computation, pages 259–270. Springer Berlin Heidelberg, 2015.  arXiv:1503.04702, doi:10.1007/978-3-662-48971-0_23.
  * [7] Patricia Contreras-Tejada, Carlos Palazuelos, and Julio I. de Vicente.  Asymptotic survival of genuine multipartite entanglement in noisy quantum networks depends on the topology.  Physical Review Letters, 128(22), 2022.  arXiv:2106.04634, doi:10.1103/physrevlett.128.220501.
  * [8] Bruno Courcelle and Sang il Oum.  Vertex-minors, monadic second-order logic, and a conjecture by Seese.  Journal of Combinatorial Theory, Series B, 97(1):91–126, 2007.  doi:10.1016/j.jctb.2006.04.003.
  * [9] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner.  How to transform graph states using single-qubit operations: computational complexity and algorithms.  Quantum Science and Technology, 5(4):045016, Sep 2020.  arXiv:1805.05306, doi:10.1088/2058-9565/aba763.
  * [10] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner.  Transforming graph states to Bell-pairs is NP-Complete.  Quantum, 4:348, Oct 2020.  arXiv:1907.08019, doi:10.22331/q-2020-10-22-348.
  * [11] Axel Dahlberg and Stephanie Wehner.  Transforming graph states using single-qubit operations.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(2123):20170325, 2018.  arXiv:1805.05305, doi:10.1098/rsta.2017.0325.
  * [12] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor.  Graphical description of the action of local clifford transformations on graph states.  Physical Review A, 69(2), Feb 2004.  arXiv:quant-ph/0308151, doi:10.1103/physreva.69.022316.
  * [13] Gang Du, Tao Shang, and Jian-wei Liu.  Quantum coordinated multi-point communication based on entanglement swapping.  Quantum Information Processing, 16, Mar 2017.  doi:10.1007/s11128-017-1558-2.
  * [14] Alex Fischer and Don Towsley.  Distributing graph states across quantum networks.  In IEEE International Conference on Quantum Computing and Engineering (QCE), pages 324–333, 2021.  arXiv:2009.10888, doi:10.1109/QCE52317.2021.00049.
  * [15] Frederik Hahn, Anna Pappa, and Jens Eisert.  Quantum network routing and local complementation.  npj Quantum Information, 5(1):1–7, 2019.  arXiv:1805.04559, doi:10.1038/s41534-019-0191-6.
  * [16] Mayan Hein, W. Dür, Jens Eisert, Robert Raussendorf, M. Nest, and H. Briegel.  Entanglement in graph states and its applications.  162, Mar 2006.  arXiv:quant-ph/0602096, doi:10.3254/978-1-61499-018-5-115.
  * [17] Peter Høyer, Mehdi Mhalla, and Simon Perdrix.  Resources Required for Preparing Graph States.  4288:638 – 649, Dec 2006.  URL: https://hal.archives-ouvertes.fr/hal-01378771, doi:10.1007/11940128\\_64.
  * [18] Sang il Oum.  Rank-width and vertex-minors.  Journal of Combinatorial Theory, Series B, 95(1):79–100, 2005.  doi:10.1016/j.jctb.2005.03.003.
  * [19] Jessica Illiano, Michele Viscardi, Seid Koudia, Marcello Caleffi, and Angela Sara Cacciapuoti.  Quantum internet: from medium access control to entanglement access control.  2022\.  arXiv:2205.11923.
  * [20] Jérôme Javelle, Mehdi Mhalla, and Simon Perdrix.  On the minimum degree up to local complementation: Bounds and complexity.  In Graph-Theoretic Concepts in Computer Science, pages 138–147. Springer Berlin Heidelberg, 2012.  doi:10.1007/978-3-642-34611-8_16.
  * [21] Clément Meignant, Damian Markham, and Frédéric Grosshans.  Distributing graph states over arbitrary quantum networks.  Physical Review A, 100:052333, Nov 2019.  arXiv:1811.05445, doi:10.1103/PhysRevA.100.052333.
  * [22] Jorge Miguel-Ramiro, Alexander Pirker, and Wolfgang Dür.  Optimized quantum networks.  Quantum, 7:919, Feb 2023.  arXiv:2107.10275, doi:10.22331/q-2023-02-09-919.
  * [23] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha.  Routing entanglement in the quantum internet.  npj Quantum Information, 5(1):1–9, 2019.  arXiv:1708.07142, doi:10.1038/s41534-019-0139-x.
  * [24] Eddie Schoute, Laura Mancinska, Tanvirul Islam, Iordanis Kerenidis, and Stephanie Wehner.  Shortcuts to quantum network routing.  2016\.  arXiv:1610.05238.

## Appendix: Technical lemmas

######  Lemma 3.

Given $c>0$, the value of $x$ that maximizes $f:x\rightarrow x^{2}(1-x)^{c}$
is $x=\frac{2}{c+2}$. Also,
$f(\frac{2}{c+2})\leqslant\frac{4e^{-2}}{(c+2)^{2}}$.

###### Proof.

$f^{\prime}(x)=2x(1-x)^{c}-x^{2}(1-x)^{c-1}c=x(1-x)^{c-1}(2(1-x)-cx)=x(1-x)^{c-1}(2-(c+2)x)$.
We note that $f^{\prime}(x)=0$ when $x=\frac{2}{c+2}$. Also, $f(x)\leqslant
x^{2}e^{-\frac{xc}{1-x}}$, and
$\frac{\frac{2}{c+2}c}{1-\frac{2}{c+2}}=\frac{\frac{2}{c+2}c}{\frac{c}{c+2}}=2$,
so $f(\frac{2}{c+2})\leqslant\frac{4e^{-2}}{(c+2)^{2}}$. ∎

######  Lemma 4.

For any $k>1$, any $m>{k\choose 2}$,

${m(k+1)\choose k}{k\choose 2}\leqslant{m(k+1)\choose k+1}$

###### Proof.

$\begin{split}\frac{{m(k+1)\choose k+1}}{{m(k+1)\choose k}{k\choose
2}}&=\frac{(m(k+1))!}{(m(k+1)-k-1)!(k+1)!}\frac{(m(k+1)-k)!k!}{(m(k+1))!}\frac{2!(k-2)!}{k!}=\frac{2(m(k+1)-k)}{(k+1)k(k-1)}\\\
&\geqslant\frac{2\left(\left({k\choose
2}+1\right)(k+1)-k\right)}{(k+1)k(k-1)}=\frac{2\left({k\choose
2}(k+1)+1\right)}{(k+1)k(k-1)}=\frac{(k-1)k(k+1)+2}{(k+1)k(k-1)}\\\
&=1+\frac{2}{(k+1)k(k-1)}\geqslant 1\end{split}$

∎