# Base Layer Efficiency in Scalable Human-Machine Coding

###### Abstract

A basic premise in scalable human-machine coding is that the base layer is
intended for automated machine analysis and is therefore more compressible
than the same content would be for human viewing. Use cases for such coding
include video surveillance and traffic monitoring, where the majority of the
content will never be seen by humans. Therefore, base layer efficiency is of
paramount importance because the system would most frequently operate at the
base-layer rate. In this paper, we analyze the coding efficiency of the base
layer in a state-of-the-art scalable human-machine image codec, and show that
it can be improved. In particular, we demonstrate that gains of 20-40% in BD-
Rate compared to the currently best results on object detection and instance
segmentation are possible.

Index Terms—  Human-machine coding, scalable coding, learning-based
compression

##  1 Introduction

Traditionally, image and video codecs have been developed to minimize the
bitrate required to support human viewing of the visual content. Codecs such
as JPEG, JPEG2000, and H.26X have become enabling technologies for many
multimedia services. Increasingly, however, visual content is also “viewed” by
machines for the purpose of automated analysis. Examples include traffic
monitoring, visual surveillance, autonomous driving, and others. This has
spurred interest in the development of codecs optimized for machine-based
analysis [1, 2], which have demonstrated significant bit savings compared to
coding for human viewing. Reasons for these bit savings have also been
supported by rate-distortion theory [3].

In applications such as traffic monitoring, analysis tasks – such as object
detection, tracking, speed estimation – are supposed to run continuously,
while human viewing may be necessary on occasion to assess a certain situation
of interest, for example an accident. For these applications, codecs would
need to support both machine analysis and human viewing. This has inspired
human-machine scalable codecs [4, 5, 3], where the base layer supports machine
analysis tasks, while the enhancement layer supports human viewing.

Our focus in this paper is on a scalable human-machine image codec [3], which
presents state-of-the-art (SOTA) results for the cases of object detection +
human viewing and object detection + instance segmentation + human viewing. In
applications that require such scalable coding, the efficiency of the base
layer is crucial, because the machine analysis runs continuously while human
viewing is only needed occasionally. Our main goal here is to improve the
efficiency of the base layer. Our contributions are as follows:

  * •

We show that, despite its good performance, the base layer in [3] is
inefficient. We explain the source of this inefficiency, and propose a way to
optimize the base-layer efficiency in human-machine scalable coding.

  * •

We demonstrate coding gains of up to 20-40% in BD-Rate over [3] for the base
tasks of object detection and instance segmentation, setting, to our
knowledge, new SOTA rate-accuracy results on these tasks.

Section 2 briefly reviews related work. The proposed method is described in
Section 3. Experimental results are presented in Section 4, followed by
conclusions in Section 5.

Fig. 1: Scalable human-machine coding by latent-space partitioning [3]

##  2 Related work

Although coding for machines can be performed using conventional handcrafted
codecs [1, 2, 6], learning-based codecs offer greater flexibility to exploit
redundancies encountered in this kind of compression. Learning-based image
codecs have come a long way recently [7, 8, 9, 10, 11, 12], rivaling the
performance of the best handcrafted codecs, especially on perceptual metrics
like Structural Similarity Index Metric (SSIM). The general processing chain
of recent learned image codecs can be described as
$X\overset{g_{a}}{\to}\mathbfcal{Y}\to\widehat{\mathbfcal{Y}}\overset{g_{s}}{\to}\widehat{X}$,
where $X$ is the input image, $g_{a}$ is a learnable analysis transform,
$\mathbfcal{Y}$ is the latent-space representation of the input image, which
is quantized to $\widehat{\mathbfcal{Y}}$, $g_{s}$ is a learnable synthesis
transform, and $\widehat{X}$ is the approximation to the input image. Upon
deployment, and during our evaluation, the quantized latent representation
$\widehat{\mathbfcal{Y}}$ is entropy-coded and decoded. Such codecs are
trained end-to-end using a Lagrangian loss function:

$\mathcal{L}=R+\lambda\cdot D,$ (1)

where $R$ is the total rate estimate for $\widehat{\mathbfcal{Y}}$ and any
side information needed for its encoding and decoding, and $D$ is the
distortion between $X$ and $\widehat{X}$. The scalar $\lambda$ can be adjusted
to achieve the desired balance between compression efficiency and
reconstructed image quality.

Recently, the concept of latent-space scalability [13, 3] was proposed for
scalable human-machine coding. Here, the latent representation is partitioned
into base and enhancement portions,
$\mathbfcal{Y}=\\{\mathbfcal{Y}_{base},\mathbfcal{Y}_{enh}\\}$, such that
$\mathbfcal{Y}_{base}$ feeds the machine analysis task $T$, while both
$\mathbfcal{Y}_{base}$ and $\mathbfcal{Y}_{enh}$ are used for input
reconstruction, as shown in Fig. 1. Such a system can be trained end-to-end
using a generic loss function:

$\mathcal{L}=R_{base}+R_{enh}+\lambda_{base}\cdot D_{base}+\lambda_{enh}\cdot
D_{enh},$ (2)

where $R_{i}$ are the rate estimates for layer $i\in\\{base,enh\\}$, including
any side information, and $D_{i}$ are distortions related to the specific
layer. In [3], two systems were demonstrated based on this concept: a 2-layer
system whose base layer supports object detection using YOLOv3 [14], and a
3-layer system whose base layer supports object detection using Faster R-CNN
[15], together with the second base (or first enhancement) layer that supports
instance segmentation using Mask R-CNN [16]. In each case, state-of-the-art
rate-accuracy results were demonstrated on the machine task, while remaining
comparable to the state-of-the-art image codecs for human viewing as the
enhancement task. However, despite its good performance, the base layer of [3]
turns out to be inefficient. In the next section, we explain the source of
this inefficiency and present a way to improve it.

##  3 Proposed methods

The idea behind using the loss function (2) to optimize the codec in [3] was
that the base task-relevant information will be steered towards
$\mathbfcal{Y}_{base}$ because distortion $D_{base}$ depends only on
$\mathbfcal{Y}_{base}$ and not $\mathbfcal{Y}_{enh}$. While this is true, it
is only part of the story. To appreciate what happens during training,
consider the following simplified111This is a simplified scenario because, in
reality, features are being created and placed into $\mathbfcal{Y}_{base}$ or
$\mathbfcal{Y}_{enh}$ simultaneously, whereas here, for simplicity, we assume
that features are created first, then their placement is decided. scenario:
imagine that a feature $f$ has already been created and the goal of training
is to decide whether to place it in $\mathbfcal{Y}_{base}$ or
$\mathbfcal{Y}_{enh}$ based on the loss function (2). Consider two extreme
cases:

Case 1: feature $f$ carries base task-relevant information; note that such a
feature also carries information relevant to the enhancement task of input
reconstruction. If such a feature is placed into $\mathbfcal{Y}_{base}$, then
$R_{base}$ will increase and both $D_{base}$ and $D_{enh}$ will decrease, as
the feature will be used for both tasks. On the other hand, if such a feature
is placed into $\mathbfcal{Y}_{enh}$, then $R_{enh}$ will increase, but only
$D_{enh}$ will decrease, because the feature will not be used for the base
task. Hence, base task-relevant features are encouraged to end up in
$\mathbfcal{Y}_{base}$.

Case 2: feature $f$ carries no base task-relevant information, only
enhancement-relevant information. If such a feature is placed into
$\mathbfcal{Y}_{base}$, then $R_{base}$ will increase and $D_{enh}$ will
decrease, because both $\mathbfcal{Y}_{base}$ and $\mathbfcal{Y}_{enh}$ are
used for the enhancement task. Similarly, if such a feature is placed into
$\mathbfcal{Y}_{enh}$, then $R_{enh}$ will increase and $D_{enh}$ will
decrease, because both $\mathbfcal{Y}_{base}$ and $\mathbfcal{Y}_{enh}$ are
used for the enhancement task. Therefore, based on (2), there is no preference
for placing $f$ in either $\mathbfcal{Y}_{base}$ or $\mathbfcal{Y}_{enh}$, and
such a feature may end up anywhere in the latent space.

Based on the analysis above, we conclude that features that are not relevant
to the base task (case 2) may still end up in $\mathbfcal{Y}_{base}$. In other
words, the base layer of the codecs presented in [3] is likely inefficient,
containing more information than strictly necessary for the base task. In the
next section, we describe how base layer efficiency can be improved.

###  3.1 Base layer

As our framework is based on [3], we consider three machine analysis tasks as
our base layer tasks: object detection using YOLOv3, object detection using
Faster R-CNN, and instance segmentation using Mask R-CNN. Our results
demonstrate that we can improve the rate-accuracy efficiency on these tasks by
20-40% in BD-Rate.

As noted in the previous section, the source of inefficiency in the base layer
is the task-irrelevant information, which can end up in $\mathbfcal{Y}_{base}$
when base and enhancement layers are trained in parallel, as in [3]. For this
reason, we employ sequential training, where the base layer is trained first,
then frozen, followed by training of the enhancement layer. Conceptually, the
base layer processing chain can be described as
$X\overset{g_{b}}{\to}\mathbfcal{Y}_{base}\to\widehat{\mathbfcal{Y}}_{base}\overset{g_{t}}{\to}T$,
where $g_{b}$ is the base analysis transform, and $g_{t}$ accomplishes the
task $T$ from $\widehat{\mathbfcal{Y}}_{base}$. The key to making an efficient
base layer is to realize an Information Bottleneck (IB) [17] for task $T$:

$\min_{p(\widehat{y}_{base}|x)}\quad
I(X;\widehat{\mathbfcal{Y}}_{base})-\beta\cdot
I(\widehat{\mathbfcal{Y}}_{base};T),$ (3)

where $I(\cdot;\cdot)$ is the mutual information [18],
$p(\widehat{y}_{base}|x)$ is the mapping from the input image to the base-
layer latent representation, and $\beta>0$ is the IB Lagrange multiplier [17].

In our case, $p(\widehat{y}_{base}|x)$ is $g_{b}$ followed by quantization.
Hence, when input $X$ is given, $\widehat{\mathbfcal{Y}}_{base}$ is fully
determined, so we have
$I(X;\widehat{\mathbfcal{Y}}_{base})=H(\widehat{\mathbfcal{Y}}_{base})-H(\widehat{\mathbfcal{Y}}_{base}|X)=H(\widehat{\mathbfcal{Y}}_{base})$,
because $H(\widehat{\mathbfcal{Y}}_{base}|X)=0$. Here, $H(\cdot)$ and
$H(\cdot|\cdot)$ are the entropy and conditional entropy [18], respectively.
Moreover, since decreasing $-\beta\cdot I(\widehat{\mathbfcal{Y}}_{base};T)$
(i.e., increasing $I(\widehat{\mathbfcal{Y}}_{base};T)$) is supposed to
improve the task accuracy, we take $\lambda_{base}\cdot D_{base}$ as the proxy
for $-\beta\cdot I(\widehat{\mathbfcal{Y}}_{base};T)$. Therefore, in our case,
the IB (3) for task $T$ becomes:

$\min_{g_{b},g_{t}}\quad H(\widehat{\mathbfcal{Y}}_{base})+\lambda_{base}\cdot
D_{base},$ (4)

showing that it can be solved using a loss function analogous to (1). We
employ [10] to realize $g_{b}$ and perform entropy estimation, and the Latent
Space Transform (LST) from [3] to map $\widehat{\mathbfcal{Y}}_{base}$ to the
task network features, where we use MSE as our distortion target during
training. The number of channels in $\widehat{\mathbfcal{Y}}_{base}$ is set
depending on the task, as described in the experiments.

###  3.2 Enhancement layer

After training the base layer, we freeze it, and construct a “preview
transform” that is meant to recover an approximation $\widehat{X}_{pre}$ of
the input image $X$ from base features $\widehat{\mathbfcal{Y}}_{base}$, as
shown in Fig. 2. This transform consists of a $1\times 1$ convolutional layer
to adjust the number of channels, followed by a synthesis transform $g_{s}$
from [10] to approximate the input image $X$. Next, we subtract the preview
image $\widehat{X}_{pre}$ from the input $X$, resulting in a residual image
$X_{res}$. This residual image is then encoded by [10], which was fine-tuned
for our setting using an MSE loss. Finally, we obtain the reconstructed input
$\widehat{X}$ by adding $\widehat{X}_{pre}$ to the reconstructed residual
$\widehat{X}_{res}$. The dashed line in Fig. 2 indicates that during training
of the enhancement layer, the base layer is frozen.

##  4 Experiments

###  4.1 Base layer

As explained above, we begin by training and evaluating the base layer without
the enhancement part. We do this using several tasks and models following [3]:
object detection using YOLOv3 [14] and Faster R-CNN [15], and instance
segmentation using Mask R-CNN [16]. All base-layer experiments share the
following two-stage training approach. Input images are random patches of size
$256\times 256$ from the JPEG-AI [19] and CLIC [20] datasets in stage one and
VIMEO-90K [21] in stage two, with a mini-batch size of 16. The first stage
uses the Adam optimizer with a fixed learning rate of $10^{-4}$ for 500
epochs, followed by another 400 epochs with a polynomial decay of the learning
rate every 10 epochs. The Lagrange multipliers as well as the number of base
channels $L_{base}$ for each task are shown in Table 1.

Fig. 2: Sequentially-optimized two-task scalable codec: the base layer is optimized first, and then frozen while the enhancement layer is optimized. Table 1: Task model parameters Task model | $\lambda_{base}$ | $L_{base}$
---|---|---
Faster R-CNN | 1.28e–5 | 3.2e–5 | 8e–5 | 2e–4 | 4e–4 | 5.5e–4 | 96
Mask R-CNN | 1.28e–5 | 3.2e–5 | 8e-5 | 2e–4 | 4e–4 | 5.5e–4 | 128
YOLOv3 | - | 5e–5 | 1e–4 | 4e–4 | 1e–3 | 2e–3 | 64

Task performance is then evaluated following the same procedure as in the
3-layer network described in [3], using the COCO2017/COCO2014 validation set
[22], and Detectron2 [23]. We maintain the same formulation for the mean
average precision (mAP) as in [3] and compare the performance of our proposed
base layer with [3] (which we refer to as Choi2022) alongside other benchmarks
in Fig. 3-5.

Fig. 3: Evaluation of base layer for object detection task using Faster R-CNN
backbone on COCO2017 validation set Fig. 4: Evaluation of base layer for
object detection task using YOLOv3 backbone on COCO2014 validation set Fig. 5:
Evaluation of base layer for instance segmentation using Mask R-CNN backbone
on COCO2017 validation set

