# The sudden death of quantum advantage in correlation generations

Weixiao Sun1 These authors contributed equally to this work. Fuchuan Wei2,3
These authors contributed equally to this work. Yuguo Shao2,3 Zhaohui Wei2,4,
<EMAIL_ADDRESS>1Institute for Interdisciplinary Information Sciences,
Tsinghua University, Beijing 100084, China
2Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China
3Department of Mathematics, Tsinghua University, Beijing 100084, China
4Yanqi Lake Beijing Institute of Mathematical Sciences and Applications,
Beijing 101407, China

###### Abstract

As quantum error corrections still cannot be realized physically, quantum
noise is the most profound obstacle to the implementations of large-scale
quantum algorithms or quantum schemes. It has been well-known that if a
quantum computer suffers from too strong quantum noise, its running can be
easily simulated by a classical computer, making the quantum advantage
impossible. Generally speaking, however, the dynamical process that how
quantum noise of varying strengths from 0 to a fatal level impacts and
destroys quantum advantage has not been understood well. Undoubtedly,
achieving this will be extremely valuable for us to understand the power of
noisy intermediate-scale quantum computers. Meanwhile, correlation generation
is a precious theoretical model of information processing tasks in which the
quantum advantage can be precisely quantified. Here we show that this model
also provides us a valuable insight into understanding the impact of noise on
quantum advantage. Particularly, we will rigorously prove that when the
strength of quantum noise continuously goes up from 0, the quantum advantage
gradually declines, and eventually fades away completely. Surprisingly, in
some cases we observe an unexpected phenomenon we call the sudden death of the
quantum advantage, i.e., when the strength of quantum noise exceeds a certain
point, the quantum advantage disappears suddenly from a non-negligible level.
This interesting phenomenon reveals the tremendous harm of noise to quantum
information processing tasks from a new viewpoint.

##  I Introduction

Quantum noise is the major obstacle in building large-scale quantum computers.
Although remarkable progresses on their physical implementations have been
made arute2019quantum ; wu2021strong ; zhu2022quantum ; zhong2020quantum ;
zhong2021phase , we still do not have enough computational resources to
perform quantum error corrections, which are believed to be the ultimate
approach to fight against quantum noise. As a result, for now we can only work
with the so-called noisy intermediate-scale quantum (NISQ) computers
preskill2018quantum ; bharti2022noisy ; chen2022complexity , which are usually
based on short-depth quantum circuits that do not involve any quantum error
corrections. In recent years, in order to show that NISQ computers can
efficiently solve computational problems that any classical computers cannot,
researchers have been intensively utilizing them to sample the outputs of
random quantum circuits and solve optimization problems like calculating the
ground-state energy of physically relevant Hamiltonians. To reliably exhibit
quantum advantage, one not only needs to improve the quality of quantum
hardware and mitigate experimental imperfections such that NISQ computers have
good precisions, but also needs to understand how precisely noise impacts the
computational advantage of quantum computing. In this paper, we will focus on
the second aspect.

To figure out the impact of noise on quantum advantage, we have to face two
major challenges. First, the rigorous quantum advantage is usually hard to
characterize mathematically. For example, the discovery of Shor’s algorithm
was a milestone in the developments of quantum computing, but in principle
whether it can achieve exponential speedup over the optimal classical
counterpart has not been rigorously proved or disproved shor1994algorithms ,
as the classical computational complexity of integer factorization has not
been settled. In some specific computational models such as query complexity
grover1996fast ; buhrman2002complexity , communication complexity
yao1993quantum ; brassard2003quantum , and some machine learning models
gao2018quantum ; huang2022quantum , researchers have managed to identify the
existence of quantum advantage mathematically, but this is often achieved by
roughly upper bounding the power of quantum computing and meanwhile lower
bounding that of its classical counterpart on a same task. Indeed, on most
problems it is very hard to _quantify_ quantum advantage. To look into the
impact of noise with different strengths on quantum advantage, a proper
measure for quantifying it is desirable.

Second, the influences of noise on quantum circuits are highly complicated,
and have not been understood well. In the past several years, because of the
impact of the quantum supremacy experiments based on random quantum circuits
arute2019quantum ; wu2021strong ; zhu2022quantum , a huge amount of efforts
have been devoted to analyzing the properties of noisy random quantum circuits
aaronson2017complexity ; aaronson2020classical ; boixo2018characterizing ;
dalzell2022random ; deshpande2022tight ; aharonov2023polynomial ;
cheng2023efficient ; hangleiter2023computational ; napp2022efficient ;
mishra2024classically ; aharonov2023polynomial ; dalzell2024random ;
gao2024limitations ; zhou2020limits ; pan2022solving ; yung2017can . Since
quantum advantage is certified only when a quantum computer can solve a
computational problem much more easily than its classical counterparts, a
crucial topic in these works is when sampling from the outputs of noisy random
quantum circuits can and cannot be efficiently simulated by classical
computers. For example, in Ref.aharonov2023polynomial  it was proved that in
the presence of a constant rate of noise per quantum gate, sampling from the
output distribution of a noisy random circuit can be approximately simulated
by an efficient classical algorithm, as long as the so-called anti-
concentration property is assumed aaronson2013computational . This surprising
result highlights the importance of further decreasing error rates in NISQ
computers. In Ref.dalzell2024random , strong evidence was provided to show
that under certain conditions, local errors are scrambled by random quantum
circuits and can be approximated by global white noise, justifying an
assumption that played a key role in Google’s supremacy experiment
boixo2018characterizing ; arute2019quantum . Meanwhile, when demonstrating
quantum supremacy based on random quantum circuits, a challenging issue is how
to verify the existence of quantum advantage at a reasonable amount of
experimental cost, for which several tools like the heavy-outcome generation
fidelity aaronson2017complexity  and the linear cross-entropy benchmark
arute2019quantum  have been proposed and studied gao2024limitations ;
zhou2020limits ; pan2022solving .

In addition to sampling the outputs of random quantum circuits, very recently
the quantum supremacy of NISQ computers working on optimization problems has
also been investigated stilck2021limitations ; gonzalez2022error ;
de2023limitations , and these works suggest that quantum advantage is possible
only when the error rate is extremely low. Please see
Refs.stilck2021limitations ; gonzalez2022error ; de2023limitations ;
gao2018efficient ; noh2020efficient ; ben2013quantum ; fefferman2023effect ;
mele2024noise ; wang2021noise ; shao2023simulating  for more on how noise
affects quantum computing.

Despite these encouraging progresses, however, in most cases the quantum
advantage of noisy NISQ computers can only be identified in certain small or
rough areas of the parameter spaces of quantum circuits, for example on one
side of certain transition points morvan2023phase ; ware2023sharp ;
cheng2023efficient . As a result, the dynamical process that how quantum noise
with the strength continuously increasing from 0 to a fatal level harms the
quantum advantage in a specific NISQ computer step by step, and eventually
destroys it completely, is still far from being understood well. Undoubtedly,
achieving this will be extremely important for us to develop NISQ computers
with practical quantum supremacy.

In this paper, we will focus on a simpler sampling model than sampling from
the outputs of noisy random quantum circuits, in which two separated parties,
Alice and Bob, cooperate and try to sample two separated outcomes according to
a target joint probability distribution zhang2012game ; Jain2013efficient .
This task can be fulfilled by either a quantum scheme or a classical one. In
the former, Alice and Bob can realize the sampling by locally measuring a
shared quantum seed state without any communications, and then outputting the
corresponding outcomes; in the latter, Alice and Bob can replace the shared
quantum state with a public randomness, and the other actions allowed are
local classical operations only. A crucial feature of this elegant model is
that a quantum scheme can enjoy a remarkable advantage over any classical one,
furthermore, in the noiseless case the smallest computational costs needed for
both scenarios, which are measured by the sizes of the shared quantum states
and the public randomness respectively, can be characterized exactly
zhang2012game ; Jain2013efficient . In other words, the quantum advantage in
this model can be precisely quantified. Based on this key fact, here we show
that this model also allows us to rigorously analyze the dynamical process
that how noise of continuously increasing strengths impacts the quantum
advantage. Specifically, on an arbitrary target correlation, we first define a
measure for the quantum advantage in this model, then we prove that when the
strength of noise continuously goes up from zero, the quantum advantage
gradually decreases, and eventually fades away completely. Surprisingly, we
will report an unexpected phenomenon we call the _sudden death of quantum
advantage_ , i.e., in some cases when the strength of noise reaches a certain
point, the quantum advantage disappears suddenly from a non-negligible level.
This interesting phenomenon brings us a new viewpoint to appreciate the harm
of noise in quantum information processing tasks.

##  II The Setting

Suppose two separate parties, Alice and Bob, want to sample two outcomes
$x\in[m]\equiv\\{1,2,...,m\\}$ and $y\in[n]$ respectively according to a
discrete joint probability distribution $P=[P(x,y)]_{x\in[m],y\in[n]}$, i.e.,
the probability that Alice outputs $x$ and Bob outputs $y$ is $P(x,y)$. If
this is the case, we say Alice and Bob generate $P$, and $P$ is also called a
classical correlation. We can write $P$ as an $m\times n$ nonnegative matrix
(A nonnegative matrix is a matrix with all the entries nonnegative), and
without loss of generality in the current work we assume that $m=n$ for
simplicity. When generating $P$, we suppose that any communication between
Alice and Bob is not allowed. Then if the target $P$ is not a product
distribution, that is, $\operatorname{rank}(P)>1$, they need to share some
initial resource to generate $P$. If Alice and Bob choose to generate $P$ with
a classical protocol, the initial shared resource can be another shared
classical correlation $P^{\prime}$, which is called a seed correlation. In
this case, Alice and Bob can perform local classical operations on
$P^{\prime}$ to generate $P$. Similarly, they can also generate $P$ with a
quantum protocol, in which the initial shared resource can be a shared quantum
state $\rho$ called a seed state. On this state, Alice and Bob perform proper
local positive operator-valued measurements (POVM) on $\rho$ and output the
corresponding outcomes to obtain $P$. We define the size of $P^{\prime}$ or
$\rho$ to be half of the total number of bits or qubits needed to record
$P^{\prime}$ or $\rho$, and denote it as $\operatorname{size}(P^{\prime})$ or
$\operatorname{size}(\rho)$ respectively. Please see Refs.zhang2012game ;
Jain2013efficient  for more details on this model of correlation generations.

For a given target $P$, we are concerned about the minimum value of
$\operatorname{size}(P^{\prime})$ (or $\operatorname{size}(\rho)$) for
$P^{\prime}$ (or $\rho$) that can generate $P$, which is called the classical
(quantum) correlation complexity of $P$, denoted $\mathrm{R}(P)$ (or
$\mathrm{Q}(P)$), correspondingly. It turns out that $\mathrm{R}(P)$ and
$\mathrm{Q}(P)$ have been fully characterized zhang2012game ;
Jain2013efficient . Specifically, it holds that

$\displaystyle\mathrm{R}(P)=\left\lceil\log_{2}\operatorname{rank}_{+}(P)\right\rceil$

and

$\displaystyle\mathrm{Q}(P)$
$\displaystyle=\left\lceil\log_{2}\operatorname{rank}_{\mathrm{psd}}(P)\right\rceil.$

For a nonnegative matrix $P\in\mathbb{R}_{\geq 0}^{n\times n}$,
$\operatorname{rank}_{+}(P)$ is the nonnegative rank defined to be the minimum
integer $r$ such that $P$ can be expressed as the sum of $r$ nonnegative
rank-$1$ matrices. $\operatorname{rank}_{\mathrm{psd}}(P)$ is the positive
semidefinite rank (PSD-rank) defined to be the minimum integer $r$ such that
there exist $r\times r$ positive semidefinite matrices
$C_{x},D_{y}\in\mathbb{C}^{r\times r}$ satisfying
$P(x,y)=\tr\left(C_{x}D_{y}\right)$ for all $x$ and $y$, and this
factorization is called a PSD decomposition Samuel2012linear ;
Fawzi2015psdrank . Although both of these two ranks are NP-hard to compute
vavasis2010complexity ; shitov2017complexity , this problem provides us with a
precious model on which the quantum advantage can be quantified precisely.
Indeed, it has been known that there exists such a classical correlation $P$
that $\operatorname{rank}_{+}(P)\gg\operatorname{rank}_{\mathrm{psd}}(P)$
Samuel2012linear , implying that quantum schemes can have a remarkable
advantage over classical ones in generating correlations.

In the quantum protocol, however, the states that Alice and Bob share may
suffer from noise, due to various experimental imperfections, which may affect
the above quantum advantage seriously. Analyzing this kind of affection is the
major motivation of the current paper. For simplicity, here we suppose that
all quantum noise is concentrated on the preparations and the quantum memories
for initial seed states, and assume that all the other quantum operations are
noiseless. Meanwhile, we assume that classical protocols are always noiseless.
More specifically, in a quantum protocol we assume that the seed state $\rho$
suffers from a bipartite quantum noise of the form
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, i.e., each of the two
subsystems of $\rho$ goes through a global depolarizing noise channel
$\mathcal{E}_{\lambda}$ with a strength $\lambda$, which keeps the subsystems
unchanged with probability $1-\lambda$ and replaces it with the maximally
mixed state with probability $\lambda$. We would like to point out that this
kind of noise can appear naturally in real-life quantum systems. For example,
Ref.dalzell2024random  shows that under certain conditions the overall effect
of local quantum errors in random quantum circuits can be approximated by
global white noise. For simplicity, here we assume that all the other quantum
operations are noiseless. When the strength $\lambda=0$, as mentioned a
quantum scheme for correlation generations may exhibit a remarkable quantum
advantage over its classical counterparts, while when $\lambda=1$, the initial
seed state degrades into the white noise completely, making quantum advantage
impossible (Alice and Bob can only produce a product distribution). In the
rest of the paper, we will characterize the process that as the noise strength
$\lambda$ continuously increases from $0$ to $1$, how the advantage of quantum
schemes over classical ones gradually disappears.

