多体量子关联与通信复杂性的研究

1多体量子关联和通信复杂性Rahul Jain魏朝晖 < $PenghuiYao姚盛宇 Zhang<$摘要量子关联复杂度和量子通信复杂度的概念最近被提出来量化在单次设置中生成二分经典或量子态前者是初始共享状态σ的最小尺寸，在该尺寸上，双方的本地操作（无通信）可以生成目标状态ρ，而后者是初始不共享时所需的最小通信量在本文中，我们将这两个概念推广到多部的情况下，精确和近似的状态生成。我们的结果总结如下。1. 对于多体纯态，关联复杂性可以用系统的局部秩来完全刻画。2. 我们将矩阵的PSD秩的概念推广到张量的PSD秩，并利用它来约束生成多体经典分布的量子关联复杂性3. 对于生成多体混合量子态，通信复杂度并不总是等于关联复杂度（与二体情况相反）。但它们最多相差2倍。生成多体混合量子态与生成其最优纯化具有相同的通信复杂性。但是对于相关性，这两个任务的复杂性可能不同（尽管仍然相关小于2倍）。4. 为了近似地生成一个二部经典分布P（x，y），量子通信复杂度完全由P的近似PSD秩来刻画.近似生成多体纯态的量子关联复杂性受近似局域秩的限制。1介绍共享随机性和量子纠缠是各种分布式信息处理任务的重要资源。如何产生这些共享资源一直是最重要的问题之一，最近，人们一直关注在一次设置中产生二分经典态和量子态所需的最小共享相关和通信量[1，5，4，12，6]。在[6]最坏的情况新加坡国立大学计算机科学系和量子技术中心。电子邮件地址：rahul@comp.nus.edu.sg†新加坡南洋理工大学物理与数学科学学院和量子技术中心。电子邮件地址：weizhaohui@gmail.com新加坡国立大学量子技术中心。 电子邮件地址：phyao1985@gmail.com§香港中文大学计算机科学与工程系及理论计算机科学与通信研究所。电子邮件地址：syzhang@cse.cuhk.edu.hkarXiv：1405.6015v3 [quant-ph] 2014年721已经描述了产生相关性和量子纠缠的几种单次二分方案的成本。设置如下。假设两方Alice和Bob需要生成相关的随机变量X和Y，Alice输出X，Bob输出Y，使得（X，Y）根据目标分布P分布。如果P不是乘积分布，Alice和Bob可以通过共享初始种子分布（X′，Y′）来生成P，Alice拥有X′，Bob拥有Y′，然后每个人都在自己的部分执行本地操作该种子相关性的最小大小（X′，Y′）被定义为随机相关复杂度[12]，表示为R（P），其中二分分布的大小已知R（P）完全被表征为Rlog2rank+（P）Rank[12]，其中rank+（P）是矩阵P的非负秩，是线性代数中的一种度量，在组合优化[11]、非确定性通信复杂性[7]、代数复杂性理论[9]和许多其他领域[2]中有许多应用。当允许量子操作时，问题变得更加有趣：Alice和Bob共享一个种子量子态σ，并执行局部量子操作以生成分布式经典分布P。在这种情况下，种子量子态的最小尺寸σ被定义为量子相关复杂度，表示为QCorr（P），其中二分量子态的尺寸[ 6 ]的主要结果之一是QCorr（P）可以完全刻画为P的PSD-rank，其中rank psd（P）是P的PSD-rank，这是Fiorini等人最近提出的一个概念。 在研究最小尺寸的扩展配方的优化问题，如TSP[4]。由于rank+（P）可能比rankpsd（P）大得多，这意味着使用量子运算产生经典分布的潜在巨大优势。更一般地，目标态可以是量子态ρ，并且[6]给出了生成ρ的种子态的最小尺寸的完整特征。特别地，如果ρ是纯态，|并且允许一个近似来生成|ψ⟩ ⟨ψ|，则相关复杂度完全由以下Schmidt系数的（1 -1）2 -截止点来表征：|因此，关闭[ 1 ]中留下的可能指数差距。|ψ⟩, closing a possibly exponential gapleft in[1].上面的讨论假设Alice和Bob对共享状态执行本地操作。实际上，Alice和Bob可以通过通信来替换上面讨论的共享状态在这种情况下，经典和量子协议中用于生成目标经典分布P的最小通信量被定义为随机和量子通信复杂度，分别表示为RComm（P）和QComm（P）[12];可以类似地定义QComm（ρ）以生成量子态ρ。我们引入了相关复杂度和通信复杂度。一个有趣的事实是，当只涉及两方时，这两个度量总是相同的，这对经典和量子设置都是如此[12]。为了获取生成目标状态的最小代价，相关复杂度和通信复杂度的概念是共享状态作为资源的基本参数。特别是，当目标状态是量子时，资源是纠缠，可以说是几乎所有量子信息处理任务中最重要的共享资源。虽然两体纠缠已经被很好地理解，但多体纠缠在许多层面上都是难以捉摸的，并且已经做出了相当大的努力来从各个角度研究它。在本文中，我们将经典关联和量子纠缠产生的关联和通信复杂性的研究扩展到多体情况。我们的结果总结如下，我们希望他们可以从另一个基本的角度阐明多体纠缠。1.一个二分维数P是一个非线性矩阵x[P（x，y）]x，y，并且我们将P用于该二分维数和矩阵。31.1多体量子关联复杂度对于多体情形，量子关联复杂性和量子通信复杂性不再等价，必须分别处理我们首先考虑生成k-粒子态的量子关联复杂度.定义1. 假设k方，A1，A2，...，Ak，共享一个种子状态σ，它们的目标是通过各自对σ的自己的部分执行一些操作来生成目标状态ρ 则ρ的量子相关复杂度，记为QCorr（ρ），是σ的最小大小，使得对σ可以生成ρ。 这里，σ的大小被定义为Σkn，其中n是σ的量子比特数我我由Ai。让我们首先考虑ρ是纯态的情况。对于二分纯态|然而，Schmidt分解有助于我们表征QCorr（|QC-QCM（|但是多体纯态一般不具有施密特分解。结果表明，量子关联度是量子关联度的一个“平均值”的总和。定义2. 假设|是H1<$···<$Hk中的纯态，ρ j是|在Hj.定义边际复杂度|ψ> asM（|ψ⟩)=克j=1、、、l0g2rank（ρj）.定理1. 假设|是H1<$···<$Hk中的纯态，ρ j是|在Hj. 然后QCorr（|（1）A =A（|ψ>）。然而，对于混合量子态ρ，相关复杂性不太清楚。 在二分情况下，QCorr（ρ）恰好是最小QCorr（|在所有的净化中|[6]第六节。在多方背景下，情况不再如此。定理2. 假设ρ是NkH中的量子态。 然后我们有我.2ΣQCorr（ρ）≤r（ρ）≤2−kQCorr（ρ），其中r（ρ）是最小QCorr（|在所有的净化中|ρ的最大值我们还将证明上述定理中的两个不等式都是紧的，从而意味着：（2）求出最大值，求出最小值，求出最小值。|（中文）：|ψ⟩ purifies ρ}.当一种简单的纯量子态包含在最多的“量子态”中时，另一种极端是经典态的混合，即：经典分布。在二分情况下，生成分布P= [P（x，y）]x，y的量子相关复杂度正好是P<0.05，P<0.05。我们将在多体情况下给出一个类似的结果为此，我们需要首先将PSD秩的概念从矩阵推广到张量。类似于二部情况，k部概率分布P = [P（x1，x2，...，xk）] x1，x2，.，xk也可以看作是k维的张量。i=1i=14Σ≤≤1i，j=1X1XK2K定义3. 对于逐项非负张量P =[P（x1，.， x k）] x1，.，xk的维数，其PSD秩rank（k）（P）是最小rs.t. 存在r × r个PSD矩阵C（1），.，C（k）≥ 0，P（x，.，XPSD）=rC（1）（i，j）· · ·C（k）（i，j）。x1xk有了这个定义，我们可以根据P的PSD秩来限制P定理3. 设P =[P（x1，.， x k）] x1，.，xk是X1×···×Xk上的概率分布。然后K，日志 rank（k）（P），≤QCorr（P）≤，（k） ，2k− 2PSDklog 2秩psd（P）。1.2多体量子通信复杂性如前所述，还可以考虑玩家在开始时不共享任何内容并进行通信以生成某些目标状态的设置。通信复杂度的形式定义如下。定义4. 假设k方，A1，A2，...，Ak，最初不共享任何东西，并且旨在通过通信共同生成量子态ρ。生成ρ的量子通信复杂度，记为QComm（ρ），是在这k方之间交换的量子比特的最小数量。下面的表格显示的是用于满足以下要求的Occurrémigiónbounds，这些要求包含了纯数据的完整性。因此，M（|ψ⟩)=Kj=1log2rank（ρi）|你要去我的地盘。定理4. 假设|量子态是一种k-分纯态。然后1M（|01-02-2016刘晓波（|10 - 1|ψ>）。接下来，我们转向一般的多体量子混合态。 与量子相关复杂度不同，量子通信复杂度QComm（ρ）总是等于最小QComm（|过度净化|ρ的最大值定理5. 对于任意k-分量子态ρ，QComm（ρ）= min {QComm（|（中文）：|是ρ}的纯化。综合以上两节的结果，我们得到了一般多体量子态ρ的QCorr（ρ）与QComm（ρ）之间的关系。推论6. 对于任意k-分量子态ρ，k QComm（ρ） QCorr（ρ）2QComm（ρ）. k− 11.3近似量子相关复杂度在本节中，我们考虑通过允许近似来放松状态生成的任务毕竟，我们通常生成状态是为了以后的信息处理目的，因此如果生成的状态ρ′非常接近目标状态ρ，那么无论进一步的操作，全局或局部，都可以保持相同的精度。K25ǫǫ2ǫ−ǫ′ǫ1.3.1二部当一个很好的近似而不是精确的一代是令人满意的，共享种子状态的最小尺寸可以小于精确的一代。在[6]中，给出了近似相关复杂度的自然定义如下。定义5. 设ρ是HA <$HB中的一个二分量子态，且<$0. 定义QCorr（ρ）d=efmin{QCorr（ρ′）：ρ′∈HA<$HBanddF（ρ，ρ′）≥1−<$}因为对于任何二分态ρ，生成混合态与生成其（最佳）纯化相同[12，6]QCorr（ρ）= min {QCorr（|（中文）：|2019- 02 - 12 01：02：02 01：02 - 12 01：02|）|水净化ρ}，通过将近似值置于纯化上而不是原始目标状态来给出另一个定义也是自然的。让QCorr′（ρ）= min {QCorr（|′|2016年10月15日，中国科学院院士李国祥（|但是，|′正如我们将要证明的，这两个定义是等价的，即。，QCorr（ρ）=QCorr′（ρ）.请注意，此定义是为了分析、区分纯数据集的可执行性[16]故有“知”者，谓之“知”。|A = x，yA（x，y）|X轴|y≠ y，设矩阵A = [A（x，y）]，则min {QCorr（|2016 - 05- 2200：00：00|但是，|′其中矩阵A的近似秩秩δ（A）是矩阵A的最小数rs.t. 最大r个奇异值的平方和至少为1−δ。在 此 基 础 上 ， 我 们 得 到 了 经 典 分 布 ρ 的 特 殊 情 形 ， 即 ρ 为 经 典 分 布 P 时 ，QCorr<$（ρ）的如下特征.我们首先定义近似PSD秩和近似相关复杂度的经典状态如下。定义6.P=[p（x，y）]x，y是一个二部概率分布，其近似PSD秩为rank psd，F（P）= min {rank psd（P ′）：F（P，P ′）≥ 1 − F}。（一）其中P′是P的同一样本空间上的另一个概率分布定义7. 对于二分经典分布P = [P（x，y）] x，y，其经典态的近似量子关联复杂度为QCorrcla（P）= min {QCorr（P ′）：F（P，P ′）≥ 1 − k}，其中P是P在同一样本空间上的另一个概率分布.下面的定理说，一个经典态的最有效的近似生成总是可以通过另一个经典态来实现。此外，一个经典态的近似关联复杂度可以完全由近似PSD秩来表征。定理7. 对于任何经典态P= [P（x，y）]x，y，QCorrσ（P）= QCorrcla（P）= σ log2秩psd，σ（P）σ。6ǫǫǫi=1ǫ我ǫi=1我ǫǫ最后，对于任意量子态ρ的一般情况，我们给出了QCorr_∞（ρ）的如下特征。定理8. 设σ是HA <$HB中的任意量子态，0 <<$1<。 则QCorr（σ）=其中r是最小整数s. t。存在列数l ≥ r的矩阵{Ax}和{By}的集合，满足下列条件。1. 矩阵与σ之间的关系如下：- 是的ΣΣσ=|xx′|⊗|你好，|·tr（A <$′Ax）T（B <$′B y）。（二）X yx，x′;y，y′2. 表示任何矩阵M的第i列，|M（i），则ΣA x（i）|A x（j）=XΣBy（i）|B y（j）= 0，（3）y3.布雷尔 . Σ- 是的ΣΣi=1A x（i）|Ax（i）XBy（i）|By（i）y≥1−1，（4）1.3.2多部如在[6]中，考虑对纯目标状态的两种不同近似是很自然的，一种是用混合状态近似，另一种是用纯状态近似定义8. 设k> 0。 让|量子纯态是H1 <$H2中的k-粒子量子纯态。⊗Hk. 定义QCorr（|ψ⟩def{QCorr（ρ′）：ρ′在H1<$H2<$. ZH，则F（|ψ⟩⟨ψ|，ρ′）≥ 1 − ε}k）= mink和QCorpu re（|C=C= C（|（φ）：|φ∈H1<$H2<$.. . 2016年01月01日@上午10时30分01秒01：00|ψ⟩⟨ψ|、|φ⟩⟨φ|）≥1− 1}。我们可以看到，QCorr（ρ）和QCorrpure（ρ）是用混合函数逼近ρ的复杂度。和纯态。对于k分纯态|在H1<$H2<$··<$Hk中，设ρ i是|ψ⟩ in Hi, and r i= rank (ρ i). 表示的近似施密特秩|在这方面，separatin（A，A ）（heA=A. AA... A）asr（n），i. e. （1）A（1）A（2）A（3）A（4）A（|ψ>）。Then我们有i−i−i1i−1i+1ki ii定理9. 让|n∈ NkH 01- 02|ψ⟩)= Σk、日志r（λ），. 然后M（|QC rre（|10-12-2000|ψ>）。最后，我们考虑QCorr（|01- 02 - 2013张晓波（|ψ>）。定理10. 让|当n∈ HA1n···HAk是纯态且n> 0时，则n ∈ HA1 n···HAk是纯态. 然后01-02|01- 02 - 2016刘晓波（|01 - 02 - 2016刘晓波（|ψ>）。2卡茨72k− 28def+=HHBH2预赛在本文中，我们考虑多部系统。如果一个系统有k个参与方，我们通常使用A1，...，k表示它们。 它们的空间是H1，…， Hk，分别。 为了便于记法，我们用A−i表示A1. A i−1A i+1. A k，并在其他符号中使用下标−i（如H −i）表示类似的含义。矩阵理论 对于一个自然数n，我们让[n]表示集合{1，2，. . . ，n}。我们有时写A=[A（x，y）]来表示A是一个矩阵，第（x，y）个元素是A（x，y）。一个算子A被称为厄米特算子，如果A†=A。一个厄米特算子A被称为半正定（PSD），如果它的所有特征值都是非负的。 对于任何向量|v1，. . . 、|v r∈ Cn，r × r矩阵Mdef inedbyM（i，j）=nvi|vjisposiveemi-def inite。文[ 4 ]给出了矩阵的PSD-rankk的下式分解。定义9.对于矩阵P∈Rn×m，其PSD秩（rankpsd（P））是最小的r，使得存在PSD矩阵Cx，Dy ∈ Cr×r，其中tr（CxDy）= P（x，y），n ∈ [n]，y ∈ [m].可以看出，这对应于定义3中k= 2的特殊情况。 当k= 2时，我们去掉定义3中的上标（2），从而使其与上述矩阵的PSD秩的定义一致。量子信息。Hilbert空间H中的量子态ρ，记作ρ∈ H，是作用在H上的迹1半正定算子.如果一个量子态ρ是秩一，则称它为纯态即ρ = |ψ⟩⟨ψ|对于某个向量|单位范数为1/2的范数;在这种情况下，我们通常将ρ等同于|好吧def√二分之一二分之一对于量子态ρ和σ，它们的保真度定义为F（ρ，σ）=tr（σρσ）。 对于ρ，|H∈ H，我们有一个F（ρ，|ψ⟩⟨ψ|）=|ρ|好吧 Wedef inenormof|ψ⟩asǁ|ψ⟩ǁdef√⟨ψ|好吧为了一个人状态ρ∈ HA<$HB，我们用trHBρ表示ρ在HA中的部分迹，追踪出HB.让ρ∈ HA，|φ∈ HA<$HB使得trHB|φ⟩⟨φ|=ρ，则我们称之为|φ是ρ 的纯化。定义10. 对于一个纯粹的国家|<$$> ∈ HA<$HB，其施密特分解定义为：|ψ⟩ = 布雷尔i=1p i·|v i|当我们在一起时，哪里|V1是HA中的正交归一化状态，|W是HB中的正交态，p是概率分布。很容易看出，r也等于rank（tr|ψ⟩⟨ψ|）= rank（tr|ψ⟩⟨ψ|），因此A B在所有Schmidt分解中，|好吧 这个数字也被称为施密特秩，|10- 12 - 1 |ψ>）。上标（A，B）是为了强调分割在A和B之间。下一个事实可以通过考虑所涉及的纯态的施密特分解来证明;例如，参见[8]的Ex（2.81）。事实11. 让|但是，|φ∈HA<$HB使得|φ⟩⟨φ|= trHB|ψ⟩⟨ψ|. 存在一个单一的对HB的运算U使得（IHA <$U）|ψ>=|其中IHA是H A上的恒等算子。我们还需要乌尔曼（Uhlmann）所证明的另一个基本事实12（Uhlmann，[8]）。 设ρ，σ∈HA. 让|<$$>∈HA<$HB是ρ和dim（HA）≤的纯化dim（HB）. 存在一种净化|φ∈HA<$HB，使得F（ρ，σ）= |⟨φ|ψ⟩|.√9Jj=1ǫ）=min将在本文中使用的施密特分解的近似版本是如下所示，这被称为近似施密特秩。定义11. 设k> 0。 让|在HAHB中，纯态是。定义A、B、C、D、E、|ψ⟩def（2）A =A（|（φ）：|1998年，张晓飞（|ψ⟩⟨ψ|、|φ⟩⟨φ|）≥1 − 1}。对于多体纯态，一般不存在施密特分解。但一个较弱的说法成立。引理13. 假设|H1<$H2<$··<$Hk中的纯态，ρ i是H1 <$H2 <$··<$Hk的约化密度矩阵，|我的天 Denoteri=rank（ρi）。 如果{|αij∈：j∈[ri]}是ρic或p∈非零特征值的广义逆向量，则|可以将该函数表示为Σ|ψ⟩ =j1∈ [r1]，.，jk∈[rk]一个j1... JK|α1j1···|αkjk，其中，J1... jk是复系数。证据 对于每个i ∈ [k]，可以扩展向量|你好，我是... |正交基|你好，我是...|ψ iDi⟩ of Hi, where D iis the dimension of Hi.一个人可以分解|根据基础计算|ψij⟩:i∈[k],j∈[Di]. 这是一个简单的问题|在这里，你不会有任何麻烦。|你好，你好，[001 pdf 1st-31files] 这是真的吗？|我的意思是，我的意思是，我的意思是，|对于某些类型的应用程序，新的计算方法会将|在Hi中，Wegetρiw i w it thapomponentin|ij|. THUS|在没有任何零风险的情况下，我们可以通过简单的方法来管理业务。3多体态在这一节中，我们证明了1.1小节中关于多体态的量子关联复杂性的结果定理1（重述）。 假设|是H1<$···<$Hk中的纯态，ρ j是|在Hj. 然后QCorr（|ψ⟩)=克j=1、、、l0g2rank（ρj）.证据让rj=rank（ρ）。 根据引理13，假设|ψ⟩= Σij≤rj ai1. Ik |λi1⟩···|λ ik 在哪里？|λij⟩isthej-theigenvectorofρj. 这是一个非常复杂的问题|在此基础上，Σ种子状态|联系我们一|我的天|我阿斯克，- 是的 由于这个州需要ij≤rji1. ik1k，，j=1log2rank（ρj）数量在此基础上，提出了一种新的量子比特（| log rank（ρ）。2J对于另一个方向，让我们假设k个参与者生成目标|通过对初始种子状态σ的局部操作来实现，其大小为QCorr（|ψ>）。 首先注意，为了生成纯状态，具有纯状态作为种子就足够了，因为否则支持混合种子状态的每个纯状态可以给出相同的目标|好吧 现在定义系统Aj中σ的约化密度矩阵为σj，并假设其秩为s 则σ的大小至少为Σk，jj=1log2sj ，其中第j个被加数限定了10K23212这是一个很好的例子。在不确定的情况下，我们知道sj≥rj。 因此QCorr（|ψ⟩)≥克j=1、、、log2sj≥克j=1、、、log2rj克=j=1、、、l0g2rank（ρj）.正如我们前面提到的，生成一个二分混合量子态ρ与生成ρ的某种纯化具有相同的成本[12]。然而，在多方参与的情况下，这不再成立。下一个定理比较了生成混合态ρ和生成纯化态的量子相关复杂性定理2（重述）。 假设ρ是NkH中的量子态。然后我们有我.2ΣQCorr（ρ）≤r（ρ）≤2−kQCorr（ρ），其中r（ρ）是最小QCorr（|在所有的净化中|ρ的最大值证据第一，我们有QCorr（ρ）≤ QCorr（|用于任何净化|ρ的π，因此QCorr（ρ）≤ r（ρ）。现在对于另一个方向，假设生成ρ的最小种子态是σ，size（σ）=QCorr（ρ）。Letσieth ed dededdeddeddeddeddeddeddededdededdeded d e d e d d e d e d d e d d ed e d de d e ed e d ee ded是σi的量子位数，因此QCorr（ρ）=ki=1尼岛 在不失一般性的情况下，假设n1≤ · ·· ≤n k.采取任何净化|σ在HA1<$··<$HAk−1<$HAk <$HA′中的θ，其中A′k是Ancillarysystemint eroducedbyAk. 在一个并行程序中，局部并行程序可以附加一些额外的系统，执行一个酉运算，然后跟踪出系统的一部分。如果所有参与人都不追踪系统的任何部分，|θ而不是σ，则相同的协议导致纯态|这是一个纯化的ρ。这样，QCorr（|01 - 02 - 2016刘晓波（|θ）。根据定理1，我们有QCorr（|（θ）=克i=1log2ri对于i≤k−1，且r是树的维数|θ⟩⟨θ|. 注意k−1kH···Hri≤2ni，i≤k− 1，且rk≤2n1+···+nk−1，最后一个不等式利用了|θ是一个纯态。 因此，k.2000年.2ΣQCorr（|01-02-2016刘晓波（|（θ）=i=1100log2ri≤2i=1ni≤2 −ki=1ni=2 −kQCorr（ρ）.在上述定理中，当ρ是纯态时，左不等式是紧的。下面的命题通过一个三重态ρ的例子证明了右不等式也是紧的，其中Qcorr（ρ）=3，ndr（ρ）=4. 记录3-qubitGHZ状态|2019-01-2200：01：01（|000+|（111）and三个四分之一的水是|01-0|001+|010+|100磅）。14号提案 对于ρ0= 1|简体中文|+1个|W W|，则QCorr（ρ0）= 3，r（ρ0）= 4。i=111111111证据由于ρ0是一个3量子比特的状态，三个参与者可以简单地共享自己作为种子（然后什么也不做），所以QCorr（ρ0）≤3。接下来我们将证明r（ρ0）= 4，这通过定理2意味着QCorr（ρ0）≥3。因此，QCorr（ρ0）= 3。现在我们证明r（ρ0）= 4。假设ρ0的三个量子位分别被Alice、Bob和查理分别。一个简单的净化方法是1 1|GHZ频段|1分+2分|W|0，|0⟩,最后一个量子位是由一个参与者引入的，比如查理 以来|0我们将证明r（ρ0）≥4。假设ρ0的三个量子比特分别被Alice、Bob和Charlie为了方便起见，我们把这三个量子位称为主系统。 然后，在HA<$HA1<$HB<$HB1<$HC<$HC1中的ρ0的任意纯化可以表示为：1 1|GHZ频段|u 0 +2|W|u 1，|u1⟩,哪里|u0个字符|u1是正交的，它们由三个局中人引入的所有辅助系统组成. 请注意，有些玩家可能没有辅助系统。在不失一般性的情况下，我们假设|你属于爱丽丝。 我们从主系统中追踪出鲍勃和查理的两个量子比特，|快，快ρ a= trHB HC|ψ⟩⟨ψ|（五）.- 是的Σ1 1 1 1=2个|0 ⟩|u0 +6 |1 ⟩|u12 0|中国0|+ 100万美元|u1|1 1（六）+4个|1⟩⟨1|⊗ |u0u0|+3个|0⟩⟨0|⊗ |u1u1|、（七）其中第一个量子位属于爱丽丝，其余的是所有辅助系统的组合。继续采用Bo b和Carlie的循环系统，Alice的重新设计的循环系统ρa′中的新操作。 同样地，我们发现，ρ′borρc′、providedBoborCharrli具有一个非传统的部分，|你好。现在我们证明了ρ′a、ρ′b和ρ′c中至少有一个的秩至少为3。 如果是这样的话，rank（ρ′a）≥3，则Alice需要至少2个量子比特。由于鲍勃和查理每个人都需要至少1个量子比特，QCorr（|≥4。I f|你只是在李茜的房间里，我。e. 在一个线性系统中，当Alce=ρa时，等级为3。 现在假设鲍勃也引入了一个辅助系统。 我们主张，如果|u1不是（A，BC）上的乘积态，则ρ ′ a，ρ ′ b和ρ ′ c中的一个至少有秩|u1⟩ is not a productstate across (A, BC), then one of ρ′a, ρ′b and ρ′c has rank at least3. 事实上，假设|u0不是跨越（A，BC）的乘积状态，则rank（trHB <$HC|u0u0|）≥ 2。注意，（5）中的三个分量是正交的，因此rank（ρ′a）≥ rank（trHB <$HC|u0u0|）+的rank（trHB HC |），这意味着秩（ρ ′ a）≥ 3。|), which means rank (ρ′a) ≥ 3. 因此，我们只需要照顾的情况|u0个字符|u1是产品状态。由 于 它们是正交的，因此不失一般性，我们可以将它们表示为|u0= |u0，a|v0，bc|u1= |u1，a|v1，bc100，其中|u0，a0，|v0，bc 0，|v1，bc <$∈ H B 1 <$H C 1，其中，|u1，a = 0或u 0，bc|u1，bc n = 0.|u1,bc⟩ = 0.这样，1 1|000+ |111）|u 0，a|01-02|001+ |010+|001）|u 1，a|v1，公元前200年。|v1,bc⟩.121PSDXtJ我Xt、我1i，j=1X1XK不难证明ρ′bc = trHA<$HA的秩|ψ⟩⟨ψ|至少是3。与此同时，thatrank（ρ′bc）=rank（ρ′a）. 当rank（ρa′）≥3时，可满足上述条件。接下来我们考虑另一个极端，当ρ是多体经典态时，即一个多方参与的项目是一个很好的选择。在X上 接收 分类 数据 的内 容，我们将使用这些内容进行识别ρ=x P（x）|xx|. 还记得对于非负张量P =[P（x1，.，x k）] x1，.，xk，其PSD-rankrank（k）（P）是最小rs.t.存在r × r个 PSD矩阵C（1），.， C（k）≥ 0，P（x，.，X社会民主党）=rC（1）（i，j）· · ·C（k）（i，j）。x1xk定理3（重述）。 设P = [P（x1，.，x k）] x1，.，xk是X 1 × x上的概率分布···× X k. 然后我们有K，日志 rank（k）（P），≤QCorr（P）≤，（k） ，2k− 2PSDklog 2秩psd（P）。证据 首先证明右不等式。 设r=rank（k）（P），则存在正半-定矩阵{C（i）：i∈ [k]，x∈ X }s.t. 对 于 任何x =（x，...，x），则P（x）=xiiQQ1 .一 、 Kr kC（t）（i，j）. 对于i∈ [r]，令|u i（吨）n是C的第i列。然后我们就有了i，j=1t=1xtxtNxtji（t）ru xt|u xt = C xt（i，j）.我们现在定义一个纯态|ψ⟩ ∈t=1 (HAt⊗HA′⊗HA′′) as follows.布雷尔 Ok|ψ⟩ =t tΣ（|x t|x t|u in）。i=1t =1xt对于每个t，追踪第二和第三寄存器给出trA′A′′|ψ⟩⟨ψ|Ht Ht阿吉尔=|x1条x1条|⊗···⊗ |x kx k|Ykuxt |u xt⟩x1，.，XKi，j=1t=1阿吉尔=|x1条x1条|⊗···⊗ |x kx k|YkC（t）（i，j）x1，.，XKΣ=x1，.，XKi，j=1t=1P（x1，.，x k）·|x1条x1条|⊗ · · · ⊗ |x kx k|.THUS|如果ρ是一个整数，则该整数是一个整数，并且该整数2等于QCorr（ρ）≤QCorr（|ψ>）。，Frther注意，QCorr（|由定理1可知，从而证明了QCorr（ρ）≤klog2r.对于左不等式，假设|“”是一种纯态，Nki=1（HAi A′），实现了在定理2中，r（ρ）是最优的，那么这个定理告诉我们，克 ，，QkK213QCorr（ρ）≥01- 02 - 2013张国荣（|′K卷筒r2016年10月22日，≥i=1ri），（8）2k− 22k− 22我i=12k− 214J我我我≥j=1XKQxXX2K其中ri是的约化密度矩阵的维数，|在第i个玩家身上。根据引理13，|可以表示为EURR|ψ′⟩ =a我|α1⟩ · · ·|α kαQKJ我我i=1这里R =j=1 r j，对于i ∈ [R]，|α i <$∈ HAj <$HA′。应当指出，对于不同的i和我，|αjand|这是一个共同点。 在这个世界上，|我们的客户都是我们的客户伊伊ROk|ψ′⟩ =Σ|xj|uxj好吧i=1j =1xj记得|是ρ的提纯，所以ρ= trHA′. 阿哈|ψ′⟩⟨ψ′|1km2ΣΣR Yk′=|x1条x1条|⊗···⊗|xkxk|中国xj|uxjx1，.，XKΣ=x1，.，XKi，i′=1j=1P（x1，.，x k）|x1条x1条|⊗ · · · ⊗ |x kx k|.注意，对于任何x，R×R矩阵C，其中C（j，i）= u j|u i 所以根据定义对于PSD秩，我们有秩（k）（P）≤R=kr j。将该结果与Eq.（8）我们得到，PSD，j=1QCorr（ρ）k2k−2 log2 rank（k）PSD，这就完成了证明。4多体态在本节中，我们研究了生成多体状态的通信复杂性，并证明了1.2节中的结果。定理4（重述）。 假设|10、A是一个k-粒子纯态，而M（|ψ⟩)= Σk第二节秩（ρi）其中ρ i是|把参与人i的空间缩小到他的空间. 然后1M（|01-02-2016刘晓波（|10 - 1|ψ>）。证据让我们先证明上界。通过定理1，我们可以假设参与者可以通过对大小M的所见数据σ的局部选择来获得ρ（|ψ>）。 如果Playeri的 part ofσ 具 有 最 大 数 量 的量 子 比 特 ， 则 该 玩 家 可 以 准 备 σ 并 将 其 部 分 发 送 给 其 他 玩 家 。因此，通信成本最多为k-1M（|ψ>）。对于下限，假设参与者i和参与者j在最佳通信协议中通信c ij量子位，|首先，从产品状态开始。 考虑到量子操作的线性和目标状态是纯的，我们可以不失一般性地假设所看到的状态是纯的。 Dentebyri=rank（ρi），其中reρi为|你要去我的地盘。（P）1522i=1我≤≤2由于交换r个量子比特只能使参与人i和其他参与人之间的施密特排名增加最多2r，我们有Σri≤2j：jici j。把所有参与者对之间的通信放在一起，我们有ΣQComm（|ψ⟩)=1Σ ΣC =c1Σ≥log101- 02 - 2016刘晓波（|ψ>）。IJ{i，j}：i j2ij我j：j i2012年2月2日我上述定理中的两个界都是紧的。对于上限，考虑3量子比特GHZste|01-0|000+|111年）由Alice、Bob和Charlie组成。 Itisnotthardtosee t ttM（|2019 -03 -2200：00：0000：00|2. 对于较低的债券，可以将EPR P PPAir|01-0|00+|11日）SAREDY两个玩家 所以M（|2.2.2QComm（|1.在定理2及其后面关于边界紧性的评论中，我们已经看到，混合量子态ρ的关联复杂性一般不同于ρ的（甚至是最好的）纯化。下一个定理表明，对于通信复杂性，生成混合量子态与生成它的纯化是相同的。定理5（重述）。 对于任意k-分量子态ρ，QComm（ρ）= min {QComm（|（中文）：|是ρ}的纯化。证据 很明显，对于任何净化|10、QComm（？）|因为一个人可以只生成|ψ⟩ and then trace out some part to get ρ.对于另一个方向，假设r = QComm（ρ），则从 |0⟩, the players can通过局部操作和通信r个量子比特来生成ρ。这里所有的局部操作都可以假定为先附加一些附属部分，然后执行一个酉操作，最后跟踪出一些部分。如果玩家没有追踪到任何部分，那么在协议结束时，他们将拥有一个纯净的状态作为净化|ρ的最大值（2）Q-Qm（|ψ>）。下面的结果比较了一般多体量子态的QCorr（ρ）和QComm（ρ）推论6（重述）。对于任何k-分量子态ρ，它认为，k QComm（ρ） QCorr（ρ）2QComm（ρ）. k− 1证据 左不等式可以很容易地证明使用相同的论据作为定理4的下限证明。对于右不等式，根据定理5，我们可以找到一个纯化|ρ的单位（1）A（1）A（2）A（3）A（3）A（|ψ>）。 第四章：Q-Qm（|ψ⟩)≥1QCorr（|ψ>）。 将这些结果与定理2相结合，我们得到：QCorr（ρ）≤ QCorr（|2019- 05 - 25 00：00：00（|QComm）= 2 QComm（ρ）。16纯ǫi=1我）2分）（二）12分）、、 得双曲正弦值.、115二分态的近似量子关联复杂度在这一节中，我们研究了近似生成二分态的关联复杂性，并证明了1.3.1节中提到的结果。我们将首先考虑两种极端情况：量子纯态和经典分布，然后是一般的量子混合态。量子纯态。对于量子纯态，我们将首先证明以下两种近似是等价的。回想一下，对于状态ρ∈HA<$HB，QCorr（ρ）= min{QCorr（ρ′）：ρ′∈ HAB，F（ρ，ρ′）≥1−}，和QCorr′s（ρ）=min.QCorr（|（中文）：|其中，ρ = trH<$HΣ|ϕ ⟩⟨ ϕ|ǫ1 1.，、A1B1= min2016年02月03日02：00 - 02：00（|（掌声）：|ρ∈ HA1ABB1，ρ = trHA<$HB|.|.我们将需要在[6]中的一个结果，它说纯态可以被给定的另一个纯态最佳地近似。引理15（[6]）. 对于二分纯态|施密特系数λ1≥... 1999年，张晓波（|ψ⟩)=布雷尔QCorrpure（|其中r是最小整数s. t。λ2≥（1 −λ）2。16号提案 对HA<$HB中的任意量子态ρ，有QCorr<$（ρ）= QCorr′<$（ρ）.证据 QCorr<$（ρ）≥QCorr′<$（ρ）：设ρ′∈HA<$HB，F（ρ，ρ′）≥1−<$且QCorr<$（ρ）=QCorr（ρ′）。 根据[6]的引理2.2，存在一个纯化|A1ABB1of ρ′s.t. QCorr（ρ′）=、、、2019-02- 22 00：00：00 00：00|ψ⟩. 根据Uhlmann的理论，这些x是A 1 A B B 1中的一个纯函数，因此|阿尔法星，，则F（|α⟩⟨α|、|ψ⟩⟨ψ|）= F（ρ，ρ′）≥ 1 − ε。（我们假设，|αα和|两个扩张空间都在同一个扩张空间HA1ABB1中，否则我们可以使用两个扩张空间的并集。因此、、QCorr′（ρ）≤ log S-rank（|01- 02 - 2016 刘 晓 波（|ψ⟩= QCorrǫ(ρ).、、、QCorr（ρ）≤ QCorr′（ρ）：假设QCorr′（ρ）=log S-rank（|ϕ⟩ ，且