Observing the three figures, it is evident that our base layer outperforms the
previous SOTA by a significant margin. For example, Fig. 3, shows that using
Faster R-CNN, [3] experiences a $1.3\%$ drop in mAP at $0.1$ bits per pixel
(BPP), while our base layer only drops by $0.56\%$. Similarly, when using
YOLOv3 in Fig. 4, [3] suffers a degradation of $1.15\%$ even at a relatively
high bit-rate of over $0.7$ BPP, while our approach remains at less than $1\%$
reduction in mAP until approximately $0.5$ BPP. Lastly, we see that such
improvement persist even in the more complex task of instance segmentation,
seen in Fig. 5.

To summarize the difference in performance between our proposed method and
previous SOTA, we employ the Bjøntegaard Delta (BD) metric [24] for rate
difference at equivalent accuracy (BD-Rate). We see significant savings in all
three experiments, which are summarized in Table 2.

Table 2: BD-Rate of the proposed base layer relative to the base layer of [3] Task model | Faster R-CNN | Mask R-CNN | YOLOv3
---|---|---|---
BD-Rate (%) | –36.5 | –18.9 | –41.7

###  4.2 Enhancement layer

Once the base-layer training is complete, we proceed to train the enhancement
layer. Because of the decoupling between the training of our base and
enhancement layers, we can theoretically match various levels of image
reconstruction to each of our base-layer models. However, in order to create a
fair comparison with previous models, where base and enhancement performance
are inherently linked, we match the relative qualities of our two layers. In
training the enhancement layer, we freeze our base layer and initialize the
residual using a pre-trained model [10] (Cheng2020 in figures) of varying
quality index, provided by CompressAI [25]. For the first three base
qualities, we choose quality index 1, while for higher base qualities, we
assign quality 3 from [10]. ̵It is worth noting that both quality levels
contain 128 channels.

The enhancement layer is trained for 300 epochs using random patches of
$256\times 256$ from the JPEG-AI [19] and CLIC [20] datasets, with a mini-
batch size of 16, the Adam optimization algorithm with a constant learning
rate of $10^{-4}$ is used. The values of the $\lambda_{enh}$ are similar to
the $\lambda_{enh}$ used in [3]. The performance of the enhancement layer is
evaluated on Kodak [26] dataset, which consists of 24 uncompressed images. The
results of the input reconstruction are shown in terms of PSNR vs. BPP in Fig.
6. Table 3 summarizes the BD-Rate results using Cheng2020 as the benchmark,
including Choi2022 and our proposed approach.

Table 3: BD-Rate relative to [10] Network | Setting | BPP | BD-Rate (%)
---|---|---|---
Choi2022 | 2-layer | Total | 4.40
3-layer | Total | 24.11
Proposed | Faster R-CNN | Total | 71.46
Enh. only | –7.41
Mask R-CNN | Total | 92.86
Enh. only | –10.92
YOLOv3 | Total | 28.90
Enh. only | –16.95
Fig. 6: Comparison of input reconstruction performance using proposed base
layers on Kodak dataset

As could perhaps have been expected, the improvement of our base layer came at
the cost of some degradation to the enhancement-layer performance. We do see
significant increase in bitrate when compared with Cheng2020, as well as the
scalable approach of Choi2022 [3]. Fortunately, however, when comparing our
enhancement layer alone, we still see rate savings compared to re-transmitting
the full image, with BD-Rate improvement (compared to [10]) ranging from
$7-17\%$. In a practical setting, the choice between two approaches will
depend on the relative frequency of the use of human vision compared to
machine vision, denoted $f_{T}$. Using this, the relative rate of our approach
and a human-vision encoder is given by:

$(1-f_{T})\cdot\frac{R_{base}}{R}+f_{T}\cdot\frac{R_{base}+R_{enh}}{R},$ (5)

where $R$ is the bitrate of the single-layer encoder. Whenever the relative
rate is smaller than 1, our approach will be preferable. Using BD-Rate
estimates to approximate the ratios in Eq. 5, we see, that our models achieves
overall rate savings so long as human viewing is used less than $59\%$,
$34\%$, and $17\%$, for YOLOv3, Faster R-CNN, and Mask R-CNN, respectively.

##  5 Conclusions

We have explained and demonstrated an inefficiency in the base layer in the
previous state-of-the-art human-machine scalable image codec. To mitigate this
problem, we proposed an improved base-layer training procedure achieving
significant rate savings on multiple tasks. We then added a residual-based
enhancement layer for input reconstruction. As expected, we saw some
degradation in rate-distortion for the enhancement layer, which we believe can
be reduced through further optimization of the enhancement layer.
Nevertheless, in scenarios where machine analysis is needed more frequently
than human viewing, our proposed method outperforms relevant single-layer
learned image codecs.

## References

  * [1] H. Choi and I. V. Bajć,  “High efficiency compression for object detection,”  in Proc. IEEE ICASSP, Apr. 2018, pp. 1792–1796.
  * [2] H. Choi and I. V. Bajić,  “Deep feature compression for collaborative object detection,”  in Proc. IEEE ICIP, Oct. 2018, pp. 3743–3747.
  * [3] H. Choi and I. V. Bajić,  “Scalable image coding for humans and machines,”  IEEE Trans. Image Processing, vol. 31, pp. 2739–2754, 2022.
  * [4] S. Yang, Y. Hu, W. Yang, L.-Y. Duan, and J. Liu,  “Towards coding for human and machine vision: Scalable face image coding,”  IEEE Trans. Multimedia, vol. 23, pp. 2957–2971, 2021.
  * [5] N. Yan, C. Gao, D. Liu, H. Li, L. Li, and F. Wu,  “SSSIC: semantics-to-signal scalable image coding with learned structural representations,”  IEEE Trans. Image Processing, vol. 30, pp. 8939–8954, 2021.
  * [6] S. Jeong, S. Jeong, S. S. Woo, and J. H. Ko,  “An overhead-free region-based jpeg framework for task-driven image compression,”  Pattern Recogn. Lett., vol. 165, no. C, pp. 1–8, Jan. 2023.
  * [7] G. Toderici, S. M. O’Malley, S. J. Hwang, D. Vincent, D. Minnen, S. Baluja, M. Covell, and R. Sukthankar,  “Variable rate image compression with recurrent neural networks,”  in ICLR, 2016.
  * [8] D. Minnen, J. Ballé, and G. D. Toderici,  “Joint autoregressive and hierarchical priors for learned image compression,”  Advances in Neural Information Processing Systems, vol. 31, pp. 10771–10780, 2018.
  * [9] J. Ballé, D. Minnen, S. Singh, S. J. Hwang, and N. Johnston,  “Variational image compression with a scale hyperprior,”  in International Conference on Learning Representations, 2018.
  * [10] Z. Cheng, H. Sun, M. Takeuchi, and J. Katto,  “Learned image compression with discretized gaussian mixture likelihoods and attention modules,”  in Proc. IEEE/CVF CVPR, Jun. Jun. 2020, pp. 7939–7948.
  * [11] Y. Hu, W. Yang, and J. Liu,  “Coarse-to-fine hyper-prior modeling for learned image compression,”  in Proc. AAAI Conf. Artif. Intell., 2020, vol. 34, pp. 11013–11020.
  * [12] Y. Xie, K. L. Cheng, and Q. Chen,  “Enhanced invertible encoding for learned image compression,”  in Proc. 29th ACM Int. Conf. Multimedia, Oct. 2021, pp. 162–170.
  * [13] H. Choi and I. V. Bajić,  “Latent-space scalability for multi-task collaborative intelligence,”  in Proc. IEEE ICIP, Sep. 2021, pp. 3562–3566.
  * [14] J. Redmon and A. Farhadi,  “YOLOv3: An incremental improvement,”  arXiv preprint arXiv:1804.02767, 2018.
  * [15] S. Ren, K. He, R. Girshick, and J. Sun,  “Faster R-CNN: towards real-time object detection with region proposal networks,”  IEEE Trans. Pattern Anal. Mach. Intell., vol. 39, no. 6, pp. 1137–1149, Jun. 2017.
  * [16] K. He, G. Gkioxari, P. Dollár, and R. Girshick,  “Mask R-CNN,”  in Proc. IEEE ICCV, Oct. 2017, pp. 2961–2969.
  * [17] N. Tishby, F. C. Pereira, and W. Bialek,  “The information bottleneck method,”  in Proc. 37th annual Allerton Conference on Communication, Control, and Computing, Sep. 1999, pp. 368–377.
  * [18] T. M. Cover and J. A. Thomas,  Elements of Information Theory,  Wiley, 2nd edition, 2006.
  * [19] “JPEG AI dataset,” https://jpeg.org/jpegai/dataset.html,  [Online].
  * [20] “Challenge on learned image compression (CLIC),” http://www.compression.cc/,  [Online].
  * [21] T. Xue, B. Chen, J. Wu, D. Tao, and W. T. Freeman,  “Video enhancement with task-oriented flow,”  Int. J. Comput. Vis., vol. 127, no. 8, pp. 1106–1125, 2019.
  * [22] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick,  “Microsoft COCO: Common objects in context,”  in Computer Vision – ECCV 2014, Cham, 2014, pp. 740–755, Springer International Publishing.
  * [23] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick,  “Detectron2,” https://github.com/facebookresearch/detectron2, 2019\.
  * [24] G. Bjøntegaard,  “Calculation of average PSNR differences between RD-curves,” https://www.itu.int/wftp3/av-arch/video-site/0104_Aus/VCEG-M33.doc, Apr. 2001,  VCEG-M33.
  * [25] J. Bégaint, F. Racapé, S. Feltman, and A. Pushparaja,  “CompressAI: a PyTorch library and evaluation platform for end-to-end compression research,”  2020\.
  * [26] Kodak,  “Kodak lossless true color image suite (photocd pcd0992),” http://r0k.us/graphics/kodak.


# No graph states can be prepared in quantum networks with bipartite sources

Owidiusz Makuta  Center for Theoretical Physics, Polish Academy of Sciences,
Aleja Lotników 32/46, 02-668 Warsaw, Poland  Laurens T. Ligthart  Institute
for Theoretical Physics, University of Cologne, Zülpicher Straße 77, D-50937
Cologne, Germany  Remigiusz Augusiak  Center for Theoretical Physics, Polish
Academy of Sciences, Aleja Lotników 32/46, 02-668 Warsaw, Poland

###### Abstract

In research concerning quantum networks, it is often assumed that the parties
can classically communicate with each other. However, classical communication
might introduce substantial delay to the network, especially if it is large.
As the latency of a network is one of its most important characteristics, it
is interesting to consider quantum networks in which parties cannot
communicate classically and ask what limitations this assumption imposes on
the possibility of preparing multipartite states in such networks. We show
that graph states of arbitrary prime local dimension known for their numerous
applications in quantum information cannot be generated in a quantum network
in which parties are connected via sources of bipartite quantum states and the
classical communication is replaced by some pre-shared classical correlations.
We then generalise our result to arbitrary quantum states that are
sufficiently close to graph states.

##  I Introduction

Out of all proposed real-life implementations of quantum information, quantum
networks stand as one of the most promising ones. We already have many ideas
for possible applications of quantum networks such as quantum key distribution
Lo  _et al._ (2014); Liao  _et al._ (2017); Tang  _et al._ (2014), clock
synchronisation Kómár  _et al._ (2014), parallel computing Parekh  _et al._
(2021) or even quantum internet Kimble (2008); Wehner  _et al._ (2018). What
is more, their relative simplicity as compared with other quantum
technologies, makes them perhaps the closest ones to commercial
implementation. This sentiment is also supported by the significant progress
in experimental implementation of quantum networks that has recently been made
Wang  _et al._ (2010); Sasaki  _et al._ (2011); Fröhlich  _et al._ (2013);
Liao  _et al._ (2018); Yin  _et al._ (2020).

At their core, quantum networks are simply collections of parties and of
sources of multipartite quantum (possibly entangled) states. Every party in a
network can perform certain operations on their share of the distributed
quantum states. These, however, strongly depend on the considered model of a
quantum network. The most natural model of quantum networks (referred here to
as LOCC networks) allows the parties to act with the most general local
operations on their shares of the distributed states and to coordinate their
actions by using classical communication. However, while connected LOCC
networks enable preparing any multipartite state, the use of classical
communication might be problematic for their commercial implementations. For
instance, classical communication, especially in large networks, might
increase their latency and thus make the parties use long-lived quantum
memories.

It is thus reasonable to consider quantum networks in which the amount of
classical communication between the parties is limited or even no
communication is allowed. A possible model of quantum networks that fulfils
this requirement is one in which the parties can apply arbitrary quantum
channels to their share of states, however, contrary to LOCC, they cannot use
classical communication. Instead, they are allowed to orchestrate their
actions with the aid of some pre-shared classical information. We call such
networks LOSR (local operations and shared randomness) quantum networks. While
the above no-communication assumption severely reduces the capability of
generating multipartite states in LOSR quantum networks as compared to the
LOCC ones, they are still more general than those in which the parties have no
access to shared classical correlations and can only implement unitary
operations. While the LOSR networks have become an object of intensive studies
Mao  _et al._ (2022); Navascués  _et al._ (2020); Coiteux-Roy  _et al._
(2021); Hansenne  _et al._ (2022); Luo (2021), it remains unclear what
multipartite entangled states can actually be prepared in them.

In quantum information graph states stand as one of the most representative
classes of multipartite states, including the Greenberger-Horne-Zeilinger
Greenberger  _et al._ (1989), cluster Briegel and Raussendorf (2001) or the
absolutely maximally entangled Helwig (2013) states. Moreover, they are key
resources for many applications, just to mention quantum computing Raussendorf
and Briegel (2001); Briegel  _et al._ (2009); Yao  _et al._ (2012),
multipartite secret sharing Hillery  _et al._ (1999), or quantum metrology
Tóth and Apellaniz (2014). It has been thus a question of utmost importance
whether they can be prepared in quantum networks.

Here we answer the above question to the negative and show that no graph
states of arbitrary prime local dimension (or any state sufficiently close to
them) can be prepared in LOSR networks with bipartite sources. We thus
generalise the recent results that the three-partite GHZ states Navascués  _et
al._ (2020); Kraft  _et al._ (2021) or any $N$-qubit graph states with $N$ up
to $12$ cannot be prepared in LOSR networks with bipartite sources Hansenne
_et al._ (2022). Our work is at the same time complementary to Ref. Luo (2021)
which shows that no qubit or qutrit graph states of arbitrary number of
parties can be prepared in such networks even with $(N-1)$-partite sources.
Our proof employs the quantum inflation method Wolfe  _et al._ (2019, 2021)
which is perfectly suited to decide whether multipartite states can be
prepared in LOSR networks Navascués  _et al._ (2020); Wolfe  _et al._ (2021).

##  II Preliminaries