If a classical correlation $P$ can be generated by $\rho$ under the noise
channel $\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, we denote this
fact to be $\rho\xrightarrow{\lambda}P$. Under such a noise channel, we define
the quantum advantage in generating a classical correlation P, denoted
$\mathcal{S}_{\lambda}(P)$, as the ratio between the lowest classical cost of
generating $P$ and the smallest size of $\rho$ such that
$\rho\xrightarrow{\lambda}P$. Formally,

$\displaystyle\mathcal{S}_{\lambda}(P)=\frac{\mathrm{R}(P)}{\inf_{\rho}\textup{size}(\rho)},$

where the infimum is taken over all $\rho$ such that
$\rho\xrightarrow{\lambda}P$. It can be seen that this definition is
consistent with our intuition on quantum advantage: If
$\mathcal{S}_{\lambda}(P)$ is very large, say $10$, then the classical cost of
generating $P$ is at least $9$ times higher than that of the optimal noisy
quantum protocol that suffers from the noise channel
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$.

Before proceeding, we first analyze the quantum advantage of noiseless quantum
protocols in generating classical correlations. It has been known that for an
arbitrary classical correlation $P$, the minimum quantum seed that can
generate $P$ can always be chosen as a pure quantum state sikora2016minimum .
Then we have the following conclusion, which shows that noiseless quantum
protocols enjoy a remarkable quantum advantage in generating classical
correlations.

######  Theorem 1.

Suppose $\rho=\outerproduct{\psi}{\psi}$ is a bipartite entangled pure quantum
state on $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Then, there always exists a
family of classical correlation $\\{P_{m}\\}_{m\in\mathbb{Z}^{+}}$ such that
$\rho\xrightarrow{0}P_{m}$ for all $m$, and
$\underset{m\rightarrow\infty}{\operatorname{lim}}\mathcal{S}_{0}(P_{m})=\infty$.

The proof for Theorem 1 can be seen in Appendix A. Here we sketch the main
idea for the proof. For $m$ distinct real numbers
$\alpha_{1},\cdots,\alpha_{m}$, we define a so-called $m\times m$ Euclidean
distance matrix $\mathrm{EDM}_{m}$ by
$\mathrm{EDM}_{m}(x,y)=\frac{(\alpha_{x}-\alpha_{y})^{2}}{\sum_{ij}(\alpha_{i}-\alpha_{j})^{2}}$.
It has been known that
$\operatorname{rank}_{\mathrm{psd}}(\mathrm{EDM}_{m})=2$ and
$\operatorname{rank}_{+}(\mathrm{EDM}_{m})\geq 2\sqrt{m}-2$
Shitov2019Euclidean . Then we call $\mathrm{EDM}_{m}^{\prime}\equiv
L\cdot\mathrm{EDM}_{m}\cdot R$ a modified Euclidean distance matrix, where $L$
and $R$ are two $m\times m$ diagonal matrices with positive diagonal entries.
We can prove that for any bipartite entangled pure state $\ket{\psi}$ and any
integer $m$, $\ket{\psi}$ can always generate a class correlation $P_{m}$ such
that some submatrix of $P_{m}$ is an $m\times m$ modified Euclidean distance
matrix $\mathrm{EDM}_{m}^{\prime}$. Then it can be seen
$\mathcal{S}_{0}(P_{m})\geq\lceil\log_{2}(2\sqrt{m}-2)\rceil/\operatorname{size}(\rho)=\Omega(\log(m))$.
Since $m$ can be chosen arbitrarily, the proof is completed.

##  III The Impact of Noise on Quantum Advantage

We now move to the case of noisy quantum protocols that generate classical
correlations, and try to find out how noise affects quantum advantage. Recall
that the noise model we choose is that the global depolarizing noise channel
$\mathcal{E}_{\lambda}(\rho)=(1-\lambda)\rho+\lambda\tr(\rho)I_{d}/d$ acts
independently on the subsystems of Alice and Bob respectively, which transfers
a noiseless seed state $\sigma$ to
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma)$.

###  III.1 The case of strong noise: the destruction of reachability

Let us first consider the scenario of strong quantum noise. It turns out that
for a classical correlation $P$, if the strength of quantum noise is higher
than a certain value of $\lambda$, which we call the threshold, any quantum
protocols will fail in generating $P$. Denote
$\norm{\mathbf{s}}_{1}=\sum_{x=1}^{n}\absolutevalue{s_{x}}$ as the one-norm of
a vector $\mathbf{s}=(s_{1},\cdots,s_{n})$. For a Hilbert space $\mathcal{H}$,
denote $D(\mathcal{H})$ be the set of density operators on $\mathcal{H}$. The
following proposition can be utilized to identify this threshold. Note that if
$\sigma\xrightarrow{\lambda}P$ for some $\lambda>0$, then every entry of $P$
is positive. Thus we always assume $P\in\mathbb{R}_{>0}^{n\times n}$ below.

######  Proposition 1.

Suppose $P\in\mathbb{R}^{n\times n}_{>0}$ is a correlation and $\lambda<1$ is
a noise strength. Then there exists a dimension $d$ and a quantum state
$\sigma\in D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$ making
$\sigma\xrightarrow{\lambda}P$, if and only if there exists
$\mathbf{s}=(s_{1},\cdots,s_{n}),\mathbf{t}=(t_{1},\cdots,t_{n})\in\mathbb{R}_{>0}^{n}$
with $\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that

$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\equiv
P(x,y)-\lambda s_{x}\sum_{a}P(a,y)-\lambda
t_{y}\sum_{b}P(x,b)+\lambda^{2}s_{x}t_{y}\geq 0\ $ (1)

holds for all $x,y$.

The proof for Proposition 1 can be found in Appendix B. We sketch the main
idea of the proof here. If there exist POVMs $\\{E_{x}\\}$ and $\\{F_{y}\\}$
such that

$\displaystyle P(x,y)=$ $\displaystyle\tr(E_{x}\otimes
F_{y}\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma))$
$\displaystyle=$ $\displaystyle(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)+\lambda(1-\lambda)\frac{\tr(E_{x})}{d}\tr(F_{y}\sigma_{B})$
$\displaystyle+\lambda(1-\lambda)\tr(E_{x}\sigma_{A})\frac{\tr(F_{y})}{d}+\lambda^{2}\frac{\tr(E_{x})}{d}\frac{\tr(F_{y})}{d}.$

Take $s_{x}=\tr(E_{x})/d$ and $t_{y}=\tr(F_{y})/d$ and rearrange the terms, we
can see that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)=(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)\geq 0$. On the other hand, if Eq.(1) holds, we can first find a
noiseless quantum protocol with a seed state $\sigma^{\prime}$, and POVMs
$\\{E_{x}^{\prime}\\}$ and $\\{F_{y}^{\prime}\\}$ to generate the correlation
$\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}$. Then by
enlarging the quantum systems of Alice and Bob to allow more freedom, we can
construct a new quantum protocol that can generate $P$ exactly under the
noise.

We now show how Proposition 1 allows us to characterize the region of
$\lambda$ that a given classical correlation $P\in\mathbb{R}_{>0}^{n\times n}$
is reachable for quantum protocols. For this, we denote $\Lambda(P)$ as this
region, i.e.,

$\displaystyle\Lambda(P)=\left\\{\lambda:\text{ there exists a quantum state
}\rho\text{ such that }\rho\xrightarrow{\lambda}P\right\\}.$ (2)

For any $\lambda\in\Lambda(P)$, according to Proposition 1 there exists
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$, such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}$ defined in Eq.(1) is a nonnegative
matrix. Note that

$\displaystyle\frac{\partial\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)}{\partial\lambda}$
$\displaystyle=2\lambda s_{x}t_{y}-s_{x}\sum_{a}P(a,y)-t_{y}\sum_{b}P(x,b)$
(3)
$\displaystyle=-\frac{1}{1-\lambda}\left(s_{x}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)+t_{y}\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)\leq
0.$

Thus for any $0\leq\lambda^{\prime}\leq\lambda$ we have
$\hat{P}_{\lambda^{\prime}}^{\mathbf{s},\mathbf{t}}(x,y)\geq\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq
0$, which implies $\lambda^{\prime}\in\Lambda(P)$. Therefore, $\Lambda(P)$ is
an interval. That is, the continuous increase of $\lambda$ will destroy the
reachability of quantum protocols for $P$, which will never come back.

Proposition 1 fully characterizes the reachability of noisy quantum protocols
in generating correlations. However, for a given $P$, finding out whether
suitable $\mathbf{s}$ and $\mathbf{t}$ can be found to satisfy the conditions
in the Proposition 1 is very challenging, making it difficult to determine
whether a correlated $P$ can be generated quantumly under the noise strength
$\lambda$. Because of this, below we provide an easy-to-handle necessary
condition for the reachability of noisy quantum protocols. Specifically, for a
given classical correlation $P\in\mathbb{R}^{n\times n}_{\geq 0}$, there
exists a quantum state $\sigma\in D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$
satisfying $\sigma\xrightarrow{\lambda}P$, only if

$\displaystyle 0\leq\lambda\leq 1-\max_{\varphi\in
S_{n}}\sum_{x=1}^{n}\sqrt{\max\left\\{0,\sum_{b=1}^{n}P(x,b)\sum_{a=1}^{n}P(a,\varphi(x))-P(x,\varphi(x))\right\\}},$
(4)

where $S_{n}$ is a symmetric group of degree $n$. The proof can be found in
Appendix C.

Note that $\sum_{xy}\big{(}\sum_{b}P(x,b)\sum_{a}P(a,y)-P(x,y)\big{)}=0$. Then
if $\operatorname{rank}(P)\geq 2$, there always exist $x_{0}$ and $y_{0}$ such
that

$\displaystyle\sum_{b}P(x_{0},b)\sum_{a}P(a,y_{0})-P(x_{0},y_{0})>0.$

Thus the upper bound is always strictly less than $1$. That is to say, for any
$P$ with $\operatorname{rank}(P)\geq 2$, reachability will always be destroyed
before $\lambda$ reaches $1$.

###  III.2 The case of weak noise: the costs of noisy quantum protocols

For a given nontrivial classical correlation $P\in\mathbb{R}_{\geq 0}^{n\times
n}$ whose $\textup{rank}\geq 2$, we now focus on the interval $\Lambda(P)$,
that is, the region of $\lambda$ that $P$ is reachable for noisy quantum
protocols. In such a situation, the most important problem is how the cost of
generating $P$ increases as the noise strength grows.

We denote $\mathrm{C}_{\lambda}(P)$ as the minimal local dimension for the
seed states that can generate $P$ under the noise channel
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, i.e., the smallest number
$d$ such that there exists $\sigma\in D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$
satisfying $\sigma\xrightarrow{\lambda}P$. Then the size of the minimum seed
state can be written as $\lceil\log_{2}\mathrm{C}_{\lambda}(P)\rceil$.

Recall that the cost of the optimal noiseless quantum protocol generating $P$
can be fully characterized as

$\displaystyle\mathrm{Q}(P)$
$\displaystyle=\left\lceil\log_{2}\operatorname{rank}_{\mathrm{psd}}(P)\right\rceil,$

where $\operatorname{rank}_{\mathrm{psd}}(P)$ is the PSD-rank of $P$
Jain2013efficient . Inspired by the result above, we connect the cost of noisy
quantum protocols in generating correlations to a modified version of PSD-
rank. Specifically, we define
$\operatorname{rank}_{\textup{psd}}^{\mathcal{E}_{\lambda}}(P)$ to be the
smallest $r$ for which there exist $r\times r$ PSD matrices
$\\{C_{x}\\},\\{D_{y}\\}$ such that $P(x,y)=\tr(C_{x}D_{y})$, satisfying that
both

$\displaystyle
C_{x}-\frac{\lambda}{r}\tr(C_{x}\left(\sum_{k=1}^{n}C_{k}\right)^{-1})\sum_{k=1}^{n}C_{k}$

and

$\displaystyle
D_{y}-\frac{\lambda}{r}\tr(D_{y}\left(\sum_{k=1}^{n}D_{k}\right)^{-1})\sum_{k=1}^{n}D_{k}$

are PSD matrices. In this context, we say $\\{C_{i}\\},\\{D_{j}\\}$ is an
$\mathcal{E}_{\lambda}$-PSD factorization of $P$. Then we have that

$\displaystyle\mathrm{C}_{\lambda}(P)\leq\operatorname{rank}_{\textup{psd}}^{\mathcal{E}_{\lambda}}(P),$
(5)

which will be proved in Appendix D. Particularly, if we restrict seed states
to be pure states, the above inequality holds with equality.

Meanwhile, it turns out that Proposition 1 also helps to bound
$\mathrm{C}_{\lambda}(P)$, which allows us to obtain the following upper and
lower bounds for $\mathrm{C}_{\lambda}(P)$. For a given classical correlation
$P\in\mathbb{R}_{>0}^{n\times n}$ and $\lambda\geq 0$, if there exists
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)$ defined in Eq.(1) is
nonnegative for all $x,y$, then

$\displaystyle\mathrm{C}_{\lambda}(P)$
$\displaystyle\leq\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})\left\lceil\frac{1}{\min_{x,y}\\{s_{x},t_{y}\\}}\right\rceil,$
(6)

and

$\displaystyle\mathrm{C}_{\lambda}(P)$
$\displaystyle\geq\frac{1}{1-\lambda}\left(\inf_{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}\max_{x,y}\left\\{\frac{\sum_{b}P(x,b)}{s^{\prime}_{x}},\frac{\sum_{a}P(a,y)}{t^{\prime}_{y}}\right\\}-\lambda\right),$
(7)