(1) Graph states. Consider a multigraph $G$ which is a graph in which any two
vertices can be connected by more than one edge, but no edge can connect a
vertex to itself. Let $\Gamma_{i,j}$ denote the number of edges connecting
vertices $i$ and $j$, and let $\mathcal{N}_{i}$ be the neighbourhood of vertex
$i$, i.e., the set of vertices that are connected to $i$ by at least one edge.
See Fig. 1 for an example of a multigraph. To associate a quantum state to
such an $N$-vertex graph $G$, we consider a Hilbert space
$\mathcal{H}=\mathcal{H}_{1}\otimes\dots\otimes\mathcal{H}_{N}=\mathbb{C}_{d}^{\otimes
N}$, where each local qudit space $\mathbb{C}_{d}$ corresponds to one of the
vertices of $G$; we assume that $d$ is prime and fulfils
$d\geqslant\max_{i,j}\Gamma_{i,j}$. To each vertex $i$ we associate the
following operator

$g_{i}=X_{i}\prod_{j\in\mathcal{N}_{i}}\left(Z_{j}\right)^{\Gamma_{i,j}},$ (1)

where $X$ and $Z$ are generalised Pauli matrices given by

$X=\sum_{i=0}^{d-1}\ket{i+1}\\!\\!\bra{i},\qquad
Z=\sum_{i=0}^{d-1}\omega^{i}\ket{i}\\!\\!\bra{i},$ (2)

with $\omega=\exp(2\pi i/d)$ and $\ket{d}=\ket{0}$. The subscripts in Eq. (1)
specify the subsystems which these operators act on. One then defines the
graph state $\ket{G}$ associated to $G$ to be the unique state from
$\mathcal{H}$ that fulfils $g_{i}\ket{G}=\ket{G}$ for all
$i\in\\{1,\dots,N\\}$ (for a more in-depth look at graph states, see e.g. Ref.
Hein  _et al._ (2006)).

Figure 1: An example of a multigraph with three vertices.

(2) Quantum networks. Let us consider a scenario in which $N$ parties,
labelled $1,\dots,N$, receive quantum states distributed by independent
sources. Each party $i$ can perform an arbitrary local operation
$\mathcal{E}_{i}$ on their shares of the distributed states. We also assume
that parties cannot communicate with each other, yet they all have access to
some shared randomness, which is a random variable $\lambda$ with a
distribution $p_{\lambda}$. This $\lambda$ is a representation of classical
correlations between the parties, and it can be interpreted as, for instance,
a measurement strategy that was agreed upon before the experiment. This set of
assumptions describes a scenario called Local Operations and Shared Randomness
(LOSR).

There is one more assumption, independent of LOSR, that we make, namely, that
the sources distributing quantum states are bipartite, i.e., a single source
distributes a quantum state to at most two parties. If two parties share a
state we say that they are connected.

The most general state that can be produced in a quantum network that
satisfies the above assumptions is given by Hansenne  _et al._ (2022)

$\rho=\sum_{\lambda}p_{\lambda}\mathcal{E}_{1}^{\lambda}\otimes\dots\otimes\mathcal{E}_{N}^{\lambda}\left[\sigma_{1,2}\otimes\sigma_{1,3}\otimes\dots\otimes\sigma_{N-1,N}\right],$
(3)

where $\sigma_{i,j}$ denotes a state distributed between parties $i$ and $j$,
$\sum_{\lambda}p_{\lambda}=1$, and the subscript $\lambda$ denotes the
dependence of local operations on the shared random variable.

Here, three remarks are in order. First, the local operation
$\mathcal{E}_{i}^{\lambda}$ acts on $i$’s part of all $\sigma_{i,j}$, meaning
that tensor products of $\mathcal{E}_{i}^{\lambda}$ and of $\sigma_{i,j}$ are
taken with respect to different sets of subsystems; while the former is taken
with respect to different parties, the latter separates states from different
sources.

Second, we should expect the distributed states $\sigma_{i,j}$ to depend on
$\lambda$ because the sources can be classically correlated as well. However,
since we do not impose any restriction on the dimension of $\sigma_{i,j}$, one
can get rid of this dependency by considering a Hilbert space of sufficiently
high dimension Navascués  _et al._ (2020).

Third, in this work we will assume that every network we consider (not
including inflations) is fully-connected, i.e., each party shares a bipartite
state with every other party. We can make this assumption without loss of
generality because the behaviour of each quantum network can always be
simulated by the fully connected one: taking $\sigma_{i,j}$ to be the
maximally mixed state produces the same outcomes as removing the connection
between the nodes $i$ and $j$. In other words, if $\rho$ cannot be generated
in an $N$-partite LOSR network with bipartite sources that is fully connected,
then it cannot be generated in any such network which is not fully connected.

(3) Network inflation. One of the standard techniques in disproving a
statement is to relax the initial assumptions in hopes of streamlining the
proof. In the context of quantum networks this is achieved by using the
quantum inflation method Wolfe  _et al._ (2019, 2021). Given some network
$\mathcal{O}$, the inflation $\mathcal{I}$ of $\mathcal{O}$ is a network that
consists of multiple copies of parties and sources from the original network.
Whether two parties are connected in $\mathcal{I}$ is up to us, the only
restriction is that they are connected via a copy of a source from
$\mathcal{O}$.

This construction is very general as many different inflations can be
considered for a given network $\mathcal{O}$. However, here we focus on a
certain class of inflations that are tailored to the needs of our proof.
Consider an $N$-partite network $\mathcal{O}$ that we want to analyse; as
already explained, we assume it to be fully connected. In our approach, every
inflation $\mathcal{I}$ of $\mathcal{O}$ consists of two copies of the parties
from $\mathcal{O}$ labelled $1,\dots,N$ and $1^{\prime},\dots,N^{\prime}$. We
assume that both parties $i$ and $i^{\prime}$ apply the same local operation
as the original one, that is,
$\mathcal{E}^{\mathcal{I}}_{i}=\mathcal{E}^{\mathcal{I}}_{i^{\prime}}=\mathcal{E}^{\mathcal{O}}_{i}$,
where the superscripts indicate the network. We also assume that each party
$i$ in $\mathcal{I}$ is connected to either $j$ or $j^{\prime}$ but never to
both. Furthermore, if two copies of parties share a state, this state is a
copy of a state shared between original parties in $\mathcal{O}$. These last
two assumptions together, imply that for every pair of parties
$i,j\in\mathcal{O}$ and for any inflation $\mathcal{I}$, exactly one of the
two following statements always holds true:

$\sigma_{i,j}^{\mathcal{I}}=\sigma_{i^{\prime},j^{\prime}}^{\mathcal{I}}=\sigma_{i,j}^{\mathcal{O}},\quad\textrm{or}\quad\sigma_{i,j^{\prime}}^{\mathcal{I}}=\sigma_{i^{\prime},j}^{\mathcal{I}}=\sigma_{i,j}^{\mathcal{O}}.$
(4)

We finally assume that in $\mathcal{I}$ the shared randomness is distributed
between all copies of parties, meaning that the state generated in
$\mathcal{I}$ is described by Eq. (3).

The above assumptions allow us to establish very useful relations between
expected values $\langle\cdot\rangle_{\mathcal{I}_{1}}$ and
$\langle\cdot\rangle_{\mathcal{I}_{2}}$ calculated over states from two
different inflations $\mathcal{I}_{1}$, $\mathcal{I}_{2}$

######  Fact 1.

Consider a network $\mathcal{O}$ and two different inflations of it, denoted
$\mathcal{I}_{1}$ and $\mathcal{I}_{2}$. Consider also two matrices
$B=\bigotimes_{i\in\mathcal{I}_{1}}B_{i}$ and
$C=\bigotimes_{i\in\mathcal{I}_{2}}C_{i}$ that act nontrivially on some
subnetworks $\mathcal{I}_{i}^{\prime}\subseteq\mathcal{I}_{i}$. Then, $\langle
B\rangle_{\mathcal{I}_{1}}=\langle C\rangle_{\mathcal{I}_{2}}$ if

  1. 1.

The subnetworks $\mathcal{I}^{\prime}_{1}$ and $\mathcal{I}^{\prime}_{2}$ are
isomorphic.

  2. 2.

For every party $i$ we have that either $B_{i}=C_{i}$ and
$B_{i^{\prime}}=C_{i^{\prime}}$, or $B_{i^{\prime}}=C_{i}$ and
$B_{i}=C_{i^{\prime}}$.

Let us add here that we say that two networks are isomorphic if one can be
transformed into the other one by making the non-primed parties primed and
vice versa. The above fact can be easily proven by using Eq. (3) and tracing
out the parties where $B$ and $C$ act trivially. Notice that since the
original network $\mathcal{O}$ can be thought of as a trivial inflation of
itself, Fact 1 enables also establishing relations between
$\langle\cdot\rangle_{\mathcal{O}}$ and $\langle\cdot\rangle_{\mathcal{I}}$
for some inflation $\mathcal{I}$.

Figure 2: A fully connected tripartite quantum network $\mathcal{O}^{\Delta}$
with its two inflations $\mathcal{I}_{0}^{\Delta}$ and
$\mathcal{I}_{1}^{\Delta}$. The "edges" represent bipartite states shared by
the parties.

##  III Main results

Let us now move on to the main results of our work that no graph state can be
generated in quantum networks with bipartite sources. We begin by presenting
the key ingredients of our approach, which at its core is highly inspired by
the recent work Hansenne  _et al._ (2022). The proof hinges on reaching a
contradiction with the following inequality (see Appendix A for a proof and
Appendix B for an alternative approach).

######  Lemma 1.

Consider two unitary matrices $A_{1},A_{2}$ acting on some Hilbert space
$\mathbbm{C}^{D}$ with $D$ being a multiple of some prime number $d\geq 2$.
Assume moreover that $A_{i}$ are such that $A_{1}^{d}=A_{2}^{d}=\mathbb{1}$
and $A_{1}A_{2}=\omega^{q}A_{2}A_{1}$ for some $q\in\\{1,\dots,d-1\\}$. Then,
the following inequality holds true

$\sum_{k=0}^{d-1}\langle A_{1}^{k}+A_{2}^{k}\rangle\leqslant d+\sqrt{d}.$ (5)

In order to show violation of Eq. (5) we have to find a relation between
expected values calculated on states from the original network and its
inflations. This can be done using Fact 1, however, it might not always be
possible to directly find an equivalence
$\langle\cdot\rangle_{\mathcal{I}}=\langle\cdot\rangle_{\mathcal{O}}$ for some
product observable. Luckily, we can alleviate this problem, by conditioning
one expected value over some inflation on some other expected values over the
same inflation.

######  Fact 2.

Consider three mutually commuting unitary matrices $B_{i}$ that obey
$B_{i}^{d}=\mathbb{1}$. If $\langle B_{1}B_{3}\rangle=\langle
B_{2}B_{3}^{\dagger}\rangle=1$, then $\langle B_{1}B_{2}\rangle=1$.

This fact follows from a simple observation that if $\langle
B_{1}B_{3}\rangle=\langle B_{2}B_{3}^{\dagger}\rangle=1$ for some
$\ket{\psi}$, then the fact that $B_{1}B_{3}$ and $B_{2}B_{3}^{\dagger}$ are
unitary implies that they both stabilize $\ket{\psi}$, that is,
$B_{1}B_{3}\ket{\psi}=\ket{\psi}$ and
$B_{2}B_{3}^{\dagger}\ket{\psi}=\ket{\psi}$. Taking into account that $B_{i}$
mutually commute, one concludes that $B_{1}B_{2}\ket{\psi}=\ket{\psi}$ from
which the above implication follows.

Facts 1 and 2 together with Lemma 1 are the key elements of our approach.
However, before showing in a full generality how they are combined into a
proof, let us first present an illustrative example. Consider the tripartite,
fully connected network $\mathcal{O}^{\Delta}$ presented in Fig. 2 and the
graph state $\ket{G_{\Delta}}$ corresponding to the triangle graph, i.e., one
that satisfies $g_{i}\ket{G_{\Delta}}=\ket{G_{\Delta}}$ for $d=3$,
$i\in\\{1,2,3\\}$, where

$g_{1}=X_{1}Z_{2}^{2}Z_{3},\qquad g_{2}=Z_{1}^{2}X_{2},\qquad
g_{3}=Z_{1}X_{3}.$ (6)

To show that $\ket{G_{\Delta}}$ cannot be generated in $\mathcal{O}^{\Delta}$
consider its inflation $\mathcal{I}_{0}^{\Delta}$ presented in Fig. 2. Since
the operators $g_{1}$ and $Z_{1}^{2}X_{2^{\prime}}$ obey the assumptions of
Lemma 1, the following inequality holds true for them:

$\sum_{k=0}^{2}\left(\left\langle
g_{1}^{k}\right\rangle_{\mathcal{I}_{0}^{\Delta}}+\left\langle(Z_{1}^{2}X_{2^{\prime}})^{k}\right\rangle_{\mathcal{I}_{0}^{\Delta}}\right)\leqslant
3+\sqrt{3},$ (7)

where $\langle\cdot\rangle_{\mathcal{I}_{0}^{\Delta}}$ denotes the expected
value calculated on a state generated in $\mathcal{I}_{0}^{\Delta}$. Our goal
is to show that this inequality is violated, assuming that $\ket{G_{\Delta}}$
can be generated in $\mathcal{O}^{\Delta}$.

Let us focus on the first expected value in (7). Given that $\ket{G_{\Delta}}$
can be prepared in $\mathcal{O}^{\Delta}$, it follows from Fact 1 that
$\langle g_{1}^{k}\rangle_{\mathcal{I}_{0}^{\Delta}}=\langle
g_{1}^{k}\rangle_{\mathcal{O}^{\Delta}}=1$. As for the second expected value
in Eq. (7), we can use Fact 1 to show that

$\left\langle
Z_{1}^{2}X_{2^{\prime}}\right\rangle_{\mathcal{I}_{0}^{\Delta}}=\left\langle
g_{2}\right\rangle_{\mathcal{I}_{1}^{\Delta}},$ (8)

where $\mathcal{I}_{1}^{\Delta}$ is another inflation of
$\mathcal{O}^{\Delta}$ presented in Fig. 2.

Let us now prove that $\langle g_{2}\rangle_{\mathcal{I}_{1}^{\Delta}}=1$.
Since the nodes $1$ and $2$ are disconnected in $\mathcal{I}_{1}^{\Delta}$ we
cannot directly obtain this expected value from the original network
$\mathcal{O}^{\Delta}$ and the state $\ket{G_{\Delta}}$; still we can compute
it indirectly by employing Fact 2. To this aim, we first notice that Fact 1
implies that $\langle g_{2}g_{3}\rangle_{\mathcal{I}_{1}^{\Delta}}=\langle
g_{2}g_{3}\rangle_{\mathcal{O}^{\Delta}}=1$ and $\langle
g_{3}\rangle_{\mathcal{I}_{1}^{\Delta}}=\langle
g_{3}\rangle_{\mathcal{O}^{\Delta}}=1$. Since the three generators $g_{i}$
mutually commute, Fact 2 implies that

$\langle g_{2}g_{3}\rangle_{\mathcal{I}_{1}^{\Delta}}=\langle
g_{3}\rangle_{\mathcal{I}_{1}^{\Delta}}=1\quad\Rightarrow\quad\left\langle
g_{2}\right\rangle_{\mathcal{I}_{1}^{\Delta}}=1,$ (9)

which is what we wanted to obtain.

Hence, Eq. (8) implies that $\left\langle
Z_{1}^{2}X_{2^{\prime}}\right\rangle_{\mathcal{I}_{0}^{\Delta}}=1.$ By the
same argument we have $\left\langle
Z_{1}X_{2^{\prime}}^{2}\right\rangle_{\mathcal{I}_{0}^{\Delta}}=1,$ which
implies that the left side of Eq. (7) equals six, leading to a contradiction
with the right-hand side of this inequality. Thus, the triangle graph state
cannot be generated in the network $\mathcal{O}^{\Delta}$.

We are now ready to present our main result that no graph states of arbitrary
local prime dimension can be produced in LOSR quantum networks with bipartite
sources, generalizing the results of Refs. Hansenne  _et al._ (2022); Luo
(2021) to the case of arbitrary graph states of prime local dimension $d$.

######  Theorem 1.

Consider a graph $G$ with $N\geqslant 3$ vertices and where at least one
vertex $i$ has a neighbourhood $|\mathcal{N}_{i}|\geqslant 2$. A graph state
$\ket{G}\in\mathbb{C}_{d}^{\otimes N}$, where $d$ is prime, corresponding to a
graph $G$ cannot be generated in an LOSR $N$-partite quantum network with
bipartite sources.

###### Proof.

The proof is highly technical, and so we present it in Appendix C. Here we
describe its most important ideas.

First, in every graph satisfying the assumptions of Theorem 1 we can relabel
vertices so that $|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geqslant 2$ and
$\Gamma_{1,2}\neq 0$. Next, we utilise a graph transformation called local
complementation (see Refs. Van den Nest  _et al._ (2004); Bahramgiri and Beigi
(2007)) to divide the set of all graph states into four, distinct subsets
(Lemma 4 in Appendix C). Since the proof for three of those classes is
relatively simple, here we discuss only the most complicated case of graphs
for which $\mathcal{N}_{1}\cap\mathcal{N}_{2}\neq\emptyset$ and for all
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ we have

$\mathcal{N}_{2}\setminus\\{n\\}\neq\mathcal{N}_{n}\setminus\\{2\\}.$ (10)

Let us consider a graph state $\ket{G}$ corresponding to a multigraph $G$ that
fulfils the above assumptions. To prove that this state cannot be generated in
an $N$-partite quantum network $\mathcal{O}$ we use the aforementioned network
inflation method.

Figure 3: Inflations $\mathcal{I}_{k}$. Here $T_{k}$, $T_{k}^{\prime}$,
$R_{k}$, $R_{k}^{\prime}$ are not individual parties, but rather sets of
parties. In each such set we assume that every party shares a state with every
other party from that set. Moreover, if two sets are connected, then we assume
that every party from one set shares a state with every other party from the
second set. In that context, parties $2$ and $2^{\prime}$ can be thought of as
one-element sets.

Let us briefly describe the inflations $\mathcal{I}_{k}$ of the original
network $\mathcal{O}$ that our proof is based on. They all have the same
structure (see Fig. 3). A non-primed party $i$ (for $i\neq 2$) is connected to
every other non-primed party $j$ (for $j\neq 2$) and to either $2$ or
$2^{\prime}$. By $R_{k}$ and $T_{k}$ we denote the sets of non-primed parties
connected to party $2$ and $2^{\prime}$, respectively. Likewise, we assume
that every primed party $i^{\prime}$ (for $i^{\prime}\neq 2^{\prime}$) is
connected to every other primed party $j^{\prime}$ (for $j^{\prime}\neq
2^{\prime}$) and to either $2$ or $2^{\prime}$; we denote the corresponding
sets of parties $R_{k}^{\prime}$ and $T_{k}^{\prime}$.

Notice that the union of $T_{k}$ and $R_{k}$ contains all non-primed parties
apart from party $2$, and so $R_{k}$ is fully determined by $T_{k}$.
Furthermore, it follows from Eq. (4) that $T^{\prime}_{k}$ is also fully
defined by the set $T_{k}$, meaning that the same is true for
$R^{\prime}_{k}$. Thus, each inflation $\mathcal{I}_{k}$ is fully specified by
the set $T_{k}$. However, the exact form of each $T_{k}$ depends on the
considered graph state, and so we define it later in the proof.

Having defined the inflations $\mathcal{I}_{k}$, we can now go on with the
proof. Let us consider two operators

$\tilde{g}_{1}=X_{1}Z_{2^{\prime}}^{\Gamma_{1,2}}Z_{\mathcal{N}_{1}\setminus\\{2\\}},\qquad
g_{2}=Z_{1}^{\Gamma_{1,2}}X_{2}Z_{\mathcal{N}_{2}\setminus\\{1\\}},$ (11)

where

$Z_{\mathcal{N}_{i}\setminus\\{j\\}}=\prod_{k\in\mathcal{N}_{i}\setminus\\{j\\}}Z_{k}^{\Gamma_{1,k}}.$
(12)

While $g_{2}$ stabilises the state $\ket{G}$ [cf. Eq. (1)], $\tilde{g}_{1}$ is
like $g_{1}$, however, with $Z^{\Gamma_{1,2}}$ acting on the party
$2^{\prime}$ instead of $2$. This difference between $g_{1}$ and
$\tilde{g}_{1}$ produces the following commutation relation:
$\tilde{g}_{1}g_{2}=\omega^{-\Gamma_{1,2}}g_{2}\tilde{g}_{1}$. Since we also
assume $\Gamma_{1,2}\neq 0$, Lemma 1 yields

$\sum_{k=0}^{d-1}\left\langle\tilde{g}_{1}^{k}+g_{2}^{k}\right\rangle_{\mathcal{I}_{0}}\leqslant
d+\sqrt{d},$ (13)

where $\mathcal{I}_{0}$ is defined by the set
$T_{0}=(\mathcal{N}_{1}\setminus(\mathcal{N}_{2}\cup\\{2\\}))\cup\\{1\\}$.

Next, using Fact 1 we show an equivalence between two expected values in
different inflations
$\left\langle\tilde{g}_{1}\right\rangle_{\mathcal{I}_{0}}=\langle
g_{1}\rangle_{\mathcal{I}_{1}}$, where $\mathcal{I}_{1}$ is another inflation
(Fig. 3) defined by $T_{1}=\mathcal{N}_{1}\cap\mathcal{N}_{2}$. We then
leverage Facts 1 and 2 to show that

$\langle g_{1}\rangle_{\mathcal{I}_{2}}=1,\quad\Rightarrow\quad\langle
g_{1}\rangle_{\mathcal{I}_{1}}=1,$ (14)

where $\mathcal{I}_{2}$ is an inflation (Fig. 3) defined by
$T_{2}=T_{1}\setminus\\{n\\}$ for some $n\in T_{1}$. Crucially, we can perform
this procedure again for different $n^{\prime}\in T_{1}$ which yields

$\langle g_{1}\rangle_{\mathcal{I}_{3}}=1,\quad\Rightarrow\quad\langle
g_{1}\rangle_{\mathcal{I}_{2}}=1,\quad\Rightarrow\quad\langle
g_{1}\rangle_{\mathcal{I}_{1}}=1,$ (15)

where $\mathcal{I}_{3}$ is an inflation (Fig. 3) defined by
$T_{3}=T_{1}\setminus\\{n,n^{\prime}\\}$.

This is the main idea of our proof: instead of showing the contradiction using
just two inflations (which can be challenging as is evident from Hansenne  _et
al._ (2022)), we start from inflation $\mathcal{I}_{1}$ and we gradually make
it more and more similar to the original network. How so? Notice that if
$T_{q}=\emptyset$ for some $q$, then $\mathcal{I}_{q}$ is an inflation
consisting of two copies of the original network. And so by decreasing the
size of $T_{k}$ in each step, our inflation gets closer to $\mathcal{I}_{q}$.
This procedure produces a chain of implications

$\langle g_{1}\rangle_{\mathcal{I}_{q}}=1\;\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}_{q-1}}=1\;\Rightarrow\dots\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}_{1}}=1,$ (16)

where $q=|\mathcal{N}_{1}\cap\mathcal{N}_{2}|+1$. Since $g_{1}$ acts
nontrivially only on non-primed parties, Fact 1 implies that $\langle
g_{1}\rangle_{\mathcal{I}_{q}}=\langle g_{1}\rangle_{\mathcal{O}}=1$, where we
also used the assumption that we generate a graph state $\ket{G}$ in
$\mathcal{O}$. Then, using
$\left\langle\tilde{g}_{1}\right\rangle_{\mathcal{I}_{0}}=\langle
g_{1}\rangle_{\mathcal{I}_{1}}$ and Eq. (16) we conclude that
$\left\langle\tilde{g}_{1}\right\rangle_{\mathcal{I}_{0}}=1$. So
$\tilde{g}_{1}$ is a stabilizing operator of a state generated in
$\mathcal{I}_{0}$, meaning that
$\left\langle\tilde{g}_{1}^{k}\right\rangle_{\mathcal{I}_{0}}=1$ for all $k$.

To calculate the other set of expected values in Eq. (13), it is sufficient to
consider an inflation $\mathcal{I}_{-1}$ (Fig. 3) with $T_{-1}=\\{1\\}$. A
single application of Facts 1 and 2 allows us to show that $\langle
g_{2}\rangle_{\mathcal{I}_{0}}=\langle g_{2}\rangle_{\mathcal{I}_{-1}}=\langle
g_{2}\rangle_{\mathcal{O}}=1$, where the last equality stems from our
assumption that $\ket{G}$ can be generated in $\mathcal{O}$. This in turn
implies that $g_{2}$ is a stabilizing operator of a state generated in
$\mathcal{I}_{0}$, therefore $\langle g_{2}^{k}\rangle=1$ for all $k$.
Consequently, the left side of (13) equals $2d$, leading to a contradiction. ∎

Using the standard continuity argument one can extend the result of Theorem 1
to any state that is sufficiently close to a graph state. Indeed, denoting
$F(\rho,\ket{\psi})=\bra{\psi}\rho\ket{\psi}$, we can formulate the following
result (see Appendix D for a proof).

######  Theorem 2.

Let us consider a state $\rho$ and a graph state $\ket{G}$. Moreover, let
$q=|\mathcal{N}_{1}\cap\mathcal{N}_{2}|+1$ for graphs $G$ that fulfil (10) and
$q=1$ in other cases. If

$F(\rho,\ket{G})>1-\frac{1}{8}\left(\beta^{2}+2\gamma-\beta\sqrt{\beta^{2}+4\gamma}\right),$
(17)

where $\beta=2q-1$ and $\gamma=(d-\sqrt{d})/(d-1)$, then $\rho$ cannot be
generated in an LOSR quantum network with bipartite sources.

Clearly, increasing $q$ makes the above bound tighter, which means that we can
exclude more states in the vicinity of $\ket{G}$ if $q$ is low. As an example,
let us consider the graph state corresponding to the graph presented on Fig.
1. Here $q=1$, $d=3$, and so (17) simplifies to $F(\rho,\ket{G})>0.952$.
Interestingly, the bound (17) can be relaxed by increasing $d$; in the limit
$d\rightarrow\infty$ for $q=1$ we obtain $F(\rho,\ket{G})>0.905$.

##  IV Conclusions

We have shown that for prime dimension of a local Hilbert space and for at
least three parties, generation of qudit graph states (as well as all states
that are in their close vicinity) is impossible in LOSR quantum networks with
bipartite sources. We achieve this goal by employing the quantum inflation
method. In fact, we demonstrate that the use of many different inflations of
the same network might be beneficial over using just two inflation as it is
typically done in the literature, and hence our work might inspire future
research involving quantum networks. On the one hand, our results serve as a
guide to experimental physicists who wish to implement protocols on quantum
networks that involve graph states. On the other hand, they hint at a possible
gain for construction of protocols that do not involve graph states, and so
can inspire theoretical constructions that use other classes of multipartite
states.

Still, many questions concerning LOSR quantum networks remain unexplored. In
the context of this work, the most obvious one is whether it is possible to
generate graph states with $k$-partite sources for $k\geqslant 3$. Even though
from the application point of view this case may be less important than that
of $k=2$, answering this question would certainly allow us to understand
quantum networks on a deeper level. Of course, one can also ask whether other
classes of multipartite states can be obtained in LOSR networks. Apart from
the graph states, this question was answered negatively for: symmetric or
antisymmetric states in Ref. Hansenne  _et al._ (2022), tripartite GHZ states
of arbitrary local dimension in Ref. Navascués  _et al._ (2020), and for pure,
genuinely entangled states of local dimension $2$ and $3$ in Ref. Luo (2021).
On the other hand, it would be interesting to determine the minimal amount of
resources in the form of classical communication required to generate graph
states in LOCC networks. In fact, it would be interesting to identify classes
of multipartite states for which the amount of rounds of classical
communication does not scale with the number of parties in the network.

##  V Note added

While finishing this manuscript, we became aware of a related work by Y.-X.
Wang et al. Wang  _et al._ (2022).

##  VI Acknowledgements

We thank Felipe Montealegre-Mora, David Wierichs and David Gross for useful
discussions. This work was supported by the National Science Center (Poland)
through the SONATA BIS (grant no. 2019/34/E/ST2/00369) and by Germany’s
Excellence Strategy – Cluster of Excellence Matter and Light for Quantum
Computing (ML4Q) EXC 2004/1 – 390534769.

##  Appendix A Proof of Lemma 1

Here we prove Lemma 1 stated in the main text.

######  Lemma 1.

Consider two unitary matrices $A_{1},A_{2}$ acting on some finite dimensional
Hilbert space $\mathbbm{C}^{D}$ with $D$ being a multiple of some prime number
$d\geq 2$. Assume moreover that $A_{i}$ are such that
$A_{1}^{d}=A_{2}^{d}=\mathbb{1}$ and $A_{1}A_{2}=\omega^{q}A_{2}A_{1}$ for
some $q\in\\{1,\dots,d-1\\}$. Then, the following inequality holds true

$\sum_{k=0}^{d-1}\langle A_{1}^{k}+A_{2}^{k}\rangle\leqslant d+\sqrt{d}.$ (18)

###### Proof.

We start from rewriting the sum in Eq. (18) in the following form

$\sum_{k=0}^{d-1}\langle
A_{1}^{k}+A_{2}^{k}\rangle=\sum_{k=0}^{d-1}\operatorname{tr}\left[(A_{1}^{k}+A_{2}^{k})\rho\right].$
(19)