where $\mathbf{s}^{\prime},\mathbf{t}^{\prime}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}^{\prime}}_{1}=\norm{\mathbf{t}^{\prime}}_{1}=1$ satifying
that $\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq 0$.
The proofs for these bounds can be found in Appendix E.

###  III.3 The decay process of quantum advantage

Now we are ready to analyze how quantum advantage is affected when the
strength of noise continuously grows up. We will demonstrate our techniques
using specific examples.

Define $A_{m}\in\mathbb{R}^{(m+1)\times(m+1)}$ to be the correlation with the
entries given by

$\displaystyle
A_{m}=\left(\begin{array}[]{cccc}\frac{(1-q)^{2}}{2}&\frac{q(1-q)}{2m}&\cdots&\frac{q(1-q)}{2m}\\\
\frac{q(1-q)}{2m}&&&\\\ \vdots&&\frac{1+q^{2}}{2}B_{m}&\\\
\frac{q(1-q)}{2m}&&&\end{array}\right),$ (12)

where $q=\frac{1}{1-k}-\sqrt{\frac{1}{(1-k)^{2}}-1}$, $k$ is a parameter, and
$B_{m}$ is an $m\times m$ correlation with the entries being

$\displaystyle
B_{m}(x,y)=\frac{1}{m^{2}}\left(1-k\cos(2\pi\frac{x-1+y-1}{m})\right)$

for $x,y\in[m]$. Note that if $0<k<1$, we have $0<q<1$. In fact, the
correlation $B_{m}$, as a matrix, is the slack matrix of two concentric
regular polygons, as shown in Fig. 1. More details about this geometric
interpretation can be found in fawzi2015positive ; gillis2012geometric , and
some mathematical properties of $A_{m}$ and $B_{m}$ can be seen in Appendix F.

Figure 1: A geometric interpretation for $B_{m}$, where $m=6$. The vertices of
the smaller solid-line polygon are labeled clockwise from $1$ to $6$, while
the edges of the bigger solid-line polygon are labeled counter-clockwise from
$1$ to $6$. The dash-line pentagon shows a geometric interpretation for the
restricted nonnegative rank of $B_{m}$.

It can be shown that in the absence of noise, $A_{m}$ has an arbitrarily large
quantum advantage when $m\rightarrow\infty$. In fact, in Appendix F we prove
that if $k>\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}$, then
$\operatorname{rank}_{+}(A_{m})>\log_{2}(m/2)$, whereas
$\operatorname{rank}_{\textup{psd}}(A_{m})\leq 3$. As a result, it indicates
that

$\displaystyle\underset{m\rightarrow\infty}{\lim}\mathcal{S}_{0}(A_{m})=\underset{m\rightarrow\infty}{\lim}\frac{\mathrm{R}(A_{m})}{\operatorname{rank}_{\textup{psd}}(A_{m})}=\infty.$
(13)

We then turn to noisy quantum protocols that generate $A_{m}$. Recall that
$\lceil\log_{2}\mathrm{C}_{\lambda}(A_{m})\rceil$ is the smallest size of a
seed state that can generate $A_{m}$ under the noise channel
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, which can be upper and
lower bounded by Eq.(6) and Eq.(7). As a result, we have the chance to
characterize the decay process of quantum advantage in generating $A_{m}$ when
$\lambda$ goes up.

######  Theorem 2.

As the noise strength $\lambda$ approaches $q$, the quantum advantage in
generating $A_{m}$ decreases gradually to $0$.

###### Proof.

Let $\lambda=q-\epsilon$, where $0<\epsilon<q$. And still use the notation

$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)=A_{m}(x,y)-\lambda
s_{x}\sum_{a=1}^{m+1}A_{m}(a,y)-\lambda
t_{y}\sum_{b=1}^{m+1}A_{m}(x,b)+\lambda^{2}s_{x}t_{y}.$

According to the Proposition 1, there exists $\rho$ such that
$\rho\xrightarrow{q-\epsilon}P$ if and only if there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{m+1}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$.

First, we prove that for any $0<\lambda<q$, $A_{m}$ can always be generated by
some quantum state. Let

$\displaystyle\mathbf{s}=\mathbf{t}=\big{(}\eta,(1-\eta)/m,(1-\eta)/m,\cdots,(1-\eta)/m\big{)},$

where
$\eta=\min\left\\{\frac{1-q}{2(q-\epsilon)},\frac{\epsilon(1+q)}{2q(q-\epsilon)}\right\\}$.
Note that $B_{m}(x,y)\geq\frac{1-k}{m^{2}}$. We have

$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(1,1)\geq$
$\displaystyle\frac{(1-q)^{2}}{2}-(q-\epsilon)\eta(1-q)\geq 0,$
$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(1,y)=$
$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,1)\geq\frac{q(1-q)}{2m}-(q-\epsilon)\eta\frac{1+q}{2m}-(q-\epsilon)\frac{1-\eta}{m}\frac{1-q}{2}\geq
0,\ 2\leq x,y\leq m+1,$
$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq$
$\displaystyle\frac{1+q^{2}}{2}\frac{1-k}{m^{2}}-2(q-\epsilon)\frac{1-\eta}{m}\frac{1+q}{2m}+(q-\epsilon)^{2}\frac{(1-\eta)^{2}}{m^{2}}$
$\displaystyle\geq$
$\displaystyle\frac{1+q^{2}}{2}\frac{1-k}{m^{2}}-2q\frac{1}{m}\frac{1+q}{2m}+q^{2}\frac{1}{m^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{m^{2}}\left(\frac{(1+q^{2})(1-k)}{2}-q\right)=0,\ 2\leq
x,y\leq m+1.$

That is, when $0<\lambda<q$,
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$ for any $x,y$, which
means there exists a quantum state $\rho$ such that
$\rho\xrightarrow{\lambda}A_{m}$.

By Eq.(6), if $\epsilon$ is small enough, we can obtain

$\displaystyle\mathrm{C}_{\lambda}(A_{m})$
$\displaystyle\leq\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})\left\lceil\frac{1}{\min_{x,y}\\{s_{x},t_{y}\\}}\right\rceil\leq
m\left\lceil\frac{2q(q-\epsilon)}{\epsilon(1+q)}\right\rceil=\mathcal{O}(\epsilon^{-1}).$

Second, we now show that when $\epsilon\rightarrow 0$, for any
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{m+1}$ satisfying
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ and
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$ for all $x,y$, we must
have $\min\\{s_{1},t_{1}\\}\rightarrow 0$. In fact, it holds that

$\displaystyle\sum_{i=2}^{m+1}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(i,1)+\sum_{j=2}^{m+1}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(1,j)$
$\displaystyle=$
$\displaystyle\sum_{i=2}^{m+1}A_{m}(i,1)-\sum_{i=2}^{m+1}\lambda
s_{i}\sum_{a=1}^{m+1}A_{m}(a,1)-\sum_{i=2}^{m+1}\lambda
t_{1}\sum_{b=1}^{m+1}A_{m}(i,b)+\sum_{i=2}^{m+1}\lambda^{2}s_{i}t_{1}$
$\displaystyle+\sum_{j=2}^{m+1}A_{m}(1,j)-\sum_{j=2}^{m+1}\lambda
s_{1}\sum_{a=1}^{m+1}A_{m}(a,j)-\sum_{j=2}^{m+1}\lambda
t_{j}\sum_{b=1}^{m+1}A_{m}(1,b)+\sum_{j=2}^{m+1}\lambda^{2}s_{1}t_{j}$
$\displaystyle=$
$\displaystyle\frac{q(1-q)}{2}-\lambda(1-s_{1})\frac{1-q}{2}-\lambda
t_{1}\frac{1+q}{2}+\lambda^{2}(1-s_{1})t_{1}+\frac{q(1-q)}{2}-\lambda
s_{1}\frac{1+q}{2}-\lambda(1-t_{1})\frac{1-q}{2}+\lambda^{2}s_{1}(1-t_{1})$
$\displaystyle\leq$
$\displaystyle\frac{q(1-q)}{2}-\lambda(1-s_{1})\frac{1-q}{2}-\lambda
t_{1}\frac{1+q}{2}+q^{2}(1-s_{1})t_{1}+\frac{q(1-q)}{2}-\lambda
s_{1}\frac{1+q}{2}-\lambda(1-t_{1})\frac{1-q}{2}+q^{2}s_{1}(1-t_{1})$
$\displaystyle=$
$\displaystyle-2q^{2}s_{1}t_{1}+\epsilon-\epsilon(1-s_{1}-t_{1})q$
$\displaystyle\leq$ $\displaystyle-2q^{2}s_{1}t_{1}+\epsilon(1+q).$

Therefore, for any $\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{m+1}$ and
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$, in order to let
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$, we must have

$\displaystyle\min\\{s_{1},t_{1}\\}\leq\sqrt{\frac{\epsilon(1+q)}{2q^{2}}}.$

Then according to Eq.(7),

$\displaystyle\mathrm{C}_{\lambda}(A_{m})$
$\displaystyle\geq\frac{1}{1-\lambda}\left(\inf_{\mathbf{s},\mathbf{t}}\max_{x,y}\left\\{\frac{\sum_{b}A_{m}(x,b)}{s_{x}},\frac{\sum_{a}A_{m}(a,y)}{t_{y}}\right\\}-\lambda\right)$
$\displaystyle\geq\frac{1}{1-\lambda}\left(\inf_{\mathbf{s},\mathbf{t}}\max\left\\{\frac{\sum_{b}A_{m}(1,b)}{s_{1}},\frac{\sum_{a}A_{m}(a,1)}{t_{1}}\right\\}-\lambda\right)$
$\displaystyle\geq\frac{1}{1-q+\epsilon}\left(\frac{1-q}{2}\sqrt{\frac{2q^{2}}{\epsilon(1+q)}}-q+\epsilon\right)=\Omega(\epsilon^{-1/2}).$

In conclusion, when $\epsilon$ is small, we have that

$\displaystyle\mathcal{S}_{\lambda}(A_{m})=\frac{\mathrm{R}(A_{m})}{\lceil\log_{2}\mathrm{C}_{\lambda}(A_{m})\rceil}=\Theta\left(\frac{1}{\log\epsilon^{-1}}\right).$

In other words, when $\lambda\rightarrow q$,
$\mathrm{C}_{\lambda}(A_{m})\rightarrow\infty$, implying that
$\mathcal{S}_{\lambda}(A_{m})\rightarrow 0$. This means that when $\lambda$
approaches $q$ from the left, although $A_{m}$ is always reachable for noisy
quantum protocols, their costs will continuously increase without bound,
implying that the noise with a strength around $q$ will completely destroy the
remarkable quantum advantage of the noiseless quantum protocol generating
$A_{m}$. ∎

###  III.4 The sudden death of quantum advantage

We have shown that $\mathcal{S}_{\lambda}(A_{m})$ decays gradually to $0$ as
the noise rate $\lambda$ grows. Surprisingly, if we instead focus on $B_{m}$,
a subcorrelation of $A_{m}$, we will observe an unexpected phenomenon: as
$\lambda$ continuously increases from $0$ and exceeds a certain point,
$\mathcal{S}_{\lambda}(B_{m})$ suddenly drops to $0$ from a non-negligible
value. We call this kind of phenomenon the sudden death of quantum advantage
in correlation generation.

######  Theorem 3.

Let $0<k<1$. For any integer $m$ and the classical correlation $B_{m}$ defined
in Eq.(12), we have

  1. 1.

$\mathcal{S}_{\lambda}(B_{m})=\Omega\left(\log\log(m)\right)$,  if
$0\leq\lambda\leq 1-\sqrt{k}$;

  2. 2.

$\mathcal{S}_{\lambda}(B_{m})=0$,  if  $\lambda>1-\sqrt{k}$.

Therefore, the quantum advantage in generating $B_{m}$ experiences sudden
death when the noise strength exceeds $\lambda=1-\sqrt{k}$.

###### Proof.

Let $\varphi(1)=1,\varphi(x)=m+2-x$. We have $B_{m}(x,\varphi(x))=(1-k)/m^{2}$
for all $x$. Then

$\displaystyle\sum_{b}B_{m}(x,b)\sum_{a}B_{m}(a,\varphi(x))-B_{m}(x,\varphi(x))=\frac{k}{m^{2}}.$

By Eq.(4), if $B_{m}$ can be generated under noise
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, we must have

$\displaystyle 0\leq\lambda\leq
1-\sum_{x=1}^{m}\sqrt{\max\left\\{0,\sum_{b}B_{m}(x,b)\sum_{a}B_{m}(a,\varphi(x))-B_{m}(x,\varphi(x))\right\\}}=1-\sqrt{k}.$

Thus for $\lambda>1-\sqrt{k}$, $B_{m}$ is not reachable for any noisy quantum
protocols, meaning that
$\mathcal{S}_{\lambda}(B_{m})=\frac{\mathrm{R}(B_{m})}{\infty}=0$.

For $0\leq\lambda\leq 1-\sqrt{k}$, we selcet the $2\times 2$ hermitian
matrices $\\{C_{x}\\}$ and $\\{D_{y}\\}$ introduced in Lemma F.1 of Appendix F
as a PSD decomposition of $B_{m}$, then it holds that

$\displaystyle
C_{x}-\frac{\lambda}{r}\tr(C_{x}\Big{(}\sum_{k=1}^{n}C_{k}\Big{)}^{-1})\sum_{k=1}^{n}C_{k}=C_{x}-\frac{\lambda}{\sqrt{2}m}I,$
$\displaystyle
D_{y}-\frac{\lambda}{r}\tr(D_{y}\Big{(}\sum_{k=1}^{n}D_{k}\Big{)}^{-1})\sum_{k=1}^{n}D_{k}=D_{y}-\frac{\lambda}{\sqrt{2}m}I.$

Note that the minimal eigenvalues of $C_{x}$ and $D_{y}$ are all
$\frac{1}{\sqrt{2}m}(1-\sqrt{k})$, which means both of
$C_{i}-\frac{\lambda}{\sqrt{2}m}I$ and $D_{j}-\frac{\lambda}{\sqrt{2}m}I$ are
PSD matrices, thus $\\{C_{x}\\}$ and $\\{D_{y}\\}$ form an
$\mathcal{E}_{\lambda}$-PSD factorization of $B_{m}$. By Eq.(5), we have

$\displaystyle\mathrm{C}_{\lambda}(B_{m})\leq\operatorname{rank}_{\textup{psd}}^{\mathcal{E}_{\lambda}}(B_{m})\leq
2.$

Since $B_{m}$ is not a product distribution, we have
$\mathrm{C}_{\lambda}(B_{m})=2$. That is, if $0\leq\lambda\leq 1-\sqrt{k}$, we
have

$\displaystyle\mathcal{S}_{\lambda}(B_{m})=\frac{\mathrm{R}(B_{m})}{\lceil\log_{2}\mathrm{C}_{\lambda}(B_{m})\rceil}=\mathrm{R}(B_{m}),$

which is a constant independent of $\lambda$. By Lemma F.1 in Appendix F, we
have $\mathrm{R}(B_{m})\geq\lceil\log_{2}\log_{2}(m/2)\rceil$, which completes
the proof. ∎

For any classical correlation $P$, when the sudden death of quantum advantage
happens to its generation, $\mathrm{C}_{\lambda}(P)$ will be upper bounded for
any $\lambda\in\Lambda(P)$, which means that
$\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{\lambda}(P)<\infty$. To figure out
when such a phenomenon occurs, we provide two equivalent conditions as below.

######  Theorem 4.

For any correlation $P\in\mathbb{R}_{>0}^{n\times n}$, the following
statements are equivalent to each other:

  1. 1.

The quantum advantage in generating $P$ experiences the sudden death when
$\lambda$ continuously goes up from $0$.

  2. 2.

$\Lambda(P)$ is a right closed interval.

  3. 3.

For any $\lambda>0$, if there exist non-negative vectors
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{\geq 0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}$ defined in Eq.(1) is a nonnegative
matrix, then $P$ can be generated quantumly under the noise channel
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$.

The proof for Theorem 4 is deferred to Appendix G. As a simple application of
this theorem, we now use it to reexamine the correlation $B_{m}$. According to
the proof for Theorem 3 we have that
$\Lambda(B_{m})=\big{[}0,1-\sqrt{k}\big{]}$, which is right-closed. Then
Theorem 4 immediately implies that the quantum advantage in generating $B_{m}$
suffers from the sudden death.

##  IV Discussion

Based on an elegant sampling model in which quantum advantage has been
identified and even quantified, we mathematically characterize the dynamical
process that noise of increasing strength gradually suppresses and even
destroys the quantum advantage. We also report a surprising phenomenon that
under the impact of noise, sudden death may happen to the quantum advantage in
this model. To our knowledge, this is the first quantum protocol that sudden
death is exhibited to quantum advantage, implying that in different quantum
information processing tasks the impact of noise may have different behaviors.
Our work suggests that, to fully understand the power of NISQ computers, we
need to make further efforts to characterize the nature of quantum noise for
different computational models of these computers, especially the quantum
circuit model.

###### Acknowledgements.

We thank Xun Gao and Zhengfeng Ji for helpful discussions, and Zhengwei Liu
for valuable comments. Weixiao Sun and Zhaohui Wei were supported in part by
the National Natural Science Foundation of China under Grant 62272259 and
Grant 62332009; and in part by Beijing Natural Science Foundation under Grant
Z220002. Fuchuan Wei and Yuguo Shao were supported by BMSTC and ACZSP (Grant
No. Z221100002722017).

## References

  * (1) Arute, F. _et al._ Quantum supremacy using a programmable superconducting processor.  _Nature_ 574, 505–510 (2019).
  * (2) Wu, Y. _et al._ Strong quantum computational advantage using a superconducting quantum processor.  _Physical review letters_ 127, 180501 (2021).
  * (3) Zhu, Q. _et al._ Quantum computational advantage via 60-qubit 24-cycle random circuit sampling.  _Science bulletin_ 67, 240–245 (2022).
  * (4) Zhong, H.-S. _et al._ Quantum computational advantage using photons.  _Science_ 370, 1460–1463 (2020).
  * (5) Zhong, H.-S. _et al._ Phase-programmable gaussian boson sampling using stimulated squeezed light.  _Physical review letters_ 127, 180502 (2021).
  * (6) Preskill, J.  Quantum computing in the nisq era and beyond.  _Quantum_ 2, 79 (2018).
  * (7) Bharti, K. _et al._ Noisy intermediate-scale quantum algorithms.  _Rev. Mod. Phys._ 94, 015004 (2022).  URL https://link.aps.org/doi/10.1103/RevModPhys.94.015004.
  * (8) Chen, S., Cotler, J., Huang, H.-Y. & Li, J.  The complexity of nisq.  _arXiv:2210.07234_ (2022).  URL https://arxiv.org/abs/2210.07234.
  * (9) Shor, P. W.  Algorithms for quantum computation: discrete logarithms and factoring.  In _Proceedings 35th annual symposium on foundations of computer science_ , 124–134 (Ieee, 1994).
  * (10) Grover, L. K.  A fast quantum mechanical algorithm for database search.  In _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , 212–219 (1996).
  * (11) Buhrman, H. & De Wolf, R.  Complexity measures and decision tree complexity: a survey.  _Theoretical Computer Science_ 288, 21–43 (2002).
  * (12) Yao, A. C.-C.  Quantum circuit complexity.  In _Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science_ , 352–361 (IEEE, 1993).
  * (13) Brassard, G.  Quantum communication complexity.  _Foundations of Physics_ 33, 1593–1616 (2003).
  * (14) Gao, X., Zhang, Z.-Y. & Duan, L.-M.  A quantum machine learning algorithm based on generative models.  _Science advances_ 4, eaat9004 (2018).
  * (15) Huang, H.-Y. _et al._ Quantum advantage in learning from experiments.  _Science_ 376, 1182–1186 (2022).
  * (16) Aaronson, S. & Chen, L.  Complexity-theoretic foundations of quantum supremacy experiments.  In _Proceedings of the 32nd Computational Complexity Conference_ , 1–67 (2017).
  * (17) Aaronson, S. & Gunn, S.  On the classical hardness of spoofing linear cross-entropy benchmarking.  _Theory of Computing_ 16, 1–8 (2020).
  * (18) Boixo, S. _et al._ Characterizing quantum supremacy in near-term devices.  _Nature Physics_ 14, 595–600 (2018).
  * (19) Dalzell, A. M., Hunter-Jones, N. & Brandao, F. G.  Random quantum circuits anticoncentrate in log depth.  _PRX Quantum_ 3, 010333 (2022).
  * (20) Deshpande, A. _et al._ Tight bounds on the convergence of noisy random circuits to the uniform distribution.  _PRX Quantum_ 3, 040329 (2022).
  * (21) Aharonov, D., Gao, X., Landau, Z., Liu, Y. & Vazirani, U.  A polynomial-time classical algorithm for noisy random circuit sampling.  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , 945–957 (2023).
  * (22) Cheng, Z. & Ippoliti, M.  Efficient sampling of noisy shallow circuits via monitored unraveling.  _PRX Quantum_ 4, 040326 (2023).
  * (23) Hangleiter, D. & Eisert, J.  Computational advantage of quantum random sampling.  _Reviews of Modern Physics_ 95, 035001 (2023).
  * (24) Napp, J. C., La Placa, R. L., Dalzell, A. M., Brandao, F. G. & Harrow, A. W.  Efficient classical simulation of random shallow 2d quantum circuits.  _Physical Review X_ 12, 021021 (2022).
  * (25) Mishra, S. D., Frías-Pérez, M. & Trivedi, R.  Classically computing performance bounds on depolarized quantum circuits.  _PRX Quantum_ 5, 020317 (2024).
  * (26) Dalzell, A. M., Hunter-Jones, N. & Brandão, F. G.  Random quantum circuits transform local noise into global white noise.  _Communications in Mathematical Physics_ 405, 78 (2024).
  * (27) Gao, X. _et al._ Limitations of linear cross-entropy as a measure for quantum advantage.  _PRX Quantum_ 5, 010334 (2024).
  * (28) Zhou, Y., Stoudenmire, E. M. & Waintal, X.  What limits the simulation of quantum computers?  _Physical Review X_ 10, 041038 (2020).
  * (29) Pan, F., Chen, K. & Zhang, P.  Solving the sampling problem of the sycamore quantum circuits.  _Physical Review Letters_ 129, 090502 (2022).
  * (30) Yung, M.-H. & Gao, X.  Can chaotic quantum circuits maintain quantum supremacy under noise?  _arXiv:1706.08913_ (2017).  URL https://arxiv.org/abs/1706.08913.
  * (31) Aaronson, S. & Arkhipov, A.  The computational complexity of linear optics.  _Theory OF Computing_ 9, 143–252 (2013).
  * (32) Stilck França, D. & Garcia-Patron, R.  Limitations of optimization algorithms on noisy quantum devices.  _Nature Physics_ 17, 1221–1227 (2021).
  * (33) González-García, G., Trivedi, R. & Cirac, J. I.  Error propagation in nisq devices for solving classical optimization problems.  _PRX Quantum_ 3, 040326 (2022).
  * (34) De Palma, G., Marvian, M., Rouzé, C. & França, D. S.  Limitations of variational quantum algorithms: A quantum optimal transport approach.  _PRX Quantum_ 4, 010309 (2023).  URL https://link.aps.org/doi/10.1103/PRXQuantum.4.010309.
  * (35) Gao, X. & Duan, L.  Efficient classical simulation of noisy quantum computation.  _arXiv:1810.03176_ (2018).  URL https://arxiv.org/abs/1810.03176.
  * (36) Noh, K., Jiang, L. & Fefferman, B.  Efficient classical simulation of noisy random quantum circuits in one dimension.  _Quantum_ 4, 318 (2020).  URL https://doi.org/10.22331/q-2020-09-11-318.
  * (37) Ben-Or, M., Gottesman, D. & Hassidim, A.  Quantum refrigerator.  _arXiv preprint arXiv:1301.1995_ (2013).
  * (38) Fefferman, B., Ghosh, S., Gullans, M., Kuroiwa, K. & Sharma, K.  Effect of non-unital noise on random circuit sampling.  _arXiv preprint arXiv:2306.16659_ (2023).
  * (39) Mele, A. A. _et al._ Noise-induced shallow circuits and absence of barren plateaus.  _arXiv preprint arXiv:2403.13927_ (2024).
  * (40) Wang, S. _et al._ Noise-induced barren plateaus in variational quantum algorithms.  _Nature Communications_ 12, 6961 (2021).  URL https://doi.org/10.1038/s41467-021-27045-6.
  * (41) Shao, Y., Wei, F., Cheng, S. & Liu, Z.  Simulating quantum mean values in noisy variational quantum algorithms: A polynomial-scale approach.  _arXiv preprint arXiv:2306.05804_ (2023).
  * (42) Morvan, A. _et al._ Phase transition in random circuit sampling.  _arXiv preprint arXiv:2304.11119_ (2023).
  * (43) Ware, B. _et al._ A sharp phase transition in linear cross-entropy benchmarking.  _arXiv preprint arXiv:2305.04954_ (2023).
  * (44) Zhang, S.  Quantum strategic game theory.  In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , ITCS ’12, 39–59 (Association for Computing Machinery, New York, NY, USA, 2012).  URL https://doi.org/10.1145/2090236.2090241.
  * (45) Jain, R., Shi, Y., Wei, Z. & Zhang, S.  Efficient protocols for generating bipartite classical distributions and quantum states.  _IEEE Transactions on Information Theory_ 59, 5171–5178 (2013).
  * (46) Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R. & de Wolf, R.  Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds.  In _Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing_ , STOC ’12, 95–106 (Association for Computing Machinery, New York, NY, USA, 2012).  URL https://doi.org/10.1145/2213977.2213988.
  * (47) Fawzi, H., Gouveia, J., Parrilo, P. A., Robinson, R. Z. & Thomas, R. R.  Positive semidefinite rank.  _Mathematical Programming_ 153, 133–177 (2015).  URL https://doi.org/10.1007/s10107-015-0922-1.
  * (48) Vavasis, S. A.  On the complexity of nonnegative matrix factorization.  _SIAM journal on optimization_ 20, 1364–1377 (2010).
  * (49) Shitov, Y.  The complexity of positive semidefinite matrix factorization.  _SIAM Journal on Optimization_ 27, 1898–1909 (2017).
  * (50) Sikora, J., Varvitsiotis, A. & Wei, Z.  Minimum dimension of a hilbert space needed to generate a quantum correlation.  _Physical Review Letters_ 117, 060401 (2016).
  * (51) Shitov, Y.  Euclidean distance matrices and separations in communication complexity theory.  _Discrete & Computational Geometry_ 61, 653–660 (2019).  URL https://doi.org/10.1007/s00454-018-9988-x.
  * (52) Fawzi, H., Gouveia, J., Parrilo, P. A., Robinson, R. Z. & Thomas, R. R.  Positive semidefinite rank.  _Mathematical Programming_ 153, 133–177 (2015).
  * (53) Gillis, N. & Glineur, F.  On the geometric interpretation of the nonnegative rank.  _Linear Algebra and its Applications_ 437, 2685–2712 (2012).
  * (54) Lin, L., Chen, Z., Lin, X. & Wei, Z.  All pure bipartite entangled states can be semi-self-tested with only one measurement setting on each party.  _arXiv preprint arXiv:2306.07755_ (2023).  URL https://arxiv.org/abs/2306.07755.
  * (55) Chen, Z., Lin, L., Lin, X., Wei, Z. & Yao, P.  The generations of classical correlations via quantum schemes.  _IEEE Transactions on Information Theory_ 70, 4160–4169 (2024).