Let us then assume that $A_{1}A_{2}=\omega^{q}A_{2}A_{1}$ for some
$q\in\\{1,\dots,d-1\\}$ and that $A_{1}^{d}=A_{2}^{d}=\mathbb{1}$. As proven
in Ref. Kaniewski  _et al._ (2019) (see Proposition B.1 in Appendix B) these
two conditions imply the existence of a unitary
$U:\mathbbm{C}^{D}\to\mathbbm{C}^{d}\otimes\mathcal{H}^{\prime}$ such that

$UA_{1}U^{\dagger}=X\otimes\mathbbm{1},\quad
UA_{2}U^{\dagger}=Z^{q}\otimes\mathbbm{1},$ (20)

where $\mathbbm{1}$ is the identity acting on $\mathcal{H}^{\prime}$. Denoting
$\rho^{\prime}=U\rho U^{\dagger}$, Eq. (19) can be rewritten as

$\sum_{k=0}^{d-1}\operatorname{tr}\left[(X^{k}+Z^{qk})\otimes\mathbb{1}\cdot\rho^{\prime}\right].$
(21)

We can trace out the subsystems corresponding to the Hilbert space
$\mathcal{H}^{\prime}$ which leads us to

$\sum_{k=0}^{d-1}\operatorname{tr}\left[(X^{k}+Z^{qk})\tilde{\rho}\right]=\sum_{k=0}^{d-1}\operatorname{tr}\left[(X^{k}+Z^{qk})\tilde{\rho}\right],$
(22)

where $\tilde{\rho}=\operatorname{tr}_{\mathcal{H}^{\prime}}\rho^{\prime}$.

Let us now consider the eigendecompositions of both $X$ and $Z$ operators,

$X=\sum_{i=0}^{d-1}\omega^{i}\ket{\phi_{i}}\\!\\!\bra{\phi_{i}},\qquad
Z=\sum_{i=0}^{d-1}\omega^{i}\ket{i}\\!\\!\bra{i},$ (23)

where $\ket{\psi_{i}}$ and $\ket{i}$ are the eigenvectors of $X$ and $Z$,
respectively. Exploiting the well-known fact that

$\sum_{k=0}^{d-1}\omega^{ki}=d\delta_{i,0},$ (24)

it is not difficult to observe that

$\sum_{k=0}^{d-1}X^{k}=d\ket{\phi_{0}}\\!\\!\bra{\phi_{0}},\qquad\sum_{k=0}^{d-1}Z^{kq}=d\ket{0}\\!\\!\bra{0},$
(25)

where $\ket{\phi_{0}}$ and $\ket{0}$ are eigenstates corresponding to the
eigenvalue $1$ of $X$ and $Z^{q}$, respectively. This, taking into account,
Eq. (22), allows us to rewrite Eq. (19) as

$\sum_{k=0}^{d-1}\langle
A_{1}^{k}+A_{2}^{k}\rangle=d\operatorname{tr}\left[(\ket{\phi_{0}}\\!\\!\bra{\phi_{0}}+\ket{0}\\!\\!\bra{0})\tilde{\rho}\right].$
(26)

Let us now notice that for any pair of normalized vectors $\ket{\psi_{i}}$
$(i=1,2)$, the sum of projectors
$P=\ket{\psi_{1}}\\!\\!\bra{\psi_{1}}+\ket{\psi_{2}}\\!\\!\bra{\psi_{2}}$ is a
rank-two matrix whose eigenvalues are $1\pm|\langle\psi_{1}|\psi_{2}\rangle|$
and therefore $\operatorname{tr}[P\sigma]\leq
1+|\langle\psi_{1}|\psi_{2}\rangle|$ for any $\sigma$. Taking into account
that the eigenbasis of $X$ and $Z^{q}$ are mutually unbiased, meaning that
$|\langle 0|\phi_{0}\rangle|=1/\sqrt{d}$, the above bound implies that

$\sum_{k=0}^{d-1}\langle A_{1}^{k}+A_{2}^{k}\rangle\leq d+\sqrt{d},$ (27)

which completes the proof. ∎

##  Appendix B An alternative equality

While the above inequality is enough to prove the main result of this paper,
we have found yet another way allowing to reach the same result that exploits
an equality. Let us present it here.

######  Lemma 2.

Given two positive real numbers $\lambda_{1},\lambda_{2}$ and two matrices
$A_{1},A_{2}$ such that $A_{1}^{d}=A_{2}^{d}=\mathbb{1}$ and
$A_{1}A_{2}=\omega^{q}A_{2}A_{1}$ for $q\in\\{1,\dots,d-1\\}$, if $q$ and $d$
are coprime it holds that

$\displaystyle\expectationvalue{(\lambda_{1}A_{1}+\lambda_{2}A_{2})^{nd}}=(\lambda_{1}^{d}+\lambda_{2}^{d})^{n}\qquad\forall
n\in\mathbbm{N}.$ (28)

###### Proof.

Exploiting the commutation relation $A_{2}A_{1}=\eta A_{1}A_{2}$, where
$\eta=\omega^{q}$, the fact that $A_{i}^{d}=\mathbbm{1}$ as well as Eq. (31)
one finds that

$\displaystyle(\lambda_{1}A_{1}+\lambda_{2}A_{2})^{d}$
$\displaystyle=\sum_{k=1}^{d-1}A_{1}^{d-k}A_{2}^{k}\lambda_{1}^{d-k}\lambda_{2}^{k}\sum_{i_{1}=0}^{d-k}\dots\sum_{i_{k}=i_{k-1}}^{d-k}\eta^{\sum_{j=1}^{k}i_{j}}$
$\displaystyle\hskip
14.22636pt+A_{1}^{d}\lambda_{1}^{d}+A_{2}^{d}\lambda_{2}^{d}.$ (29)

Using Eq. (31) proven below in Lemma 3 the above simplifies considerably to

$\displaystyle(\lambda_{1}A_{1}+\lambda_{2}A_{2})^{d}=A_{1}^{d}\lambda_{1}^{d}+A_{2}^{d}\lambda_{2}^{d},$
(30)

which due to the fact that $A_{i}^{d}=\mathbbm{1}$ leads us directly to Eq.
(28), completing the proof. ∎

######  Lemma 3.

Given $\eta=\omega^{-q}$ for $q\in\\{1,\dots,d-1\\}$, if $q$ and $d$ are
coprime, the following holds true

$\sum_{i_{1}=0}^{d-k}\sum_{i_{2}=i_{1}}^{d-k}\dots\sum_{i_{k}=i_{k-1}}^{d-k}\eta^{\sum_{j=1}^{k}i_{j}}=0,$
(31)

where $k\in\\{1,\dots,d-1\\}$.

###### Proof.

Let us consider the expression on the left-hand side of Eq. (31) and shift the
summation index in the last sum by $k$. That is, we apply the transformation
$i_{k}\to i_{k}-k$, which leads us to

$\sum_{i_{1}=0}^{d-k}\dots\sum_{i_{k}=i_{k-1}}^{d-k}\eta^{\sum_{j=1}^{k}i_{j}}=\eta^{-k}\sum_{i_{1}=0}^{d-k}\dots\sum_{i_{k}=i_{k-1}+k}^{d}\eta^{\sum_{j=1}^{k}i_{j}}.$
(32)

We then implement a similar transformation to the last but one sum, but this
time we shift the index by $k-1$ [$i_{k-1}\to i_{k-1}-(k-1)$], which allows us
to rewrite the above as

$\displaystyle\eta^{-k}\sum_{i_{1}=0}^{d-k}\dots\sum_{i_{k-1}=i_{k-2}}^{d-k}\sum_{i_{k}=i_{k-1}+k}^{d}\eta^{\sum_{j=1}^{k}i_{j}}$
$\displaystyle=\eta^{-k-(k-1)}\sum_{i_{1}=0}^{d-k}\dots\sum_{i_{k-1}=i_{k-2}+k-1}^{d-1}\sum_{i_{k}=i_{k-1}+1}^{d}\eta^{\sum_{j=1}^{k}i_{j}}.$

Notice that this action changes also the summation range of the last sum.

We then recursively shift the remaining summation indices as $i_{j}\to
i_{j}-j$ for $j=1,\ldots,k-2$, which yields the following expression

$\displaystyle\sum_{i_{1}=0}^{d-k}\sum_{i_{2}=i_{1}}^{d-k}\dots\sum_{i_{k}=i_{k-1}}^{d-k}\eta^{\sum_{j=1}^{k}i_{j}}$
$\displaystyle=\eta^{-k(k+1)/2}\sum_{i_{1}=1}^{d-k+1}\;\sum_{i_{2}=i_{1}+1}^{d-k+2}\dots\sum_{i_{k}=i_{k-1}+1}^{d}\eta^{\sum_{j=1}^{k}i_{j}},$

which can also be stated as

$\displaystyle\sum_{i_{1}=0}^{d-k}\sum_{i_{2}=i_{1}}^{d-k}\dots\sum_{i_{k}=i_{k-1}}^{d-k}\eta^{\sum_{j=1}^{k}i_{j}}$
$\displaystyle=\eta^{-k(k+1)/2}\sum_{1\leq i_{i}<i_{2}<\dots<i_{k}\leq
d}\eta^{\sum_{j=1}^{k}i_{j}}.$ (35)

Our aim now is to prove that the above sum vanishes. To this end, we employ
the so-called Vieta’s formulas which relate roots $x_{j}$ of any complex
polynomial of degree $n$

$P_{n}(x)=\sum_{i=0}^{n}a_{i}x^{i},$ (36)

to the coefficients $a_{i}$ defining it,

$\sum_{1\leq i_{i}<i_{2}<\dots<i_{k}\leq
n}\left(\prod_{j=1}^{k}x_{i_{j}}\right)=(-1)^{k}\frac{a_{n-k}}{a_{n}}.$ (37)

Let us then consider a particular polynomial of degree $d$,

$P_{d}^{\omega}(x)=x^{d}-1,$ (38)

whose roots are obviously $\omega^{i}$. However instead of enumerating these
roots by powers of $\omega$, i.e., $x_{i}=\omega^{i}$, we can use the fact
that $q$ and $d$ are coprime and enumerate them by powers of $\eta$, that is,

$x_{i}=\eta^{i}.$ (39)

Since all coefficients of this polynomial except $a_{d}$ and $a_{0}$ are zero,
Eq. (37) implies that for any $k=1,\ldots,d-1$,

$\sum_{1\leq i_{i}<i_{2}<\dots<i_{k}\leq
d}\;\prod_{j=1}^{k}\eta^{i_{j}}=\sum_{1\leq i_{i}<i_{2}<\dots<i_{k}\leq
d}\eta^{\sum_{j=1}^{k}i_{j}}=0.$ (40)

Substitution of the above equation to Eq. (B) ends the proof. ∎

##  Appendix C Proof of Theorem 1

Before we proceed with the proof of Theorem 1 let us introduce a couple of
important notions.

First, if a graph $G$ can be transformed into a graph $G^{\prime}$ using a set
of transformations called local complementations, then there exists a set of
local unitaries $U_{i}$ such that

$\ket{G}=\bigotimes_{i=1}^{N}U_{i}\ket{G^{\prime}}$ (41)

(see Theorem 5 in Bahramgiri and Beigi (2007)). The local complementations on
the vertex $n$ consist of the transformations of a graph $G$ to a graph
$G^{\prime}$ such that

$\Gamma_{i,j}^{\prime}=\Gamma_{i,j}+a_{n}\Gamma_{i,n}\Gamma_{j,n},$ (42)

where $a_{n}\in\\{0,\dots,d-1\\}$.

Next, let $\mathcal{O}$ be a network and
$B=\bigotimes_{i\in\mathcal{O}}B_{i}$. We call a subnetwork of $\mathcal{O}$
the $B$ subnetwork if it consists only of parties $i$ for which
$B_{i}\neq\mathbb{1}$ and sources that distribute states to said parties. For
example, if $\mathcal{O}$ is a tripartite, fully-connected network and
$B=X\otimes X\otimes\mathbb{1}$, then the $B$ subnetwork of $\mathcal{O}$ is a
network consisting of parties $1$ and $2$ and a source distributing a
bipartite state to those parties. This definition does not introduce anything
new as one can notice that in Fact 1 we have already used these types of
subnetworks. What this definition does, is that facilitates the application of
Fact 1 which will be of great help in the proof of Theorem 1.

Finally, it will be convenient to consider certain sets of graph states
separately. This division into sets is done with the following lemma.

######  Lemma 4.

Every graph that has at least $3$ vertices and has at least one vertex with a
neighbourhood $|\mathcal{N}_{i}|\geqslant 2$ can be transformed using local
complementations and relabelling into a graph $G$ that fulfils
$|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geqslant 2$, $\Gamma_{1,2}\neq 0$
and one of the four following sets of conditions:

  1. 1.

$\mathcal{N}_{1}\cap\mathcal{N}_{2}=\emptyset$,

  2. 2.

$\mathcal{N}_{1}\cap\mathcal{N}_{2}\neq\emptyset$ and for all
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ we have
$\mathcal{N}_{2}\setminus\\{n\\}\neq\mathcal{N}_{n}\setminus\\{2\\}$,

  3. 3.

$|\mathcal{N}_{1}\cap\mathcal{N}_{2}|=1$ and there exists
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ such that
$\mathcal{N}_{2}\setminus\\{n\\}=\mathcal{N}_{n}\setminus\\{2\\}$,

  4. 4.

$|\mathcal{N}_{1}\cap\mathcal{N}_{2}|\geqslant 2$, there exists
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ such that
$\mathcal{N}_{2}\setminus\\{n\\}=\mathcal{N}_{n}\setminus\\{2\\}$, and there
exists $a_{n}\in\\{1,\dots,d-1\\}$ such that for all
$i\in\mathcal{N}_{n}\setminus\\{2\\}$ we have
$\Gamma_{2,i}+a_{n}\Gamma_{2,n}\Gamma_{n,i}=0$.

###### Proof.

We assume that a graph $G$ has at least $3$ vertices and that at least one
vertex has a neighbourhood $|\mathcal{N}_{i}|\geqslant 2$, and so, without a
loss of generality, we can take $|\mathcal{N}_{1}|\geqslant 2$ and
$\Gamma_{1,2}\neq 0$. Then we act $a_{1}$ times with a local complementation
on vertex $1$, which gives us

$\Gamma_{2,n}^{\prime}=\Gamma_{2,n}+a_{1}\Gamma_{1,2}\Gamma_{1,n},$ (43)

where $n\in\mathcal{N}_{1}$. We choose $a_{1}$ such that
$\Gamma_{2,n}^{\prime}=0$, and since local complementation on $1$ does not
change $\Gamma_{1,2}$, it implies
$|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geqslant 2$. If after this
operation we have $\mathcal{N}_{1}\cap\mathcal{N}_{2}=\emptyset$ then the
first set of conditions in the lemma is fulfilled.

As for the case when $\mathcal{N}_{1}\cap\mathcal{N}_{2}\neq\emptyset$, the
graph $G$ fulfils the second set of conditions in the lemma if for all
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ we have

$\mathcal{N}_{2}\setminus\\{n\\}\neq\mathcal{N}_{n}\setminus\\{2\\}.$ (44)

Let us now consider a case where for some
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ the above equation does not hold
true. If $|\mathcal{N}_{1}\cap\mathcal{N}_{2}|=1$ then the third set of
conditions in the lemma is fulfilled. Otherwise, let us consider a local
complementation on the vertex $n$

$\Gamma_{2,i}^{\prime}=\Gamma_{2,i}+a_{n}\Gamma_{2,n}\Gamma_{n,i},$ (45)

where $i\in\mathcal{N}_{n}$. We assume that (44) does not hold for $n$, hence
for every $i$ we also have $i\in\mathcal{N}_{2}$. If one can find $a_{n}$ such
that $\Gamma_{2,i}^{\prime}=0$ for all $i\in\mathcal{N}_{n}$, then the fourth
set of assumptions from the lemma is fulfilled.

Conversely, if choosing such an $a_{n}$ is not possible, then we can take
$a_{n}$ such that $\Gamma_{1,2}^{\prime}\neq 0$ and such that there exists
$i\in\mathcal{N}_{2}$ for which $\Gamma_{2,i}^{\prime}=0$. Clearly, after this
transformation we get

$|\mathcal{N}_{2}^{\prime}|<|\mathcal{N}_{2}|.$ (46)

Let us investigate the properties of this transformed graph. First of all
$\Gamma_{1,2}\neq 0$, since that was the condition on $a_{n}$. Next, the local
complementation on the vertex $n$ by definition does not change $\Gamma_{i,n}$
for all $i$, so in particular we still have $\Gamma_{1,n}\neq 0$ and
$\Gamma_{2,n}\neq 0$ which implies
$\mathcal{N}_{1}\cap\mathcal{N}_{2}\neq\emptyset$. Last but not least, the
action of a local complementation on vertex
$n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ cannot decrease the size of a set
$\mathcal{N}_{1}\setminus\mathcal{N}_{2}$ meaning, that the assumption
$|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geqslant 2$ still holds.

To see why the last claim holds true, notice that to decrease the size of a
set $\mathcal{N}_{1}\setminus\mathcal{N}_{2}$ we would have to have
$\Gamma_{1,j}\neq 0$ and $\Gamma_{2,j}=0$ for some $j$ before the action of
the local complementation on $n$, and after said action either
$\Gamma^{\prime}_{1,j}=0$ or $\Gamma^{\prime}_{2,j}=0$. However, from the
assumption
$\mathcal{N}_{2}\setminus\\{n\\}\neq\mathcal{N}_{n}\setminus\\{2\\}$ it
follows that $\Gamma_{n,j}=0$. Crucially, this implies that under the action
of local complementation on $n$ we have

$\Gamma^{\prime}_{j,k}=\Gamma_{j,k}$ (47)

for all $k$, hence $\Gamma^{\prime}_{1,j}=\Gamma_{1,j}$ and
$\Gamma^{\prime}_{2,j}=\Gamma_{2,j}$.

The key observation here is that the new graph created after action of local
complementation fulfils $|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geqslant
2$, $\Gamma_{1,2}\neq 0$ and
$\mathcal{N}_{1}\cap\mathcal{N}_{2}\neq\emptyset$, and so we can check if the
new graph fulfils conditions 2, 3 or 4 from the lemma and if they are not
fulfilled, then we again create a new graph by action of local complementation
on some $\tilde{n}\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$. Every time we act
with this local complementation we get (46), which implies that after a finite
amount of repetition of this procedure, we will get
$|\mathcal{N}_{1}\cap\mathcal{N}_{2}|=1$ which fulfils either second or third
condition from the lemma. ∎

With that, we are ready to prove Theorem 1.

###### Proof.

We assume that the graph $G$ consists of at least three vertices and has at
least one vertex $i$ such that $|\mathcal{N}_{i}|\geqslant 2$. So by the
virtue of Lemma 4 by using local complementations and relabelling we can
transform $G$ into a graph that fulfils one of the four sets of conditions.
Acting with a local complementation on a graph $G$ corresponds to acting with
local unitaries on a graph state $\ket{G}$, and so it is sufficient to only
consider graphs that fulfil one of the four sets of conditions in Lemma 4.

Since every inflation in this proof has a very similar structure, let us begin
by discussing these similarities in order to make the proof easier to follow.
All inflations $\mathcal{I}_{k}^{l}$ that we consider in this proof share two
assumptions. First, every $\mathcal{I}_{k}^{l}$ consists of exactly two copies
of every party, denoted $i$ and $i^{\prime}$, and two copies of every source
from $\mathcal{O}$. Second, a non-primed party $i$ (for $i\neq 2$) is
connected to every other non-primed party $j$ (for $j\neq 2$) and to either
$2$ or $2^{\prime}$. Likewise, every primed party $i^{\prime}$ (for
$i^{\prime}\neq 2^{\prime}$) has to be connected to every other primed party
$j^{\prime}$ (for $j^{\prime}\neq 2^{\prime}$) and to either $2$ or
$2^{\prime}$. These two assumptions allow us to precisely describe an
inflation just by defining the set of non-primed parties connected to
$2^{\prime}$, which we denote by $T_{k}^{l}$. For a graphical description, see
Fig. 3.

We structure this proof in the following way: in Part 1 we consider graphs $G$
fulfilling the first or the second set of conditions from Lemma 4, in Part 2
we consider graphs $G$ fulfilling the third set of conditions and in Part 3 we
consider graphs fulfilling the fourth set of conditions.

Part 1. Here, we assume that a graph $G$ fulfils the first or second set of
conditions from Lemma 4. Both these sets of conditions imply the same
structure of the first two stabilizing operators, namely:

$\displaystyle\begin{split}g_{1}&=X_{1}Z_{2}^{\Gamma_{1,2}}Z_{\mathcal{N}_{1}\setminus\\{2\\}},\\\
g_{2}&=Z_{1}^{\Gamma_{1,2}}X_{2}Z_{\mathcal{N}_{2}\setminus\\{1\\}},\end{split}$
(48)

where

$Z_{\mathcal{N}_{i}\setminus\\{j\\}}=\prod_{k\in\mathcal{N}_{i}\setminus\\{j\\}}Z_{k}^{\Gamma_{i,k}}.$
(49)

Let us consider an inflation $\mathcal{I}^{1}_{0}$ for which

$T^{1}_{0}=\Big{(}\mathcal{N}_{1}\setminus(\mathcal{N}_{2}\cup\\{2\\})\Big{)}\cup\\{1\\}.$
(50)

By the virtue of Lemma 1, the following holds true:

$\sum_{k=0}^{d-1}\left\langle\tilde{g}_{1}^{k}\right\rangle_{\mathcal{I}_{0}^{1}}+\left\langle
g_{2}^{k}\right\rangle_{\mathcal{I}^{1}_{0}}\leq d+\sqrt{d},$ (51)

where
$\tilde{g}_{1}=X_{1}Z_{2^{\prime}}^{\Gamma_{1,2}}Z_{\mathcal{N}_{1}\setminus\\{2\\}}$.
To complete the proof we will show that the above inequality is violated,
since if one could generate the aforementioned graph state in the network
$\mathcal{O}$, then the above operators stabilize the state generated in the
inflation $\mathcal{I}_{0}^{1}$. We begin our analysis with the operator
$\tilde{g}_{1}$. To show that this operator is a stabilizing operator, let us
consider another inflation $\mathcal{I}^{1}_{1}$ for which

$T^{1}_{1}=\mathcal{N}_{1}\cap\mathcal{N}_{2}.$ (52)

Notice that the union

$T^{1}_{0}\cup
T^{1}_{1}\cup\\{2^{\prime}\\}=(\mathcal{N}_{1}\setminus\\{2\\})\cup\\{1,2^{\prime}\\}$
(53)

describes a set of parties in a $\tilde{g}_{1}$ subnetwork of
$\mathcal{I}^{1}_{0}$. In this subnetwork, every party from the set $T_{0}$ is
connected to $2^{\prime}$ and to $T^{1}_{1}$, but $2^{\prime}$ and $T^{1}_{1}$
are unconnected. Similarly, in the inflation $\mathcal{I}^{1}_{1}$, every
party from the set $T^{1}_{0}$ is connected to $2$ and to $T^{1}_{1}$, but $2$
and $T_{1}$ are unconnected, hence by the virtue of Fact 1 we have

$\left\langle\tilde{g}_{1}\right\rangle_{\mathcal{I}^{1}_{0}}=\langle
g_{1}\rangle_{\mathcal{I}^{1}_{1}}.$ (54)

The first set of assumptions from Lemma 4 implies $T^{1}_{1}=\emptyset$ which
gives us $\langle g_{1}\rangle_{\mathcal{I}^{1}_{1}}=\langle
g_{1}\rangle_{\mathcal{O}}=1$, since we assume that we generate a graph state
$\ket{G}$ in the original network $\mathcal{O}$. Of course, for the second set
of assumptions we have $T^{1}_{1}\neq\emptyset$, and so the same implication
does not hold. Therefore, for the next few paragraphs we only consider the
second set of assumptions from Lemma 4 and we will return to considering both
after showing that $\langle g_{1}\rangle_{\mathcal{I}^{1}_{1}}=\langle
g_{1}\rangle_{\mathcal{O}}=1$ holds also for the second set of assumptions.

One of the assumptions from the second set of assumptions from Lemma 4 states
that for all $n\in\mathcal{N}_{1}\cap\mathcal{N}_{2}$ we have

$\mathcal{N}_{2}\setminus\\{n\\}\neq\mathcal{N}_{n}\setminus\\{2\\}.$ (55)

Consequently, given two stabilizing operators $g_{2}$ and $g_{n}$ there has to
exist a qubit $i$ such that $i\neq 2,n$ and $g_{2}^{(i)}\neq g_{n}^{(i)}$,
where $g_{k}^{(i)}$ denotes a matrix of $g_{k}$ acting on the subsystem
corresponding to the party $i$. Utilising the symmetry:
$g^{(j)}_{i}=g^{(i)}_{j}$, we get two possibilities: either

$g_{i}^{(2)}=\mathbb{1},\qquad g_{i}^{(n)}=Z^{\Gamma_{i,n}}$ (56)

or

$g_{i}^{(2)}=Z^{\Gamma_{2,i}},\qquad g_{i}^{(n)}=\mathbb{1},$ (57)

where $\Gamma_{i,n},\Gamma_{2.i}\neq 0$. In what follows, we assume that Eq.
(56) is true, and we will later come back to the case of Eq. (57).

By the virtue of Fact 2 we have an implication

$\langle g_{i}^{-l}\rangle_{\mathcal{I}^{1}_{1}}=\langle
g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{1}}=1\quad\Rightarrow\quad\langle
g_{1}\rangle_{\mathcal{I}^{1}_{1}}=1,$ (58)

where $l\in\\{1,\dots,d-1\\}$.

From (56) it follows that the $g_{i}^{-l}$ subnetwork of $\mathcal{I}^{1}_{1}$
does not contain party $2$. Remember that we choose inflations such that every
non-primed party is connected to every other party with an exception of party
$2$, meaning that if a subnetwork does not contain the party $2$ or
$2^{\prime}$ then it is fully connected, which is exactly the case for the
$g_{i}^{-l}$ subnetwork of $\mathcal{I}^{1}_{1}$. Consequently, from Fact 1 it
follows that

$\langle g_{i}^{-l}\rangle_{\mathcal{I}^{1}_{1}}=\langle
g_{i}^{-l}\rangle_{\mathcal{O}}=1,$ (59)

where in the second equality we used the assumption that we generate a graph
state on the network $\mathcal{O}$. As for the expected value $\langle
g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{1}}$, in order to calculate it, we
first have to introduce another inflation $\mathcal{I}^{1}_{2}$ for which

$T^{1}_{2}=(\mathcal{N}_{1}\cap\mathcal{N}_{2})\setminus\\{n\\}.$ (60)

Notice, that the only difference between inflations $\mathcal{I}^{1}_{1}$ and
$\mathcal{I}^{1}_{2}$ is that in the former, parties $2^{\prime}$ and $n$ are
connected and in the latter $2$ and $n$. Crucially, since $d$ is prime and
$\Gamma_{i,n}\neq 0$, we can always take

$l=-\Gamma_{1,n}\Gamma_{i,n}^{-1},$ (61)

where we take the inverse and the negation to be operations in
$\mathbb{Z}_{d}$, i.e., $l\in\\{1,\dots,d-1\\}$. This implies that the
$g_{1}g_{i}^{l}$ subnetwork of $\mathcal{I}^{1}_{1}$ does not contain party
$n$, therefore by Fact 1 we have

$\langle g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{1}}=\langle
g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{2}}.$ (62)

Lastly, by using Fact 2 we can show that if $\langle
g_{1}\rangle_{\mathcal{I}^{1}_{2}}=\langle
g_{i}^{l}\rangle_{\mathcal{I}^{1}_{2}}=1$ then $\langle
g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{2}}=1$. Furthermore, since $g_{i}^{l}$
subnetwork of $\mathcal{I}^{1}_{2}$ does not contain party $2$, we have
$\langle g_{i}^{l}\rangle_{\mathcal{I}^{1}_{2}}=\langle
g_{i}^{l}\rangle_{\mathcal{O}}=1$, and so:

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{2}}=1\;\Rightarrow\;\langle
g_{1}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{2}}=1\;\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}^{1}_{1}}=1.$ (63)

As for the case when Eq. (57) is true, the proof has mostly the same
structure, but with $g_{i}^{-l}$ and $g_{1}g_{i}^{l}$ swapped. The only other
difference is that, using the fact that $d$ is prime and $\Gamma_{2,i}\neq 0$,
we take $l\in\mathbb{Z}_{d}$ such that

$l=-\Gamma_{1,2}\Gamma_{2,i}^{-1}.$ (64)

As a result, we have the same implication as in the first case:

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{2}}=1\;\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}^{1}_{1}}=1.$ (65)

Since both cases result in the above implication, we can now take a different
$n$ and apply the same procedure to produce an implication

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{3}}=1\;\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}^{1}_{2}}=1,$ (66)

where
$T^{1}_{3}=(\mathcal{N}_{1}\cap\mathcal{N}_{2})\setminus\\{n,n^{\prime}\\}$.
Repeating this procedure for all $n\in T_{1}$ results in a chain of
implications

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{q}}=1\;\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}^{1}_{q-1}}=1\;\Rightarrow\dots\Rightarrow\;\langle
g_{1}\rangle_{\mathcal{I}^{1}_{1}}=1,$ (67)