##  Appendix A The proof for Theorem 1

######  Theorem A.1.

Suppose $\rho=\outerproduct{\psi}{\psi}$ is a bipartite entangled pure quantum
state on $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Then, there always exists a
family of classical correlation $\\{P_{m}\\}_{m\in\mathbb{Z}^{+}}$ such that
$\rho\xrightarrow{0}P_{m}$ for all $m$, and
$\underset{m\rightarrow\infty}{\operatorname{lim}}\mathcal{S}_{0}(P_{m})=\infty$.

###### Proof.

Suppose $\dim(\mathcal{H}_{A})=\dim(\mathcal{H}_{B})=d\geq 2$, the Schmidt
decomposition of $\ket{\psi}$ is

$\displaystyle\ket{\psi}=\sum_{i=1}^{d}\sqrt{\lambda_{i}}\ket{\phi_{i}^{A}}\otimes\ket{\phi_{i}^{B}},$

where $\sqrt{\lambda_{1}}\geq\cdots\geq\sqrt{\lambda_{d}}>0$ are the non-zero
Schmidt coefficients. Denote
$\mu_{1}=\frac{\lambda_{1}}{\lambda_{1}+\lambda_{2}}$,
$\mu_{2}=\frac{\lambda_{2}}{\lambda_{1}+\lambda_{2}}$, and let

$\displaystyle\ket{\psi^{\prime}}=\sqrt{\mu_{1}}\ket{\phi_{1}^{A}}\otimes\ket{\phi_{1}^{B}}+\sqrt{\mu_{2}}\ket{\phi_{2}^{A}}\otimes\ket{\phi_{2}^{B}}.$

Take
$\Pi^{A}=\outerproduct{\phi_{1}^{A}}{\phi_{1}^{A}}+\outerproduct{\phi_{2}^{A}}{\phi_{2}^{A}}$,
$\Pi^{B}=\outerproduct{\phi_{1}^{B}}{\phi_{1}^{B}}+\outerproduct{\phi_{2}^{B}}{\phi_{2}^{B}}$
be two projectors, we have
$\Pi^{A}\otimes\Pi^{B}\ket{\psi}=\sqrt{\lambda_{1}+\lambda_{2}}\ket{\psi^{\prime}}$.

For $m$ distinct real numbers $\alpha_{1},\cdots,\alpha_{m}$, define the
$m\times m$ Euclidean distance matrix $\mathrm{EDM}_{m}$ by
$\mathrm{EDM}_{m}(x,y)=\frac{(\alpha_{x}-\alpha_{y})^{2}}{\sum_{ij}(\alpha_{i}-\alpha_{j})^{2}}$.
For arbitrary $m$, we can pick $\alpha_{1},\cdots,\alpha_{m}$ as described in
Shitov2019Euclidean , such that

  1. 1.

$\operatorname{rank}_{\mathrm{psd}}(\mathrm{EDM}_{m})=2$ and
$\operatorname{rank}_{+}(\mathrm{EDM}_{m})\geq 2\sqrt{m}-2$,

  2. 2.

$\alpha_{1}+\cdots+\alpha_{m}=0$,

  3. 3.

$\alpha_{1}$ big enough, such that
$\sum_{y=1}^{m}\mathrm{EDM}_{m}(1,y)=\frac{\sum_{y}(\alpha_{1}-\alpha_{y})^{2}}{\sum_{ij}(\alpha_{i}-\alpha_{j})^{2}}>\mu_{1}-\frac{1}{2}$.

For $x,y=1,\cdots,m$, let

$\displaystyle C_{x}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}\frac{\alpha_{x}^{2}}{\sum_{i}\alpha_{i}^{2}}&\frac{-\alpha_{x}}{\sqrt{m\sum_{i}\alpha_{i}^{2}}}\\\
\frac{-\alpha_{x}}{\sqrt{m\sum_{i}\alpha_{i}^{2}}}&\frac{1}{m}\end{array}\right),$
$\displaystyle D_{y}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}\frac{1}{m}&\frac{\alpha_{y}}{\sqrt{m\sum_{i}\alpha_{i}^{2}}}\\\
\frac{\alpha_{y}}{\sqrt{m\sum_{i}\alpha_{i}^{2}}}&\frac{\alpha_{y}^{2}}{\sum_{i}\alpha_{i}^{2}}\end{array}\right).$

By $\sum_{i}\alpha_{i}=0$, we know that
$\sum_{ij}(\alpha_{i}-\alpha_{j})^{2}=2m\sum_{i}\alpha_{i}^{2}$, thus we have
$\tr(C_{x}D_{y})=\frac{(\alpha_{x}-\alpha_{y})^{2}}{2m\sum_{i}\alpha_{i}^{2}}=\mathrm{EDM}_{m}(x,y)$.
Meanwhile, it can be verified that

$\displaystyle\sum_{x}C_{x}=\sum_{y}D_{y}=\left(\begin{array}[]{cc}\frac{1}{\sqrt{2}}&\\\
&\frac{1}{\sqrt{2}}\end{array}\right).$

Denote $r=\frac{\mu_{1}-1/2}{\sum_{y=1}^{m}\mathrm{EDM}_{m}(1,y)}$, then we
have $0\leq r<1$. Let $\mathrm{EDM}_{m}^{\prime}=L\cdot\mathrm{EDM}_{m}\cdot
R$, where

$\displaystyle L$
$\displaystyle=\operatorname{diag}\left(1+r,1,\cdots,1\right),$ $\displaystyle
R$ $\displaystyle=\operatorname{diag}\left(1-r,1,\cdots,1\right).$

Since $L$ and $R$ are diagonal matrices with diagonal elements $>0$, we have
$\operatorname{rank}_{+}(\mathrm{EDM}_{m}^{\prime})=\operatorname{rank}_{+}(\mathrm{EDM}_{m})$.
Note that

$\displaystyle\\{(1+r)C_{1},C_{2},\cdots,C_{m}\\},$ (14)
$\displaystyle\\{(1-r)D_{1},D_{2},\cdots,D_{m}\\}$

form a PSD decomposition of $\mathrm{EDM}_{m}^{\prime}$. Since
$C_{1},D_{1}\in\mathbb{C}^{2\times 2}$ are PSD matrices satisfying
$\tr(C_{1}D_{1})=\mathrm{EDM}_{m}(1,1)=0$, we know that $C_{1}$ and $D_{1}$
are two rank-$1$ projectors with $C_{1}D_{1}=0$. Thus the eigenvalues of

$\displaystyle\left((1+r)C_{1}+\sum_{x=2}^{m}C_{x}\right)\left((1-r)D_{1}+\sum_{y=2}^{m}D_{y}\right)=\left(rC_{1}+\frac{1}{\sqrt{2}}I_{2}\right)\left(-rD_{1}+\frac{1}{\sqrt{2}}I_{2}\right)=\frac{1}{2}I_{2}+\frac{r}{\sqrt{2}}(C_{1}-D_{1})$

are

$\displaystyle\frac{1}{2}+\frac{r}{\sqrt{2}}\tr(C_{1})=\frac{1}{2}+\frac{r}{\sum_{y=1}^{m}\mathrm{EDM}_{m}(1,y)}=\mu_{1},$
$\displaystyle\frac{1}{2}-\frac{r}{\sqrt{2}}\tr(D_{1})=\frac{1}{2}-\frac{r}{\sum_{y=1}^{m}\mathrm{EDM}_{m}(1,y)}=\mu_{2}.$

Denote the diagonal form of PSD factorization of $\mathrm{EDM}_{m}^{\prime}$
equivalent to Eq.(14) by $\\{C_{x}^{\prime},D_{y}^{\prime}\\}$, where by
equivalence we mean that there exists an invertible $H$ such that
$C_{x}^{\prime}=HC_{x}H^{\dagger}$ and
$D_{y}^{\prime}={(H^{\dagger})}^{-1}D_{y}H^{-1}$ (such an $H$ always exists
lin2023all ). Then we have
$\tr(C_{x}^{\prime}D_{y}^{\prime})=\mathrm{EDM}_{m}^{\prime}(x,y)$ and

$\displaystyle\sum_{x}C_{x}^{\prime}=\sum_{y}D_{y}^{\prime}=\left(\begin{array}[]{cc}\sqrt{\mu_{1}}&\\\
&\sqrt{\mu_{2}}\end{array}\right),$

which coincides with the Schmidt coefficients of $\ket{\psi^{\prime}}$. By
Theorem 2 of chen2024generation , there exist POVMs $\\{E_{x}\\}$ and
$\\{F_{y}\\}$ on $\Pi^{A}\mathcal{H}_{A}\otimes\Pi^{B}\mathcal{H}_{B}$ (That
is, $\Pi^{A}E_{x}\Pi^{A}=E_{x}$, $\Pi^{B}F_{y}\Pi^{B}=F_{y}$,
$\sum_{x}E_{x}=\Pi^{A}$, and $\sum_{y}F_{y}=\Pi^{B}$) such that
$\tr(E_{x}\otimes
F_{y}\outerproduct{\psi^{\prime}}{\psi^{\prime}})=\mathrm{EDM}_{m}^{\prime}(x,y)$.

Now consider measuring POVMs

$\displaystyle\\{E_{1},\cdots,E_{m},I-\Pi^{A}\\},$
$\displaystyle\\{F_{1},\cdots,F_{m},I-\Pi^{B}\\},$

on the two subsystems of $\outerproduct{\psi}{\psi}$ respectively. Since

$\displaystyle\tr\left(E_{x}\otimes
F_{y}\outerproduct{\psi}{\psi}\right)=(\lambda_{1}+\lambda_{2})\mathrm{EDM}_{m}^{\prime}(x,y),$
$\displaystyle\tr\left(E_{x}\otimes(I-\Pi^{B})\outerproduct{\psi}{\psi}\right)=0,$
$\displaystyle\tr\left((I-\Pi^{A})\otimes
F_{y}\outerproduct{\psi}{\psi}\right)=0,$
$\displaystyle\tr\left((I-\Pi^{A})\otimes(I-\Pi^{B})\outerproduct{\psi}{\psi}\right)=1-\lambda_{1}-\lambda_{2},$

we have generated an $(m+1)\times(m+1)$ correlation

$\displaystyle
P_{m}=\left(\begin{array}[]{cc}(\lambda_{1}+\lambda_{2})\mathrm{EDM}_{m}^{\prime}&0\\\
0&1-\lambda_{1}-\lambda_{2}\end{array}\right)$

with the seed state $\rho=\outerproduct{\psi}{\psi}$. And it holds that

$\displaystyle\operatorname{rank}_{+}(P_{m})\geq\operatorname{rank}_{+}(\mathrm{EDM}_{m}^{\prime})=\operatorname{rank}_{+}(\mathrm{EDM}_{m})\geq
2\sqrt{m}-2.$

Since $m$ can be arbitrary large, we have
$\underset{m\rightarrow\infty}{\operatorname{lim}}\mathcal{S}_{0}(P_{m})=\infty$.
∎

##  Appendix B The proof for Proposition 1

######  Proposition B.1.

Suppose $P\in\mathbb{R}^{n\times n}_{>0}$ is a correlation and $\lambda<1$ is
a noise strength. Then there exists a dimension $d$ and a quantum state
$\sigma\in D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$ making
$\sigma\xrightarrow{\lambda}P$, if and only if there exists
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that

$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\equiv
P(x,y)-\lambda s_{x}\sum_{a}P(a,y)-\lambda
t_{y}\sum_{b}P(x,b)+\lambda^{2}s_{x}t_{y}\geq 0\ $ (15)

holds for all $x,y$.

###### Proof.

$(\Rightarrow)$ Note that

$\displaystyle P(x,y)=$ $\displaystyle\tr(E_{x}\otimes
F_{y}\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma))$
$\displaystyle=$ $\displaystyle(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)+\lambda(1-\lambda)\frac{\tr(E_{x})}{d}\tr(F_{y}\sigma_{B})$
$\displaystyle+\lambda(1-\lambda)\tr(E_{x}\sigma_{A})\frac{\tr(F_{y})}{d}+\lambda^{2}\frac{\tr(E_{x})}{d}\frac{\tr(F_{y})}{d}$
$\displaystyle=$ $\displaystyle(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)+\lambda\frac{\tr(E_{x})}{d}\left(\sum_{a}P(a,y)-\lambda\frac{\tr(F_{y})}{d}\right)$
$\displaystyle+\lambda\frac{\tr(F_{y})}{d}\left(\sum_{b}P(x,b)-\lambda\frac{\tr(E_{x})}{d}\right)+\lambda^{2}\frac{\tr(E_{x})}{d}\frac{\tr(F_{y})}{d}$
$\displaystyle=$ $\displaystyle(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)+\lambda\frac{\tr(E_{x})}{d}\sum_{a}P(a,y)+\lambda\frac{\tr(F_{y})}{d}\sum_{b}P(x,b)-\lambda^{2}\frac{\tr(E_{x})}{d}\frac{\tr(F_{y})}{d},$

where $\sigma_{A}=\tr_{B}(\sigma)$ and $\sigma_{B}=\tr_{A}(\sigma)$ are the
reduced density matrices. If we can take $s_{x}=\frac{\tr(E_{x})}{d}$,
$t_{y}=\frac{\tr(F_{y})}{d}$, then