where $q=|\mathcal{N}_{1}\cap\mathcal{N}_{2}|+1$. However, for
$\mathcal{I}^{1}_{q}$ we have $T^{1}_{q}=\emptyset$, and so

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{q}}=\langle
g_{1}\rangle_{\mathcal{O}}=1.$ (68)

This is the first statement in the chain of implications (67), and so

$\langle g_{1}\rangle_{\mathcal{I}^{1}_{1}}=1,$ (69)

which, by the virtue of Eq. (54) implies

$\langle\tilde{g}_{1}\rangle_{\mathcal{I}^{1}_{0}}=1.$ (70)

As a direct implication of the above, we have that $\tilde{g}_{1}$ is a
stabilizing operator of $\mathcal{I}^{1}_{0}$.

We now come back to the inequality (51) and show that $g_{2}$ is also a
stabilizing operator of a state generated in the inflation
$\mathcal{I}^{1}_{0}$. We again consider both the first and second set of
assumption from Lemma 4. The $g_{2}$ subnetwork of $\mathcal{I}^{1}_{0}$ is a
fully connected subnetwork, apart from the lacking connection between parties
$1$ and $2$. Therefore, from Fact 1 we have that

$\langle g_{2}\rangle_{\mathcal{I}^{1}_{0}}=\langle
g_{2}\rangle_{\mathcal{I}^{1}_{-1}},$ (71)

where $\mathcal{I}^{1}_{-1}$ is an inflation with

$T^{1}_{-1}=\\{1\\}.$ (72)

From $|\mathcal{N}_{1}\setminus\mathcal{N}_{2}|\geq 2$ it follows that there
exists $i\in\mathcal{N}_{1}$ for which

$g_{i}^{(1)}=Z^{\Gamma_{1,i}},\qquad g_{i}^{(2)}=\mathbb{1},$ (73)

where we used the symmetry $g_{i}^{(j)}=g_{j}^{(i)}$. Next, by the virtue of
Fact 2 we have

$\langle g_{i}^{-l}\rangle_{\mathcal{I}^{1}_{-1}}=\langle
g_{2}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{-1}}=1\;\Rightarrow\;\langle
g_{2}\rangle_{\mathcal{I}^{1}_{-1}}=1,$ (74)

where we take $l\in\mathbb{Z}_{d}$ such that

$l=-\Gamma_{1,2}\Gamma_{1,i}^{-1}.$ (75)

Notice, that $\langle g_{2}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{-1}}$ has no
nontrivial matrix on the first party and $\langle
g_{i}^{-l}\rangle_{\mathcal{I}^{1}_{-1}}$ has no nontrivial matrix on the
second party meaning that the $g_{2}g_{i}^{l}$ and $g_{i}^{-l}$ subnetworks of
$\mathcal{I}^{1}_{-1}$ are fully connected which by the Fact 1 implies

$\langle g_{i}^{-l}\rangle_{\mathcal{I}^{1}_{-1}}=\langle
g_{i}^{-l}\rangle_{\mathcal{O}}=1,\qquad\langle
g_{2}g_{i}^{l}\rangle_{\mathcal{I}^{1}_{-1}}=\langle
g_{2}g_{i}^{l}\rangle_{\mathcal{O}}=1,$ (76)

and so by the virtue of Eq. (71) and Eq. (74) we have

$\langle g_{2}\rangle_{\mathcal{I}^{1}_{0}}=1,$ (77)

i.e., $g_{2}$ is a stabilizing operator of a state generated in
$\mathcal{I}^{1}_{0}$.

As a consequence of the above result and (69), the inequality (51) is
violated, meaning that our assumption was wrong - graph states corresponding
to a graph that admit the first or the second set of assumptions from Lemma 4
cannot be generated in a network with bipartite sources.

Part 2. We now assume that the graph $G$ fulfils the third set of conditions
from Lemma 4. In this part we will only use three stabilizing operators,
namely

$\displaystyle\begin{split}g_{1}&=X_{1}Z_{2}^{\Gamma_{1,2}}Z_{n}^{\Gamma_{1,n}}Z_{\mathcal{N}_{1}\setminus\\{2,n\\}},\\\
g_{2}&=Z_{1}^{\Gamma_{1,2}}X_{2}Z_{n}^{\Gamma_{2,n}}Z_{\mathcal{N}_{2}\setminus\\{1,n\\}},\\\
g_{n}&=Z_{1}^{\Gamma_{1,n}}Z_{2}^{\Gamma_{2,n}}X_{n}Z_{\mathcal{N}_{n}\setminus\\{1,2\\}},\end{split}$
(78)

where $\mathcal{N}_{1}\cap\mathcal{N}_{2}=\\{n\\}$. Let us consider an
inflation $\mathcal{I}_{0}^{2}$ for which
$T_{0}^{2}=\mathcal{N}_{2}\setminus\\{1,n\\}$. We can use Lemma 1 to construct
an inequality:

$\begin{split}\sum_{k=0}^{d-1}\expectationvalue{s^{k}}_{\mathcal{I}_{0}^{2}}+\expectationvalue{g_{1}^{k}}_{\mathcal{I}_{0}^{2}}\leqslant
d+\sqrt{d},\end{split}$ (79)

where

$s=X_{2^{\prime}}Z_{2^{\prime}}^{l\Gamma_{2,n}}Z_{n}^{\Gamma_{2,n}}X_{n}^{l}Z_{\mathcal{N}_{2}\setminus\\{1,n\\}}Z_{\mathcal{N}_{n}\setminus\\{1,2\\}}^{l},$
(80)

and we take $l\in\mathbb{Z}_{d}$ such that

$l=-\Gamma_{1,2}\Gamma_{1,n}^{-1}.$ (81)

From the assumption $|\mathcal{N}_{1}\cap\mathcal{N}_{2}|=1$ we can infer that
the $g_{1}^{k}$ subnetwork of $\mathcal{I}_{0}^{2}$ does not contain any party
from the set $T_{0}^{2}$, hence we can use Fact 1 and our assumption about the
generation of a graph state in the network $\mathcal{O}$ to get

$\langle g_{1}^{k}\rangle_{\mathcal{I}_{0}^{2}}=\langle
g_{1}^{k}\rangle_{\mathcal{O}}=1,$ (82)

hence, for all $k$, $g_{1}^{k}$ is a stabilizing operator of a state generated
in $\mathcal{I}^{2}_{0}$.

In order to tackle the second operator from Eq. (79), let us first introduce
another inflation $\mathcal{I}_{1}^{2}$ with $T_{1}^{2}=\\{n\\}$. From Fact 1
it follows that

$\displaystyle\begin{split}\left\langle
s\right\rangle_{\mathcal{I}_{0}^{2}}=\left\langle
g_{2}g_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{2}}.\end{split}$ (83)

The above can be easily shown by comparing the two operators and its
corresponding subnetworks of $\mathcal{I}_{0}^{2}$ and $\mathcal{I}_{1}^{2}$:
the former is fully-connected apart from the lacking connection between
$2^{\prime}$ and $n$, and the latter is fully-connected apart from the lacking
connection between $2$ and $n$.

By the virtue of Fact 2 we have

$\langle g_{1}^{-m}g_{2}\rangle_{\mathcal{I}_{1}^{2}}=\langle
g_{1}^{m}g_{n}^{l}\rangle_{\mathcal{I}_{1}^{2}}=1\quad\Rightarrow\quad\langle
g_{2}g_{n}^{l}\rangle_{\mathcal{I}_{1}^{2}}=1,$ (84)

where we take $m\in\mathbb{Z}_{d}$ to be

$m=\Gamma_{2,n}\Gamma_{1,n}^{-1}.$ (85)

A quick look at the $g_{1}^{-m}g_{2}$ and $g_{1}^{m}g_{n}^{l}$ subnetworks of
$\mathcal{I}_{1}^{2}$ reveals that both of them are fully-connected, since
they do not contain party $n$ and party $2$ respectively, hence from Fact 1 we
have

$\langle g_{1}^{-m}g_{2}\rangle_{\mathcal{I}_{1}^{2}}=\langle
g_{1}^{-m}g_{2}\rangle_{\mathcal{O}}=1,\langle
g_{1}^{m}g_{n}^{l}\rangle_{\mathcal{I}_{1}^{2}}=\langle
g_{1}^{m}g_{n}^{l}\rangle_{\mathcal{O}}=1,$ (86)

where we used the assumption that we can generate a graph state $\mathcal{G}$
in the network $\mathcal{O}$. However, the above implies

$\left\langle s\right\rangle_{\mathcal{I}_{0}^{2}}=1,$ (87)

and so, as was the case with $g_{1}$, the above operator is a stabilizing
operator of a state generated in $\mathcal{I}_{0}^{2}$. Therefore, the
inequality (79) is violated, which implies that the graph state corresponding
to a graph that fulfils the third set of conditions from Lemma 4 cannot be
generated in a considered quantum network.

Part 3. In this part, we consider graphs $G$ that fulfil the fourth set of
conditions from Lemma 4. The stabilizing operators used in this part of the
proof have the same general structure as the once we have used in the previous
part (see Eq. (78)).

Let us consider an inflation $\mathcal{I}_{0}^{3}$ for which
$T_{0}^{3}=\emptyset$. By the virtue of Lemma 1 we can construct the following
inequality:

$\sum_{k=0}^{d-1}\left\langle\left(X_{2^{\prime}}Z_{2^{\prime}}^{l\Gamma_{2,n}}Z_{n}^{\Gamma_{2,n}}X_{n}^{l}\right)^{k}+g_{1}^{k}\right\rangle_{\mathcal{I}_{0}^{3}}\leqslant
d+\sqrt{d},$ (88)

where $l\in\mathbb{Z}_{d}$. From Fact 1 and from the assumption that we can
generate a graph state $\ket{G}$ in the network $\mathcal{O}$ it follows that

$\left\langle g_{1}\right\rangle_{\mathcal{I}_{0}^{3}}=\left\langle
g_{1}\right\rangle_{\mathcal{O}}=1,$ (89)

and so $g_{1}$ is a stabilizing operator of a state generated in
$\mathcal{I}_{0}^{3}$. Next, let us consider an inflation
$\mathcal{I}_{1}^{3}$ for which $T_{1}^{3}=\\{n\\}$. It trivially follows from
Fact 1 that

$\left\langle
X_{2^{\prime}}Z_{2^{\prime}}^{l\Gamma_{2,n}}Z_{n}^{\Gamma_{2,n}}X_{n}^{l}\right\rangle_{\mathcal{I}_{0}^{3}}=\left\langle
X_{2}Z_{2}^{l\Gamma_{2,n}}Z_{n}^{\Gamma_{2,n}}X_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}.$
(90)

Furthermore, one of the assumptions states that there exists
$a_{n}\in\\{1,\dots,d-1\\}$ such that for all
$i\in\mathcal{N}_{n}\setminus\\{2\\}$ we have

$\Gamma_{2,i}+a_{n}\Gamma_{2,n}\Gamma_{n,i}=0.$ (91)

Taking $l=a_{n}\Gamma_{2,n}$ we get

$\left\langle
X_{2}Z_{2}^{l\Gamma_{2,n}}Z_{n}^{\Gamma_{2,n}}X_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}=\left\langle
g_{2}g_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}.$ (92)

Now, we can use Fact 2 to construct an implication

$\left\langle g_{1}^{m}g_{2}\right\rangle_{\mathcal{I}_{1}^{3}}=\left\langle
g_{1}^{-m}g_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}=1\quad\Rightarrow\quad\left\langle
g_{2}g_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}=1,$ (93)

where we take $m\in\mathbb{Z}_{d}$ such that

$m=-\Gamma_{2,n}\Gamma_{1,n}.$ (94)

It is easy to show that the $g_{1}^{m}g_{2}$ subnetwork of
$\mathcal{I}_{1}^{3}$ does not contain party $n$ and that the
$g_{1}^{-m}g_{n}^{l}$ subnetwork of $\mathcal{I}_{1}^{3}$ does not contain
party $2$. Therefore, both of these subnetworks are connected, which by the
virtue of Fact 1 implies

$\left\langle g_{1}^{m}g_{2}\right\rangle_{\mathcal{I}_{1}^{3}}=\left\langle
g_{1}^{m}g_{2}\right\rangle_{\mathcal{O}}=1,$ (95) $\left\langle
g_{1}^{-m}g_{n}^{l}\right\rangle_{\mathcal{I}_{1}^{3}}=\left\langle
g_{1}^{-m}g_{n}^{l}\right\rangle_{\mathcal{O}}=1.$ (96)

Consequently, both operators in (88) stabilize a state generated in
$\mathcal{I}_{0}^{3}$ and so the inequality (88) is violated which ends the
proof. ∎

##  Appendix D Fidelity analysis

Here we present a proof of Theorem 2 which for completeness we restate below.

######  Theorem 2.

Let us consider a state $\rho$ and a graph state $\ket{G}$ that cannot be
generated in an LOSR quantum network with bipartite sources. Moreover, let
$q=|\mathcal{N}_{1}\cap\mathcal{N}_{2}|+1$ for graphs $G$ that fulfil (10) and
$q=1$ in other cases. If

$F(\rho,\ket{G})>1-\frac{1}{8}\left(\beta^{2}+2\gamma-\beta\sqrt{\beta^{2}+4\gamma}\right),$
(97)

where $\beta=2q-1$ and $\gamma=(d-\sqrt{d})/(d-1)$, then $\rho$ cannot be
generated in an LOSR quantum network with bipartite sources.

###### Proof.

Recall the definition of the fidelity $F(\rho,\sigma)$ between two states,
where one of the states is a pure state $\sigma=\outerproduct{\psi}{\psi}$:

$\displaystyle
F(\rho,\outerproduct{\psi}{\psi})=\expectationvalue{\rho}{\psi}.$ (98)

Rewriting a state $\rho$ in an orthogonal basis that contains $\ket{\psi}$ and
diagonalising the subspace orthogonal to $\ket{\psi}$, one gets

$\displaystyle\begin{split}\rho&=(1-\delta)\outerproduct{\psi}{\psi}+\sum_{i=1}^{d}c_{i}\outerproduct{f_{i}}{f_{i}}\\\
&+\sum_{j=1}^{d}(a_{0,j}\outerproduct{\psi}{f_{j}}+a_{0,j}^{*}\outerproduct{f_{j}}{\psi}),\end{split}$
(99)

where $\sum_{i=1}^{d}c_{i}=\delta$, so that $\tr(\rho)=1$. Note, that this is
always possible, since $\rho$ is Hermitian and thus so is every principal
submatrix of $\rho$. This then yields