$\displaystyle P(x,y)-\lambda s_{x}\sum_{a}P(a,y)-\lambda
t_{y}\sum_{b}P(x,b)+\lambda^{2}s_{x}t_{y}=(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)\geq 0.$

With the properties of POVM, we have
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$, and
$\norm{\mathbf{s}}_{1}=\sum_{x}\frac{\tr(E_{x})}{d}=\frac{\tr(I_{d})}{d}=1$.
Similarly, it holds that $\norm{\mathbf{t}}_{1}=1$.

$(\Leftarrow)$ Denote that

$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)=P(x,y)-\lambda
s_{x}\sum_{a}P(a,y)-\lambda t_{y}\sum_{b}P(x,b)+\lambda^{2}s_{x}t_{y},$

which naturally satisfies
$\sum_{xy}\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)=1$.

Hence, $\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}$
can be regarded as a correlation. Based on the results in
Ref.Jain2013efficient , we know that there exist POVMs $\\{E_{x}^{\prime}\\}$
and $\\{F_{y}^{\prime}\\}$, and a quantum state $\sigma^{\prime}\in
D(\mathbb{C}^{d^{\prime}}\otimes\mathbb{C}^{d^{\prime}})$ such that
$\tr(E_{x}^{\prime}\otimes
F_{y}^{\prime}\sigma^{\prime})=\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)$,
where
$d^{\prime}=\operatorname{rank_{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})$.

Take $k\in\mathbb{Z}^{+}$ such that

$\displaystyle d^{\prime}ks_{x}-\tr(E_{x}^{\prime})\geq 0,$ $\displaystyle
d^{\prime}kt_{y}-\tr(F_{y}^{\prime})\geq 0,$

for all $x,y$. Denote $d=d^{\prime}k$ and
$\sigma=\outerproduct{0}{0}\otimes\sigma^{\prime}\otimes\outerproduct{0}{0}$,
where $\outerproduct{0}{0}\in D(\mathbb{C}^{k})$. Let

$\displaystyle E_{x}$ $\displaystyle=\outerproduct{0}{0}\otimes
E_{x}^{\prime}+\left(\frac{d^{\prime}ks_{x}-\tr(E_{x}^{\prime})}{k-1}\right)(I_{k}-\outerproduct{0}{0})\otimes\frac{I_{d^{\prime}}}{d^{\prime}},$
$\displaystyle F_{y}$
$\displaystyle=F_{y}^{\prime}\otimes\outerproduct{0}{0}+\left(\frac{d^{\prime}kt_{y}-\tr(F_{y}^{\prime})}{k-1}\right)\frac{I_{d^{\prime}}}{d^{\prime}}\otimes(I_{k}-\outerproduct{0}{0}),$

which are PSD matrices. Note that

$\displaystyle\sum_{x}E_{x}$
$\displaystyle=\outerproduct{0}{0}\otimes\sum_{x}E_{x}^{\prime}+\left(\frac{d^{\prime}k\sum_{x}s_{x}-\tr(\sum_{x}E_{x}^{\prime})}{k-1}\right)(I_{k}-\outerproduct{0}{0})\otimes\frac{I_{d^{\prime}}}{d^{\prime}}$
$\displaystyle=\outerproduct{0}{0}\otimes
I_{d^{\prime}}+\left(\frac{d^{\prime}k-d^{\prime}}{k-1}\right)(I_{k}-\outerproduct{0}{0})\otimes\frac{I_{d^{\prime}}}{d^{\prime}}=I_{k}\otimes
I_{d^{\prime}}=I_{d},$ $\displaystyle\sum_{y}F_{y}$
$\displaystyle=\sum_{y}F_{y}^{\prime}\otimes\outerproduct{0}{0}+\left(\frac{d^{\prime}k\sum_{b}t_{b}-\tr(\sum_{y}F_{y}^{\prime})}{k-1}\right)\frac{I_{d^{\prime}}}{d^{\prime}}\otimes(I_{k}-\outerproduct{0}{0})$
$\displaystyle=I_{d^{\prime}}\otimes\outerproduct{0}{0}+\left(\frac{d^{\prime}k-d^{\prime}}{k-1}\right)\frac{I_{d^{\prime}}}{d^{\prime}}\otimes(I_{k}-\outerproduct{0}{0})=I_{d^{\prime}}\otimes
I_{k}=I_{d},$

thus $\\{E_{x}\\}$, $\\{F_{y}\\}$ are valid POVMs. We also have

$\displaystyle\tr(E_{x}\otimes F_{y}\sigma)$
$\displaystyle=\tr(\outerproduct{0}{0}\otimes E_{x}^{\prime}\otimes
F_{y}^{\prime}\otimes\outerproduct{0}{0}\cdot\outerproduct{0}{0}\otimes\sigma^{\prime}\otimes\outerproduct{0}{0}+0+0+0)=\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y),$
$\displaystyle\tr(E_{x})$
$\displaystyle=\tr(E_{x}^{\prime})+\left(\frac{d^{\prime}ks_{x}-\tr(E_{x}^{\prime})}{k-1}\right)(k-1)=d^{\prime}ks_{x}=ds_{x},$
$\displaystyle\tr(F_{y})$
$\displaystyle=\tr(F_{y}^{\prime})+\left(\frac{d^{\prime}kt_{y}-\tr(F_{y}^{\prime})}{k-1}\right)(k-1)=d^{\prime}kt_{y}=dt_{y}.$

Finally, note that

$\displaystyle\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)$
$\displaystyle=(1-\lambda)\left(\sum_{a}P(a,y)-\lambda t_{y}\right),$
$\displaystyle\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)$
$\displaystyle=(1-\lambda)\left(\sum_{b}P(x,b)-\lambda s_{x}\right).$

Thus we have

$\displaystyle\Tr(E_{x}\otimes
F_{y}\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma))$
$\displaystyle=$ $\displaystyle(1-\lambda)^{2}\tr(E_{x}\otimes
F_{y}\sigma)+\lambda(1-\lambda)\frac{\tr(E_{x})}{d}\tr(F_{y}\sigma_{B})+\lambda(1-\lambda)\tr(E_{x}\sigma_{A})\frac{\tr(F_{y})}{d}+\lambda^{2}\frac{\tr(E_{x})}{d}\frac{\tr(F_{y})}{d}$
$\displaystyle=$
$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)+\frac{\lambda}{1-\lambda}s_{x}\left(\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\right)+\frac{\lambda}{1-\lambda}t_{y}\left(\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)+\lambda^{2}s_{x}t_{y}$
$\displaystyle=$
$\displaystyle\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)+\lambda
s_{x}\left(\sum_{a}P(a,y)-\lambda t_{y}\right)+\lambda
t_{y}\left(\sum_{b}P(x,b)-\lambda s_{x}\right)+\lambda^{2}s_{x}t_{y}=P(x,y),$

which completes the proof. ∎

##  Appendix C The proof for Eq.(4)

We restate the conclusion in Eq.(4): For a given classical correlation
$P\in\mathbb{R}^{n\times n}_{\geq 0}$, there exists a quantum state $\sigma\in
D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$ satisfying
$\sigma\xrightarrow{\lambda}P$, only if

$\displaystyle 0\leq\lambda\leq 1-\max_{\varphi\in
S_{n}}\sum_{x=1}^{n}\sqrt{\max\left\\{0,\sum_{b}P(x,b)\sum_{a}P(a,\varphi(x))-P(x,\varphi(x))\right\\}},$

where $S_{n}$ is a symmetric group of degree $n$.

###### Proof.

By Proposition 1, there exist $\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$
with $\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ satisfying that

$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,b)=P(a,b)-\lambda
s_{a}\sum_{a}P(a,b)-\lambda t_{b}\sum_{b}P(a,b)+\lambda^{2}s_{a}t_{b}\geq 0.$
(16)

Then, summing $a$ and $b$ separately yields

$\displaystyle\sum_{a}P(a,y)$
$\displaystyle=\frac{1}{1-\lambda}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)+\lambda
t_{y},$ $\displaystyle\sum_{b}P(x,b)$
$\displaystyle=\frac{1}{1-\lambda}\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)+\lambda
s_{x}.$

Thus by replacing $\sum_{a}P(a,y)$ and $\sum_{b}P(a,y)$ in Eq.(16), $P(x,y)$
can be expressed as

$\displaystyle P(x,y)$
$\displaystyle=\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)+\frac{\lambda}{1-\lambda}s_{x}\left(\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\right)+\frac{\lambda}{1-\lambda}t_{y}\left(\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)+\lambda^{2}s_{x}t_{y}$
$\displaystyle=\left(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)-\frac{1}{(1-\lambda)^{2}}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)+\left(\frac{1}{1-\lambda}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)+\lambda
t_{y}\right)\left(\frac{1}{1-\lambda}\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)+\lambda
s_{x}\right)$
$\displaystyle=\left(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)-\frac{1}{(1-\lambda)^{2}}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)+\sum_{a}P(a,y)\sum_{b}P(x,b).$

Then for all $x,y$, it holds that

$\displaystyle\frac{1}{(1-\lambda)^{2}}\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)$
$\displaystyle=\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,b)-\left(P(x,y)-\sum_{a}P(a,y)\sum_{b}P(x,b)\right)$
$\displaystyle\geq-\left(P(x,y)-\sum_{a}P(a,y)\sum_{b}P(x,b)\right).$

Note that
$\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,y)\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\geq
0$ and
$\sum_{a,b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,b)=(1-\lambda)^{2}$.
Then for any permutation $\varphi\in S_{n}$, we have

$\displaystyle 2$
$\displaystyle\geq\frac{1}{(1-\lambda)^{2}}\sum_{x}\left(\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,\varphi(x))+\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)\right)$
$\displaystyle\geq\frac{2}{(1-\lambda)^{2}}\sum_{x}\sqrt{\sum_{a}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(a,\varphi(x))\sum_{b}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,b)}$
$\displaystyle\geq
2\sum_{x}\sqrt{\max\left\\{0,-\frac{1}{(1-\lambda)^{2}}\left(P(x,\varphi(x))-\sum_{a}P(a,\varphi(x))\sum_{b}P(x,b)\right)\right\\}}$
$\displaystyle=\frac{2}{1-\lambda}\sum_{x}\sqrt{\max\left\\{0,\sum_{a}P(a,\varphi(x))\sum_{b}P(x,b)-P(x,\varphi(x))\right\\}}.$

This means that

$\displaystyle\lambda\leq
1-\sum_{x=1}^{n}\sqrt{\max\left\\{0,\sum_{b}P(x,b)\sum_{a}P(a,\varphi(x))-P(x,\varphi(x))\right\\}}.$

∎

##  Appendix D The proof for Eq.(5)

We restate the conclusion in Eq.(5): It holds that

$\displaystyle\mathrm{C}_{\lambda}(P)\leq\operatorname{rank}_{\textup{psd}}^{\mathcal{E}_{\lambda}}(P).$

###### Proof.

To show why this is the case, suppose $r\times r$ PSD matrices
$\\{C_{i}\\},\\{D_{j}\\}$ is an $\mathcal{E}_{\lambda}$-PSD factorization of
$P$. Note that $\\{C_{i}\\},\\{D_{j}\\}$ is also a PSD factorization of $P$.
We assume that $\\{\widetilde{C_{i}}\\},\\{\widetilde{D_{j}}\\}$ is a diagonal
PSD factorization equivalent to $\\{C_{i}\\},\\{D_{j}\\}$. Recall that by
equivalence we mean that there exists an invertible $H$ such that
$\widetilde{C_{i}}=HC_{i}H^{\dagger}$ and
$\widetilde{D_{j}}={(H^{\dagger})}^{-1}D_{j}H^{-1}$. It turns out that such an
$H$ always exists lin2023all . We can verify that
$\\{\widetilde{C_{i}}\\},\\{\widetilde{D_{j}}\\}$ is also an
$\mathcal{E}_{\lambda}$-PSD factorization for $P$, since
$\\{\widetilde{C_{i}}\\},\\{\widetilde{D_{j}}\\}$ is also a PSD factorization
of $P$, and

$\displaystyle\widetilde{C_{i}}-\frac{\lambda}{r}\tr(\widetilde{C_{i}}\left(\sum_{k=1}^{n}\widetilde{C_{k}}\right)^{-1})\sum_{k=1}^{n}\widetilde{C_{k}}$
$\displaystyle=$ $\displaystyle
H\left(C_{i}-\frac{\lambda}{r}\tr(HC_{i}H^{\dagger}\left(\sum_{k=1}^{n}HC_{k}H^{\dagger}\right)^{-1})\sum_{k=1}^{n}C_{k}\right)H^{\dagger}$
$\displaystyle=$ $\displaystyle
H\left(C_{i}-\frac{\lambda}{r}\tr(C_{i}\left(\sum_{k=1}^{n}C_{k}\right)^{-1})\sum_{k=1}^{n}C_{k}\right)H^{\dagger}$

is a PSD matrix (a similar conclusion holds for $\widetilde{D_{j}}$). Based on
the above discussion, without loss of generality, we can suppose
$\sum_{k}C_{k}=\sum_{k}D_{k}=\Lambda$, where
$\Lambda=\textup{diag}(\beta_{1},\dots,\beta_{r})$ is an invertible diagonal
matrix and $\tr(\Lambda^{2})=1$.

Let

$\displaystyle M_{i}$
$\displaystyle=\frac{1}{1-\lambda}\sqrt{\Lambda^{-1}}\left(C_{i}^{T}-\frac{\lambda}{r}\tr(C_{i}\Lambda^{-1})\Lambda\right)\sqrt{\Lambda^{-1}},$
$\displaystyle N_{j}$
$\displaystyle=\frac{1}{1-\lambda}\sqrt{\Lambda^{-1}}\left(D_{j}-\frac{\lambda}{r}\tr(D_{j}\Lambda^{-1})\Lambda\right)\sqrt{\Lambda^{-1}},$
$\displaystyle|\psi_{\Lambda}\rangle$
$\displaystyle=\sqrt{\Lambda}\otimes\sqrt{\Lambda}\sum_{k=1}^{r}|kk\rangle=\sum_{k=1}^{r}\beta_{k}|kk\rangle.$

We have that $\\{M_{i}\\},\\{N_{j}\\}$ are valid POVMs, and
$|\psi_{\Lambda}\rangle$ is a state. Furthermore, it holds that
$\tr(M_{i})=\tr(C_{i}\Lambda^{-1})$ and $\tr(N_{j})=\tr(D_{j}\Lambda^{-1})$.
In addition, it can be verified that
$\mathcal{E}_{\lambda}(M_{i})=\sqrt{\Lambda^{-1}}C_{i}^{T}\sqrt{\Lambda^{-1}}$
and
$\mathcal{E}_{\lambda}(N_{j})=\sqrt{\Lambda^{-1}}D_{j}\sqrt{\Lambda^{-1}}$.
Then we have that

$\displaystyle\tr(\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(|\psi_{\Lambda}\rangle\langle\psi_{\Lambda}|)M_{i}\otimes
N_{j})$ $\displaystyle=$
$\displaystyle\tr(|\psi_{\Lambda}\rangle\langle\psi_{\Lambda}|\mathcal{E}_{\lambda}(M_{i})\otimes\mathcal{E}_{\lambda}(N_{j}))$
$\displaystyle=$
$\displaystyle\tr(|\psi_{\Lambda}\rangle\langle\psi_{\Lambda}|\sqrt{\Lambda^{-1}}C_{i}^{T}\sqrt{\Lambda^{-1}}\otimes\sqrt{\Lambda^{-1}}D_{j}\sqrt{\Lambda^{-1}})$
$\displaystyle=$
$\displaystyle\tr(\sum_{k=1}^{r}|kk\rangle\sum_{k=1}^{r}\langle
kk|C_{i}^{T}\otimes D_{j})$ $\displaystyle=$ $\displaystyle\tr(C_{i}D_{j})$
$\displaystyle=$ $\displaystyle P_{ij}$

That is, $|\psi_{\Lambda}\rangle$ can generate $P$ under noise
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$, which means the minimum
local dimension of a seed state for $P$ under noise
$\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$ is no more than
$\operatorname{rank}_{\textup{psd}}^{\mathcal{E}_{\lambda}}(P)$. ∎

##  Appendix E The proofs for Eq.(6) and Eq.(7)

We restate Eq.(6) and Eq.(7): Given $P\in\mathbb{R}_{>0}^{n\times n}$ and
$\lambda\geq 0$, if there exists $\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$
with $\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$ for all $x,y$, then

$\displaystyle\mathrm{C}_{\lambda}(P)$
$\displaystyle\leq\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})\left\lceil\frac{1}{\min_{x,y}\\{s_{x},t_{y}\\}}\right\rceil,$

and

$\displaystyle\mathrm{C}_{\lambda}(P)$
$\displaystyle\geq\frac{1}{1-\lambda}\left(\inf_{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}\max_{x,y}\left\\{\frac{\sum_{b}P(x,b)}{s^{\prime}_{x}},\frac{\sum_{a}P(a,y)}{t^{\prime}_{y}}\right\\}-\lambda\right),$

where $\mathbf{s}^{\prime},\mathbf{t}^{\prime}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}^{\prime}}_{1}=\norm{\mathbf{t}^{\prime}}_{1}=1$ satisfy
$\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq 0$.

###### Proof.

(Proof of Eq.(6))

As shown in the proof for Proposition 1, if there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$ for all $x,y$, one can
find POVMs $\\{E_{x}^{\prime}\\}$ and $\\{F_{y}^{\prime}\\}$, and a quantum
state $\sigma^{\prime}\in
D(\mathbb{C}^{d^{\prime}}\otimes\mathbb{C}^{d^{\prime}})$ such that
$\tr(E_{x}^{\prime}\otimes
F_{y}^{\prime}\sigma^{\prime})=\frac{1}{(1-\lambda)^{2}}\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)$,
where
$d^{\prime}=\operatorname{rank_{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})$.

By taking $k\in\mathbb{Z}^{+}$ such that

$\displaystyle d^{\prime}ks_{x}-\tr(E_{x}^{\prime})\geq 0,$ (17)
$\displaystyle d^{\prime}kt_{y}-\tr(F_{y}^{\prime})\geq 0,$

for all $x,y$, we can construct a $d\times d$ seed state
$\sigma=\outerproduct{0}{0}\otimes\sigma^{\prime}\otimes\outerproduct{0}{0}$,
$\outerproduct{0}{0}\in D(\mathbb{C}^{k})$, and POVMs

$\displaystyle E_{x}$ $\displaystyle=\outerproduct{0}{0}\otimes
E_{x}^{\prime}+\left(\frac{d^{\prime}ks_{x}-\tr(E_{x}^{\prime})}{k-1}\right)(I_{k}-\outerproduct{0}{0})\otimes\frac{I_{d^{\prime}}}{d^{\prime}},$
$\displaystyle F_{y}$
$\displaystyle=F_{y}^{\prime}\otimes\outerproduct{0}{0}+\left(\frac{d^{\prime}kt_{y}-\tr(F_{y}^{\prime})}{k-1}\right)\frac{I_{d^{\prime}}}{d^{\prime}}\otimes(I_{k}-\outerproduct{0}{0}),$

to generate $P$, i.e., $P(x,y)=\tr(E_{x}\otimes
F_{y}\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma))$, where
$d=d^{\prime}k$.

In the above process, the dimension for the seed state is
$d=d^{\prime}k=\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})k$,
thus we have
$\mathrm{C}_{\lambda}(P)\leq\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})k$.
Actually, to ensure that Eq.(17) holds, it suffices to take

$\displaystyle
k=\Bigg{\lceil}\underset{x,y}{\max}\left\\{\frac{\tr(E_{x}^{\prime})}{\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})}\frac{1}{s_{x}},\frac{\tr(F_{y}^{\prime})}{\rank_{\textup{psd}}(\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}})}\frac{1}{t_{y}}\right\\}\Bigg{\rceil}\leq\left\lceil\frac{1}{\min_{x,y}\\{s_{x},t_{y}\\}}\right\rceil.$

(Proof of Eq.(7))

Suppose for a local dimension $d$, a quantum state $\sigma\in
D(\mathbb{C}^{d}\otimes\mathbb{C}^{d})$, and POVMs $\\{E_{x},F_{y}\\}$, it
holds that $P(x,y)=\tr(E_{x}\otimes
F_{y}\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}(\sigma))$. Let
$s_{x}=\tr(E_{x})/d$ and $t_{y}=\tr(F_{y})/d$. By Proposition 1 we have
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)$ defined in Eq.(1) is
nonnegative for all $x,y$. Denote $\sigma_{A}=\tr_{B}(\sigma)$ and
$\sigma_{B}=\tr_{A}(\sigma)$. For arbitrary $x$, we have

$\displaystyle\sum_{b}P(x,b)=\tr(E_{x}\mathcal{E}_{\lambda}(\sigma_{A}))=(1-\lambda)\tr(E_{x}\sigma_{A})+\lambda\frac{\tr(E_{x})}{d}\leq(1-\lambda)\tr(E_{x})+\lambda\frac{\tr(E_{x})}{d}=(d(1-\lambda)+\lambda)s_{x},$

thus $s_{x}\geq\frac{\sum_{b}P(x,b)}{d(1-\lambda)+\lambda}$, which leads to
$d\geq\frac{1}{1-\lambda}\left(\frac{\sum_{b}P(x,b)}{s_{x}}-\lambda\right)$.
Similarly, for arbitrary $y$, we can obtain
$d\geq\frac{1}{1-\lambda}\left(\frac{\sum_{a}P(a,y)}{t_{y}}-\lambda\right)$,
which leads to

$\displaystyle d$
$\displaystyle\geq\frac{1}{1-\lambda}\left(\max_{x,y}\left\\{\frac{\sum_{b}P(x,b)}{s_{x}},\frac{\sum_{a}P(a,y)}{t_{y}}\right\\}-\lambda\right).$
(18)

On the both sides of Eq.(18), taking infimum over all possible quantum
protocols which can generate $P$, we get

$\displaystyle\mathrm{C}_{\lambda}(P)\geq\frac{1}{1-\lambda}\left(\inf_{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}\max_{x,y}\left\\{\frac{\sum_{b}P(x,b)}{s^{\prime}_{x}},\frac{\sum_{a}P(a,y)}{t^{\prime}_{y}}\right\\}-\lambda\right).$

∎

##  Appendix F Some properties of $A_{m}$ and $B_{m}$

Recall that $A_{m}\in\mathbb{R}^{(m+1)\times(m+1)}$ is a classical correlation
with the entries given by

$\displaystyle
A_{m}=\left(\begin{array}[]{cccc}\frac{(1-q)^{2}}{2}&\frac{q(1-q)}{2m}&\cdots&\frac{q(1-q)}{2m}\\\
\frac{q(1-q)}{2m}&&&\\\ \vdots&&\frac{1+q^{2}}{2}B_{m}&\\\
\frac{q(1-q)}{2m}&&&\end{array}\right),$

where $k\in(0,1)$ is a variable,
$q=\frac{1}{1-k}-\sqrt{\frac{1}{(1-k)^{2}}-1}$, and
$B_{m}\in\mathbb{R}^{m\times m}$ is also a classical correlation given by

$\displaystyle
B_{m}(x,y)=\frac{1}{m^{2}}\left(1-k\cos(2\pi\frac{x-1+y-1}{m})\right),x,y=1,2,\cdots,m.$

As shown in Fig. 1 of the main text, $B_{m}$ represents the slack matrix
associated with two concentric regular polygons, denoted by $R_{\mathrm{out}}$
and $R_{\mathrm{in}}$ respectively. Here $R_{\mathrm{out}}$ has an inscribed
circle with a radius of 1, while $R_{\mathrm{in}}$ has a circumscribed circle
with a radius $k<1$. The vertices of $R_{\mathrm{in}}$ are positioned at the
midpoints of the sides of $R_{\mathrm{out}}$. More details about the slack
matrix can be found in fawzi2015positive .

The outer polygon can be expressed as
$R_{\mathrm{out}}=\\{v\in\mathbb{R}^{2}|a_{x}^{T}v\leq 1,x=1,\cdots,m\\}$,
where

$\displaystyle
a_{x}=\left(\cos{\frac{2(x-1)\pi}{m}},\sin{\frac{2(x-1)\pi}{m}}\right)$ (19)

is the midpoint of $x$-th edge of the large polygon. The $y$-th vertices of
the smaller polygon $R_{\mathrm{in}}$ is

$\displaystyle
b_{y}=\left(k\cos{\frac{2(y-1)\pi}{m}},-k\sin{\frac{2(y-1)\pi}{m}}\right).$
(20)

Thus the slack matrix between $R_{\mathrm{out}}$ and $R_{\mathrm{in}}$ is
$S_{B,A}=(1-a_{x}b_{y}^{T})_{xy}=\left(1-k\cos(2\pi\frac{x-1+y-1}{m})\right)_{xy=1,\cdots,m}$,
which leads to that $B_{m}=\frac{1}{m^{2}}S_{B,A}$.

######  Lemma F.1.

For $B_{m}$ defined above, we have

  1. 1.

$\operatorname{rank}_{+}(B_{m})>\log_{2}(m/2)$, when
$k>\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}$,

  2. 2.

$\operatorname{rank}_{\textup{psd}}(B_{m})=2$.

###### Proof.

(Part 1)

By the geometric interpretation of $B_{m}$ we can derive a lower bound for
$\operatorname{rank}_{+}(B_{m})$. We first show that
$\textup{rank}_{+}(B_{m})>\log_{2}l$ if
$k>\frac{\cos(\pi/l)}{\cos^{2}(\pi/m)}$.

A lower bound for $\textup{rank}_{+}(B_{m})$ is derived from
$\textup{rank}_{+}^{*}(B_{m})$, known as the restricted nonnegative rank. This
quantity represents the minimum number $k$ of vertices of a convex polygon
$T\in\mathbb{R}^{2}$ such that $R_{\mathrm{in}}\subset T\subset
R_{\mathrm{out}}$, where $R_{\mathrm{out}}$ and $R_{\mathrm{in}}$ denote the
polygons described in Eq.(19) and (20) respectively. More details can be found
in gillis2012geometric .

A necessary condition for an $l$-gon $T$ to be put between $R_{\mathrm{in}}$
and $R_{\mathrm{out}}$ is $R_{\mathrm{in}}^{C}\subset T\subset
R_{\mathrm{out}}^{C}$, where $R_{\mathrm{out}}^{C}$ denotes the circumscribed
circle of $R_{\mathrm{out}}$ with a radius of $\frac{1}{\cos{\frac{\pi}{m}}}$,
and $R_{\mathrm{in}}^{C}$ denotes the inscribed circle of $R_{\mathrm{in}}$
with a radius of $k\cos{\frac{\pi}{m}}$. Therefore, every angle of such a $T$
is at least $2\arcsin(k\cos^{2}\frac{\pi}{m})$, while the smallest angle of
any $l$-gon is at most $\pi-\frac{2\pi}{l}$. Consequently, it must hold that
$k\leq\frac{\cos(\pi/l)}{\cos^{2}(\pi/m)}$. In other words, if
$k>\frac{\cos(\pi/l)}{\cos^{2}(\pi/m)}$, no $l$-gon can be put between
$R_{\mathrm{in}}$ and $R_{\mathrm{out}}$. Thus,
$\textup{rank}_{+}^{*}(B_{m})>l$. According to Theorem 6 in
gillis2012geometric , we have that
$\rank_{+}(B_{m})\geq\log_{2}(\rank^{*}_{+}(B_{m}))>\log_{2}(l)$.