$\displaystyle F(\rho,\outerproduct{\psi}{\psi})=1-\delta,$ (100)

and so we can express every state with fidelity $1-\delta$ with respect to a
graph state $\ket{\psi}=\ket{G}$ in the form of Eq. (99).

In order to find our desired bound on the fidelity of $\rho$ we will need two
facts. First, given a stabilizing operator $s$ of the graph state $\ket{G}$,
we have

$\displaystyle\begin{split}\absolutevalue{\expectationvalue{\mathbb{1}-s}_{\rho}}&=\Big{|}1-(1-\delta)\expectationvalue{s}_{\ket{G}}\\\
&-\sum_{i}\tr(c_{i}s\outerproduct{f_{i}}{f_{i}})\\\
&-\sum_{j}\tr(a_{0,j}s\outerproduct{G}{f_{i}}+a_{0,j}^{*}\outerproduct{f_{i}}{G}s)\Big{|}\\\
&\leq\delta+\sum_{i}c_{i}=2\delta.\end{split}$ (101)

Second, given two unitary operators $s_{1}$ and $s_{2}$ such that
$\absolutevalue{\expectationvalue{\mathbb{1}-s_{1}}}\leqslant\mu,\absolutevalue{\expectationvalue{\mathbb{1}-s_{2}}}\leqslant\nu$,
and $\mu\leqslant\nu$ the following holds true:

$\displaystyle\begin{split}&\absolutevalue{\expectationvalue{\mathbb{1}-s_{1}s_{2}}}=\absolutevalue{\expectationvalue{(\mathbb{1}-s_{1})s_{2}+\mathbb{1}-s_{2}}}\\\
&\leq\absolutevalue{\sqrt{\expectationvalue{(\mathbb{1}-s_{1})(\mathbb{1}-s_{1}^{\dagger})}\expectationvalue{s_{2}^{\dagger}s_{2}}}}+\absolutevalue{\expectationvalue{\mathbb{1}-s_{2}}}\\\
&\leq\absolutevalue{\sqrt{\expectationvalue{2\mathbb{1}-s_{1}-s_{1}^{\dagger}}}}+\nu\\\
&\leq\sqrt{2\mu}+\nu,\end{split}$ (102)

where we have used the triangle inequality and the Cauchy-Schwarz inequality.

The next step is to assess how such a deviation from a unit expected value
propagates in the reasoning of Theorem 1. As the proof of Theorem 1 is divided
into three parts, we have to consider them separately.

We begin with Part 1 of the proof of Theorem 1. Unlike in the proof of Theorem
1,, here we are forced to start from the "end" and consider the inflation
$\mathcal{I}_{q}^{1}$ first. From Eq. (101) it follows that

$\displaystyle|\langle\mathbb{1}-g_{1}\rangle_{\mathcal{I}_{q}^{1}}|\leqslant
2\delta,\qquad|\langle\mathbb{1}-g_{i}^{l}\rangle_{\mathcal{I}_{q}^{1}}|\leqslant
2\delta,$ (103)

where we assume that Eq. (56) holds true for $n\in T_{q-1}$. The case when Eq.
(57) is true gives the same result, and so for simplicity we will only focus
on Eq. (56).

From Eq. (LABEL:eq:propagation) it follows that

$|\langle\mathbb{1}-g_{1}g_{i}^{l}\rangle_{\mathcal{I}_{q}^{1}}|\leqslant
2\sqrt{\delta}+2\delta.$ (104)

From the proof of Theorem 1 we have that

$\langle\mathbb{1}-g_{1}g_{i}^{l}\rangle_{\mathcal{I}_{q}^{1}}=\langle\mathbb{1}-g_{1}g_{i}^{l}\rangle_{\mathcal{I}_{q-1}^{1}},$
(105)

and so we also have

$|\langle\mathbb{1}-g_{1}g_{i}^{l}\rangle_{\mathcal{I}_{q-1}^{1}}|\leqslant
2\sqrt{\delta}+2\delta.$ (106)

For inflation $\mathcal{I}_{q-1}^{1}$ we also have

$|\langle\mathbb{1}-g_{i}^{-l}\rangle_{\mathcal{I}_{q-1}^{1}}|\leqslant
2\delta.$ (107)

We can again use Eq. (LABEL:eq:propagation) for $s_{1}=g_{i}^{-l}$ and
$s_{2}=g_{1}g_{i}^{l}$ which yields

$|\langle\mathbb{1}-g_{1}\rangle_{\mathcal{I}_{q-1}^{1}}|\leqslant
4\sqrt{\delta}+2\delta.$ (108)

Applying this procedure $q-1$ times, where
$q=|\mathcal{N}_{1}\cap\mathcal{N}_{2}|+1$, gives us

$\displaystyle\absolutevalue{\expectationvalue{\mathbb{1}-\tilde{g}_{1}}_{\mathcal{I}_{0}^{1}}}$
$\displaystyle\leqslant 4(q-1)\sqrt{\delta}+2\delta,$ (109)

where $\tilde{g}_{1}=X_{1}Z_{2^{\prime}}Z_{N_{1}\setminus\\{2\\}}$. As this
proof can be performed for any power $k\in\\{1,\dots,d-1\\}$ we actually have

$\displaystyle\absolutevalue{\expectationvalue{\mathbb{1}-\tilde{g}_{1}^{k}}_{\mathcal{I}_{0}^{1}}}$
$\displaystyle\leqslant 4(q-1)\sqrt{\delta}+2\delta.$ (110)

Similarly, one can show that

$\absolutevalue{\expectationvalue{\mathbb{1}-g_{2}^{k}}_{\mathcal{I}_{0}^{1}}}\leqslant
2\sqrt{\delta}+2\delta.$ (111)

Figure 4: A star graph with the central node $1$. The edges can have any
weight $\Gamma_{1,j}\in\\{1,\ldots,d-1\\}$. This graph represents a graph
state with a relatively good fidelity bound.

We can now use the above inequalities to find for which values of $\delta$ one
still breaks the bounds of Lemma 1:

$\displaystyle\begin{split}2(d-1)-&\absolutevalue{\sum_{k=1}^{d-1}\expectationvalue{\tilde{g}_{1}^{k}}_{\mathcal{I}_{0}^{1}}+\expectationvalue{g_{2}^{k}}_{\mathcal{I}_{0}^{1}}}\\\
&\leq\absolutevalue{\sum_{k=1}^{d-1}\expectationvalue{\mathbb{1}-\tilde{g}_{1}^{k}}_{\mathcal{I}_{0}^{1}}+\expectationvalue{\mathbb{1}-g_{2}^{k}}_{\mathcal{I}_{0}^{1}}}\\\
&\leq 2(d-1)\left[(2q-1)\sqrt{\delta}+2\delta\right],\end{split}$ (112)

so that

$\absolutevalue{\sum_{k=1}^{d-1}\expectationvalue{\tilde{g}_{1}^{k}}_{\mathcal{I}_{0}^{1}}+\expectationvalue{g_{2}^{k}}_{\mathcal{I}_{0}^{1}}}\\\
\geq 2(d-1)\left[1-(2q-1)\sqrt{\delta}-2\delta\right].$ (113)

Notice, that the $k=0$ terms in the inequality of Lemma 1 always give exactly
one which can be subtracted from both sides of an inequality. Hence, the bound
of $d+\sqrt{d}-2$ is violated if

$\displaystyle(2q-1)\sqrt{\delta}+2\delta<\frac{d-\sqrt{d}}{2(d-1)}.$ (114)

Solving this inequality yields

$\delta<\frac{1}{8}\left(\beta^{2}+2\gamma-\beta\sqrt{\beta^{2}+4\gamma}\right),$
(115)

where $\beta=2q-1$ and $\gamma=(d-\sqrt{d})/(d-1)$.

As for Part 2 and Part 3 of the proof of Theorem 1, the derivation of the
fidelity bound is relatively simple as compared to the case of Part 1, and so
we will only show the result. For both Part 2 and Part 3 the inequality is
violated if

$(\sqrt{\delta}+2\delta)<\frac{d-\sqrt{d}}{2(d-1)},$ (116)

which yields

$\delta<\frac{1}{8}(1+2\gamma-\sqrt{1+4\gamma}),$ (117)

where $\gamma=(d-\sqrt{d})/(d-1)$. Notice, that this bound corresponds to the
bound (115) for $q=1$, and so the case where
$\mathcal{N}_{1}\cap\mathcal{N}_{2}=\emptyset$. Coincidentally, the left hand
side of Eq. (115) decreases with increasing $q$, and so Eq. (117) is also an
optimal case of Eq. (115). ∎

One of the examples of a graph state bounded by Eq. (117) is a star graph
state presented on Fig. 4. Since we have
$\mathcal{N}_{1}\cap\mathcal{N}_{2}=\emptyset$, then clearly this graph
corresponds to the first case of Lemma 4 for which $q=1$. Substituting $d=3$
yields $\delta<0.0484$, while for $d\to\infty$ one gets
$\delta<(3-\sqrt{5})/8\approx 0.0955$.

## References

  * Lo  _et al._ (2014) H.-K. Lo, M. Curty, and K. Tamaki, Nature Photonics 8, 595 (2014).
  * Liao  _et al._ (2017) S.-K. Liao, W.-Q. Cai, W.-Y. Liu, L. Zhang, Y. Li, J.-G. Ren, _et al._ , Nature 549, 43 (2017).
  * Tang  _et al._ (2014) Y.-L. Tang, H.-L. Yin, S.-J. Chen, Y. Liu, W.-J. Zhang, X. Jiang, _et al._ , Physical Review Letters 113, 190501 (2014).
  * Kómár  _et al._ (2014) P. Kómár, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin, Nature Physics 10, 582 (2014).
  * Parekh  _et al._ (2021) R. Parekh, A. Ricciardi, A. Darwish, and S. DiAdamo, “Quantum algorithms and simulation for parallel and distributed quantum computing,” (2021), arXiv:2106.06841 .
  * Kimble (2008) H. J. Kimble, Nature 453, 1023 (2008).
  * Wehner  _et al._ (2018) S. Wehner, D. Elkouss, and R. Hanson, Science 362, 303 (2018).
  * Wang  _et al._ (2010) S. Wang, W. Chen, Z.-Q. Yin, Y. Zhang, T. Zhang, H.-W. Li, _et al._ , Optics Letters 35, 2454 (2010).
  * Sasaki  _et al._ (2011) M. Sasaki, M. Fujiwara, H. Ishizuka, W. Klaus, K. Wakui, M. Takeoka, _et al._ , Optics Express 19, 10387 (2011).
  * Fröhlich  _et al._ (2013) B. Fröhlich, J. F. Dynes, M. Lucamarini, A. W. Sharpe, Z. Yuan, and A. J. Shields, Nature 501, 69 (2013).
  * Liao  _et al._ (2018) S.-K. Liao, W.-Q. Cai, J. Handsteiner, B. Liu, J. Yin, L. Zhang, _et al._ , Physical Review Letters 120, 030501 (2018).
  * Yin  _et al._ (2020) J. Yin, Y.-H. Li, S.-K. Liao, M. Yang, Y. Cao, L. Zhang, _et al._ , Nature 582, 501 (2020).
  * Mao  _et al._ (2022) Y.-L. Mao, Z.-D. Li, S. Yu, and J. Fan, “Test of genuine multipartite nonlocality in network,” (2022), arXiv:2201.12753 [quant-ph] .
  * Navascués  _et al._ (2020) M. Navascués, E. Wolfe, D. Rosset, and A. Pozas-Kerstjens, Physical Review Letters 125, 240505 (2020).
  * Coiteux-Roy  _et al._ (2021) X. Coiteux-Roy, E. Wolfe, and M.-O. Renou, Physical Review A 104, 052207 (2021).
  * Hansenne  _et al._ (2022) K. Hansenne, Z.-P. Xu, T. Kraft, and O. Gühne, Nature Communications 13, 496 (2022).
  * Luo (2021) M.-X. Luo, Advanced Quantum Technologies 4, 2000123 (2021).
  * Greenberger  _et al._ (1989) D. M. Greenberger, M. A. Horne, and A. Zeilinger, “Going beyond Bell’s theorem,” in  _Bell’s Theorem, Quantum Theory and Conceptions of the Universe_, edited by M. Kafatos (Springer Netherlands, Dordrecht, 1989) pp. 69–72.
  * Briegel and Raussendorf (2001) H. J. Briegel and R. Raussendorf, Physical Review Letters 86, 910 (2001).
  * Helwig (2013) W. Helwig, “Absolutely maximally entangled qudit graph states,” (2013), arxiv:1306.2879 [quant-ph] .
  * Raussendorf and Briegel (2001) R. Raussendorf and H. J. Briegel, Physical Review Letters 86, 5188 (2001).
  * Briegel  _et al._ (2009) H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. V. den Nest, Nature Physics 5, 19 (2009).
  * Yao  _et al._ (2012) X.-C. Yao, T.-X. Wang, H.-Z. Chen, W.-B. Gao, A. G. Fowler, R. Raussendorf, _et al._ , Nature 482, 489 (2012).
  * Hillery  _et al._ (1999) M. Hillery, V. Bužek, and A. Berthiaume, Physical Review A 59, 1829 (1999).
  * Tóth and Apellaniz (2014) G. Tóth and I. Apellaniz, Journal of Physics A: Mathematical and Theoretical 47, 424006 (2014).
  * Kraft  _et al._ (2021) T. Kraft, S. Designolle, C. Ritz, N. Brunner, O. Gühne, and M. Huber, Physical Review A 103, L060401 (2021).
  * Wolfe  _et al._ (2019) E. Wolfe, R. W. Spekkens, and T. Fritz, Journal of Causal Inference 7, 20170020 (2019).
  * Wolfe  _et al._ (2021) E. Wolfe, A. Pozas-Kerstjens, M. Grinberg, D. Rosset, A. Acín, and M. Navascués, Physical Review X 11, 021043 (2021).
  * Hein  _et al._ (2006) M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. V. den Nest, and H. J. Briegel, “Entanglement in graph states and its applications,” (2006), arXiv:quant-ph/0602096 [quant-ph] .
  * Van den Nest  _et al._ (2004) M. Van den Nest, J. Dehaene, and B. De Moor, Physical Review A 69, 022316 (2004).
  * Bahramgiri and Beigi (2007) M. Bahramgiri and S. Beigi, “Graph states under the action of local clifford group in non-binary case,” (2007), arXiv:quant-ph/0610267 .
  * Wang  _et al._ (2022) Y.-X. Wang, Z.-P. Xu, and O. Gühne, “Quantum networks cannot generate graph states with high fidelity,” (2022), arXiv:2208.xxxxx .
  * Kaniewski  _et al._ (2019) J. Kaniewski, I. Šupić, J. Tura, F. Baccari, A. Salavrakos, and R. Augusiak, Quantum 3, 198 (2019).