By taking $l=m/2$, it follows that
$\rank_{+}(B_{m})>\log_{2}(l)=\log_{2}(m/2)$ when
$k>\frac{\cos(\pi/l)}{\cos^{2}(\pi/m)}=\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}$,
where $\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}<1$. Thus for any $m\geq 3$, we can
always choose $k$ close enough to $1$ such that
$\rank_{+}(B_{m})>\log_{2}(m/2)$.

(Part 2)

We can take

$\displaystyle
C_{x}=\frac{1}{\sqrt{2}m}\left(\begin{array}[]{cc}1&\sqrt{k}e^{\frac{x-1}{m}2\pi
i}\\\ \sqrt{k}e^{-\frac{x-1}{m}2\pi i}&1\end{array}\right),$ (21)
$\displaystyle
D_{y}=\frac{1}{\sqrt{2}m}\left(\begin{array}[]{cc}1&-\sqrt{k}e^{-\frac{y-1}{m}2\pi
i}\\\ -\sqrt{k}e^{\frac{y-1}{m}2\pi i}&1\end{array}\right),$

where $i=\sqrt{-1}$. It is straightforward to check
$B_{m}(x,y)=\tr(C_{x}D_{y})$ for all $x,y=1,\cdots,m$, which means that
$\operatorname{rank}_{\textup{psd}}(B_{m})\leq 2$. Also note that
$\rank(B_{m})\geq 2$, thus we have that
$\operatorname{rank}_{\textup{psd}}(B_{m})=2$. ∎

Based on the properties of $B_{m}$, we can now characterize $A_{m}$
accordingly.

######  Lemma F.2.

For $A_{m}$ definced in Eq.(12), we have

  1. 1.

$\operatorname{rank}_{+}(A_{m})>\log_{2}(m/2)$, when
$k>\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}$,

  2. 2.

$\operatorname{rank}_{\textup{psd}}(A_{m})\leq 3$.

###### Proof.

(Part 1)

Since $B_{m}$ is a submatrix of $A_{m}$, we have
$\operatorname{rank}_{+}(A_{m})\geq\operatorname{rank}_{+}(B_{m})$. Meanwhile,
according to Lemma F.1, it holds that
$\operatorname{rank}_{+}(B_{m})>\log_{2}(m/2)$, if
$k>\frac{\cos(2\pi/m)}{\cos^{2}(\pi/m)}$.

(Part 2)

We take the same $\\{C_{x},D_{y}\\}$ as in Eq.(21), then let

$\displaystyle C_{1}^{\prime}$
$\displaystyle=D_{1}^{\prime}=\frac{1-q}{2\sqrt{1+q^{2}}}\left(\begin{array}[]{ccc}\sqrt{2}&&\\\
&q&\\\ &&q\end{array}\right),$ $\displaystyle C_{x}^{\prime}$
$\displaystyle=\sqrt{\frac{1+q^{2}}{2}}\left(\begin{array}[]{cc}0&\\\
&C_{x-1}\end{array}\right)\text{ for }2\leq x\leq m+1,$ $\displaystyle
D_{y}^{\prime}$
$\displaystyle=\sqrt{\frac{1+q^{2}}{2}}\left(\begin{array}[]{cc}0&\\\
&D_{y-1}\end{array}\right)\text{ for }2\leq y\leq m+1.$

We have

$\displaystyle\tr(C_{1}^{\prime}D_{1}^{\prime})$
$\displaystyle=\frac{(1-q)^{2}}{2},$
$\displaystyle\tr(C_{x}^{\prime}D_{1}^{\prime})$
$\displaystyle=\tr(C_{1}^{\prime}D_{y}^{\prime})=\frac{q(1-q)}{2m}\text{ for
}2\leq x,y\leq m+1,$ $\displaystyle\tr(C_{x}^{\prime}D_{y}^{\prime})$
$\displaystyle=\frac{1+q^{2}}{2}\tr(C_{x-1}D_{y-1})=\frac{1+q^{2}}{2}(P_{m,k})_{x-1,y-1}\text{
for }2\leq x,y\leq m+1.$

Thus $C_{x}^{\prime},D_{y}^{\prime}$ is a PSD decomposition of $A_{m}$,
implying that $\operatorname{rank}_{\textup{psd}}(A_{m})\leq 3$. ∎

##  Appendix G The mathematical characterization for sudden death

We prove the following result, which is equivalent to Theorem 4.

######  Theorem G.2.

For any correlation $P\in\mathbb{R}_{>0}^{n\times n}$, the following
statements are equivalent:

  1. 1.

$\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{\lambda}(P)=\infty$.

  2. 2.

$\Lambda(P)$ is a right open interval.

  3. 3.

There exists $\lambda>0$, such that there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{\geq 0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)$ defined in Eq.(1) is
nonnegative for all $x,y$. However, $P$ is not reachable for any quantum
protocols under noise $\mathcal{E}_{\lambda}\otimes\mathcal{E}_{\lambda}$.

###### Proof.

“$1\Rightarrow 2$”: If $\Lambda(P)$ is right closed, we choose
$\lambda_{u}=\sup\Lambda(P)\in\Lambda(P)$. Thus there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda_{u}}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$. According to
Eq.(6), $\mathrm{C}_{{\lambda_{u}}}(P)$ has an upper bound.

Since for any $\lambda\leq\lambda_{u}$, it holds that
$\mathrm{C}_{{\lambda}}(P)\leq\mathrm{C}_{{\lambda_{u}}}(P)$, i.e., Alice and
Bob can simulate strong noise with weak noise by introducing more noise. Then
we have that $\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{{\lambda}}(P)$ has an
upper bound, which contradicts with
$\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{\lambda}(P)=\infty$.

“$2\Rightarrow 3$”: Let

$\displaystyle ST_{\lambda}=\left\\{(\mathbf{s},\mathbf{t})\in\mathbb{R}_{\geq
0}^{n}\times\mathbb{R}_{\geq
0}^{n}\right|\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}\geq
0,\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1\\}.$

Note that in this definition we allow the entries of $\mathbf{s}$ and
$\mathbf{t}$ to be $0$, thus $ST_{\lambda}$ is closed and
$ST_{\lambda}\subset\left\\{(\mathbf{s},\mathbf{t})\in\mathbb{R}_{\geq
0}^{n}\times\mathbb{R}_{\geq
0}^{n}\right|\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1\\}$ which is a
compact set. And also $\forall\
0\leq\lambda\leq\lambda^{\prime}\in\Lambda(P)$, $ST_{\lambda}\supseteq
ST_{\lambda^{\prime}}\neq\emptyset$, which is directly from Eq.(3). So we have
$\bigcap_{\lambda\in\Lambda(P)}ST_{\lambda}\neq\emptyset$.

For any $\lambda\in\Lambda(P)$ and
$(\mathbf{s}^{\prime},\mathbf{t}^{\prime})\in\bigcap_{\lambda\in\Lambda(P)}ST_{\lambda}$,
we always have
$\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq 0$ for
all $x,y$. Then
$\hat{P}_{\sup\Lambda(P)}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)=\lim_{\lambda\rightarrow\sup\Lambda(P)}\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq
0$. That is, for $\lambda_{u}=\sup\Lambda(P)$, there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{\geq 0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ such that
$\hat{P}_{\lambda_{u}}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$. However, since
$\sup\Lambda(P)\notin\Lambda(P)$, there do not exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ with
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ satisfying that
$\hat{P}_{\lambda_{u}}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$.

“$3\Rightarrow 2$”: Suppose that $\lambda_{u}$ satisfies Statement 3 and
$\hat{P}_{\lambda_{u}}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)\geq 0$ for all
$x,y$, where $\mathbf{s}_{u},\mathbf{t}_{u}\in\mathbb{R}_{\geq 0}^{n}$ satisfy
$\norm{\mathbf{s}_{u}}_{1}=\norm{\mathbf{t}_{u}}_{1}=1$. We prove that for any
$\epsilon>0$, $\lambda_{u}-\epsilon\in\Lambda(P)$.

For any $x,y$, if $(\mathbf{s}_{u})_{x}=(\mathbf{t}_{u})_{y}=0$, then
$\hat{P}_{\lambda-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)=P(x,y)>0$.
And if $(\mathbf{s}_{u})_{x}=0,(\mathbf{t}_{u})_{y}>0$, we have

$\displaystyle\frac{\partial\hat{P}_{\lambda}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)}{\partial\lambda}|_{\lambda=\lambda_{u}-\epsilon}=-(\mathbf{t}_{u})_{y}\sum_{b}P(x,b)<0.$

Thus
$\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)>\hat{P}_{\lambda_{u}}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)\geq
0$. The case that $(\mathbf{s}_{u})_{x}>0$ and $(\mathbf{t}_{u})_{y}=0$ is
similiar.

Lastly, if $(\mathbf{s}_{u})_{x}>0,(\mathbf{t}_{u})_{y}>0$, then

$\displaystyle\frac{\partial\hat{P}_{\lambda}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)}{\partial\lambda}|_{\lambda=\lambda_{u}-\epsilon}=\frac{\partial\hat{P}_{\lambda}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)}{\partial\lambda}|_{\lambda=\lambda_{u}}-2\epsilon(\mathbf{s}_{u})_{x}(\mathbf{t}_{u})_{y}\leq-2\epsilon(\mathbf{s}_{u})_{x}(\mathbf{t}_{u})_{y}<0.$

Thus
$\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)>\hat{P}_{\lambda_{u}}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)\geq
0$.

In conclusion, we always have
$\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)>0$. Let
$w=\underset{x,y}{\min}\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)>0$.
Note that

$\displaystyle\left|\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)-\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\right|\leq
3\left|s_{x}-s^{\prime}_{x}\right|+3\left|t_{y}-t^{\prime}_{y}\right|$

for any
$\lambda,\mathbf{s},\mathbf{t},\mathbf{s}^{\prime},\mathbf{t}^{\prime},x,y$.
Then for any $\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ that satisfy
$\norm{\mathbf{s}-\mathbf{s}_{u}}_{2}\leq\frac{w}{6}$ and
$\norm{\mathbf{t}-\mathbf{t}_{u}}_{2}\leq\frac{w}{6}$ (such
$\mathbf{s},\mathbf{t}$ exist), we have

$\displaystyle\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s},\mathbf{t}}(x,y)\geq\hat{P}_{\lambda_{u}-\epsilon}^{\mathbf{s}_{u},\mathbf{t}_{u}}(x,y)-w\geq
0.$

Thus $\lambda_{u}-\epsilon\in\Lambda(P)$, which means
$\Lambda(P)=\left[0,\lambda_{u}\right)$.

“$2\Rightarrow 1$”: Let $\lambda_{u}=\sup\Lambda(P)$. Suppose
$\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{\lambda}(P)<d$ for some constant $d$.
Then from Eq.(3), for any $\lambda\in\Lambda(P)$, there exist
$\mathbf{s},\mathbf{t}\in\mathbb{R}_{>0}^{n}$ such that
$\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1$ and
$\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}(x,y)\geq 0$ for all $x,y$, where
$s_{x}\geq\frac{\sum_{b}P(x,b)}{d(1-\lambda)+\lambda}$ and
$t_{y}\geq\frac{\sum_{a}P(a,y)}{d(1-\lambda)+\lambda}$, as shown in Eq.(18).
Let

$\displaystyle
v=\min_{x,y}\left\\{\frac{\sum_{b}P(x,b)}{d(1-\lambda_{u})+\lambda_{u}},\frac{\sum_{a}P(a,y)}{d(1-\lambda_{u})+\lambda_{u}}\right\\}.$

We have $\mathbf{s},\mathbf{t}\in\mathbb{R}_{\geq v}^{n}$. Again let

$\displaystyle ST_{\lambda}=\left\\{(\mathbf{s},\mathbf{t})\in\mathbb{R}_{\geq
v}^{n}\times\mathbb{R}_{\geq
v}^{n}\right|\hat{P}_{\lambda}^{\mathbf{s},\mathbf{t}}\geq
0,\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1\\}.$

Note that $ST_{\lambda}$ is closed and
$ST_{\lambda}\subset\left\\{(\mathbf{s},\mathbf{t})\in\mathbb{R}_{\geq
v}^{n}\times\mathbb{R}_{\geq
v}^{n}\right|\norm{\mathbf{s}}_{1}=\norm{\mathbf{t}}_{1}=1\\}$ which is
compact. And for any $\lambda\leq\lambda^{\prime}\in\Lambda(P)$,
$ST_{\lambda}\supseteq ST_{\lambda^{\prime}}\neq\emptyset$, which is directly
from Eq.(3). So we have
$\bigcap_{\lambda\in\Lambda(P)}ST_{\lambda}\neq\emptyset$.

For any $\lambda\in\Lambda(P)$ and
$(\mathbf{s}^{\prime},\mathbf{t}^{\prime})\in\bigcap_{\lambda\in\Lambda(P)}ST_{\lambda}$,
we always have
$\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq 0$ for
all $x,y$. Then

$\hat{P}_{\lambda_{u}}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)=\hat{P}_{\sup\Lambda(P)}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)=\lim_{\lambda\rightarrow\sup\Lambda(P)}\hat{P}_{\lambda}^{\mathbf{s}^{\prime},\mathbf{t}^{\prime}}(x,y)\geq
0.$ (22)

Thus $\sup\Lambda(P)\in\Lambda(P)$, which contradicts $\Lambda(P)$ is right
open. Thus we have
$\sup_{\lambda\in\Lambda(P)}\mathrm{C}_{\lambda}(P)=\infty$. ∎