极大极小问题的有效并行逼近算法及应用

1×极大极小问题Gus Gutoski吴晓迪加拿大安大略省滑铁卢大学量子计算研究所和计算机科学学院†美国密歇根州安娜堡市密歇根大学电气工程与计算机科学系2012年12月7摘要本文对一类新的极大极小问题提出了一种有效的并行逼近格式该算法是来自矩阵乘法权重更新方法，并可用于找到近最优的竞争性两方经典或量子相互作用的策略，其中裁判交换任何数量的消息与一方随后与其他任何数量的额外的消息它大大扩展了类的相互作用，承认并行解决方案，demonstrat- ing第一次存在的一个并行算法的相互作用，其中一方自适应地反应到其他。因此，我们证明了几个竞争证明复杂性类崩溃到PSPACE，如QRG（2），SQG和两个新的类称为DIP和DQIP。 我们结果的一个特例是 一类半定规划的并行逼近方案，其可行域由满足类似转录一致性条件的半定矩阵列表组成。应用到这种特殊情况下，我们的算法产生了一个直接的多项式空间模拟的多消息量子交互式的证明，导致QIP= PSPACE的第一性原理证明。1介绍本文提出了一类新的极小极大问题的并行逼近方案，并将其应用于经典和量子零和博弈及交互式证明。为了描述这类极小-极大问题，让我们首先考虑以下形式的半定规划（SDP）：尽量减少Tr（XkP）满足TrMn（Xi+1）=Φi（Xi），i=1，. . . ，k−1Tr（X1）=10 ≤X1，. . .，Xk∈Mmn（一）这里Md表示所有d d个复矩阵的空间，TrMn是部分迹-从矩阵到矩阵的唯一线性映射，满足TrMn：Mmn→Mm：A→Tr（B）A对于A∈Mm和B∈Mn的每一个选择。一个SDP（1）是由任意选择一个半正定矩阵P∈Mmn（其中P∈Mmn ≤1）和一个完全正的保迹线性映射所确定的arXiv：1011.2787v3 [quant-ph] 2012年122⊂--Φ1，. . . ，Φk−1：Mmn→Mm. （一个线性映射Φ是正的，如果当X ≥ 0时，Φ（X）≥0. 这样的地图，完全正的，如果Φ<$1Md对每一个正整数d都是正的。）设A表示SDP（1）的可行域（它总是非空的），设PMmn是a算子范数至多为1的半正定矩阵的非空紧凸子集我们关注下面的最小-最大问题，它是SDP（1）的推广：λ（A，P）=defmin（X1，.，X（k）∈A最大Tr（XkP∈PP）（2）最小化和最大化的顺序是无关紧要的，正如冯·诺依曼的最小-最大定理[vN 28，Fan 53]的众所周知的扩展所暗示的那样，我们的主要结果是一个有效的并行预言算法，寻找近似解的最小，最大问题（2）和近似λ（A，P），给出了一个在集合P.我们还描述了这个预言的并行实现某些集P，产生一个无条件有效的并行近似计划的最小-最大问题（2）的P的选择。该结果在下面作为定理1正式陈述。在陈述这个定理之前，让我们澄清一下术语。1.1并行计算的回顾，结果回想一下，一个并行算法是由一个矩阵空间均匀布尔电路族描述的均匀性约束确保了该族中每个电路的大小按输入的位长度的多项式缩放，因此该族表示多项式时间计算。布尔电路是并行计算的理想模型，因为计算活动可以同时发生在电路中的许多不同的门。实际上，并行算法的运行时间是由其电路的深度决定的，其深度可能比其电路的总大小如果并行算法的电路深度（以及算法的运行时间）与输入位长的对数成多项式关系，则称该算法是高效的。 复杂度类NC由那些可以通过有效的并行算法计算的函数组成。高效的并行算法有时被称为读者可以参考[Pap94]来了解并行计算的介绍。一个预言算法是一种算法，它被赋予了对属于某个特定预言范围内的问题获得即时答案的能力。在我们的例子中，我们假设一个关于P的最优化的预言，它立即解决了以下形式问题1（P上的最优化）。输入：矩阵X≥0，Tr（X）=1，精度参数δ>0。输出：一个近似最优元素P<$∈P，使得Tr（XP<$）≥Tr（XP）−δ，对于所有P∈P。通过在标准的门集合（如AND，OR，NOT）中添加一个特殊的oracle门，将oracle合并到计算的电路模型中。这个预言门有许多输入位（描述问题）和许多输出位（描述答案）。与标准门一样，每个oracle门对电路大小和运行时间贡献单位成本。近似方案是指将一个或多个量计算到给定精度δ的算法，并且其运行时间对于δ >0的每个固定选择是有效的，但不一定与δ很好地缩放。在电路模型（以及其他模型）中，该属性通过定义潜在问题来封装，使得精度参数δ= 1/s以一元形式指定为1s，从而迫使3K×- -1ǁ ǁ≤K输入与1/δ而不是1/log（δ）成比例。选择指定的精度参数在一元允许并行逼近计划被描述整齐的对数空间均匀电路与polylog深度。下面是我们的算法解决的问题的正式声明问题2（λ（A，P）的近似）。输入：完全隐式和保迹线性映射Φ1，. . . ，Φk-1，其指定形式（1）的SDP的可行区域A。精度参数δ> 0。甲骨文：P上的优化（问题1）。输出：近似最优元素（X，. . . ，X<$）∈ A且P <$∈ P使得Tr（X<$P）≤λ（A，P）+δ，对所有P∈PTr（XkP）≥ λ（A，P）− δ，对于所有（X1，. . . ，Xk）∈ A和一个量λ，|λ−λ（A，P）|≤δ。映射Φ1，. . . ，Φk−1是从一个维数为（mn）2的复向量空间到另一个维数为m2的复空间的线性映射。因此，这些映射可以由大小为m2（mn）2的复矩阵表示。 在问题1和问题2中，假设每个输入矩阵中的每个条目的实部和虚部被表示为有理数，所述有理数表示为对于某个p的以二进制书写的两个p位整数的比率，所述p被承诺在维度mn上缩放为多项式. （实际上，p与mn成比例关系就足以满足我们的目的。）如前所述，还假设精度参数δ以一元表示这些假设使我们能够专注于数量mn，k，1/δ作为决定我们的并行算法的运行时间的主导因素现在我们可以陈述我们的主要结果。定理1（主要结果）. 对于问题2（λ（A，P）的近似）有一个并行的预言算法，其运行时间由k，1/δ和log（mn）中的多项式限定。如果k，1/δ被保证为log（mn）中的多项式，则该算法是有效的。1.2应用：半定程序在P=P是单例集的特殊情况下，SDP（1）从（2）恢复。 因此，定理1的特殊情况是形式（1）的SDP的并行逼近方案。我们将注意力限制在其中P，Tr（X1）1的SDPs上，因为这种限制与我们在量子交互协议中的应用无关，并且因为我们的并行算法的运行时间与P的最大特征值和X1的迹成多项式比例，所以只有当这些量被输入P，Φ1，. . . ，Φk−1。（为了保持一致，我们可以将这些数量视为我们考虑的SDP的宽度。我们的算法仅对宽度有界的SDP有效很久以前就知道，逼近任意SDP的最优值的问题对于P[Ser91，Meg92]是对数空间困难的，因此不可能存在针对所有SDP的并行逼近方案，除非NC= P。SDP允许并行解决方案的确切程度尚不清楚。我们的结果的这个特殊情况大大增加了这样的SDP集，包含了当时该领域的所有先前工作它被公开了。（从那时起，我们的方案[JY11，PT12，JY12]没有涵盖的一些无界宽度的SDP的时间并行近似方案已经被发现。4≥| |在这方面，关于SDP的一些已知知识是从线性规划（LP）继承的知识。例如，Luby和Nisan描述了一种用于所谓的正LP的并行近似方案，其形式为在Cx≥q和x≥0的条件下，其中矩阵C和向量p，q的每个条目是非负实数[LN93]。Young将Luby-Nisan推广到任意混合填充和覆盖问题[You 01]。相比之下，Trevisan和Xhafa表明，找到正LP的精确解是P-困难的[TX 98]。1LP的正例的概念可以如下推广到SDPSDP的形式最小化Tr（XP），条件是X≥Q且X≥0如果P，Q0和Q1是正映射，则称Q1是正映射。当然，正的LP精确解的P-硬度意味着正的SDP精确解的P-硬度. Jain和Watrous给出了宽度有界的正SDP的并行近似方案[JW 09]。随后的改进扩展到所有阳性SDP [JY11，PT12]，甚至扩展到混合包装和覆盖SDP [JY12]。正SDPs的Jain-Watrous算法是从正SDPs和单圈量子博弈之间的对应关系中推导出来的在QIP =PSPACE的证明中，Jain等人给出了一个基于量子交互式证明的特定SDP的并行算法[JJUW11]。不难看出，它们的SDP可以写成本文所考虑的形式（1）如上所述，我们的算法在用于无限宽度的SDP时效率不高，Jain和Yao[JY11，JY12]以及Peng和Tangwongsan[PT12]最近关于混合填充和覆盖SDP的工作是唯一已知的并行SDP近似方案，不包含在本工作中。这些最近的工作不subsubsubstantive我们的结果，既不是SDP实例中使用的参考。[JJUW11]本文证明QIP=PSPACE及其推广（1）都是混合填充和覆盖SDP。1.3应用：与竞争证明者的1.3.1定义具有竞争证明者的交互式证明由验证者和两个证明者之间关于某个输入字符串x的对话组成。验证者可以使用随机性，但必须在输入长度x的多项式中运行;证明者被允许无限的计算能力。其中一个证明者（是证明者）试图说服验证者接受x，而另一个证明者（非证明者）试图说服验证者拒绝x。一个决策问题L被称为允许与具有完备性c和可靠性s的竞争证明者的交互式证明，如果存在c，s，其中c> s和满足以下条件的随机完备性条件。如果x是L的一个yes实例，那么yes证明者可以说服验证者以至少c的概率接受，而不管no证明者健全条件。 如果x是L的非实例，则非证明者可以说服验证者拒绝，不管是不是证明者的策略，概率至少为1 − s。1为了澄清，多项式时间算法找到LP或SDP的精确解，如果它找到在ε的比特长度中的最优时间多项式的ε内的解，即log（1/ε）。相比之下，LP或SDP的近似方案找到在ε内的最优解，其中运行时间超多项式地取决于ε的位长度，通常为1/ε。5- ≥| |−≥| |||| |完整性和可靠性参数c、s不需要是固定常数，而是可以作为输入长度x的函数而变化。如果没有指定这些参数，则假设L允许与竞争证明者进行交互式证明，以选择c（x），s（x），其中存在多项式有界函数p（x），使得cs1/p。复杂性类RG由所有的决策问题，承认与竞争的证明交互式证明（首字母缩略词RG代表通常在交互式证明的研究中，c，s的精确值是不重要的，因为顺序重复（有时是并行重复）可以用来将任何c s1/p的验证器转换为另一个c趋向于1而s趋向于0的验证器，在x的位长度上以指数方式快速地变化。（例如，顺序重复之后的多数表决可以用于减少RG的错误。出于这个原因，通常在不丧失一般性的情况下假设c、s是常数，例如2/3、1/3，或者c以指数方式接近于1，并且s以指数方式接近于0，只要这样做是方便的然而，给定的复杂度类对于c，s的选择是否健壮并不总是很清楚，因此在定义这些类时尽可能地包含这些类是一个很好的实践RG的有趣子类是通过对验证者和证明者之间的交互中的消息的数量和时间进行限制来获得的在本文中，我们介绍了一个这样的子类基于以下形式的相互作用：1. 验证者只与是-证明者交换几条消息2. 在处理与是-证明者的交互之后，验证者仅与非-证明者交换几个附加消息。3. 经过进一步处理后，裁判宣布接受或拒绝。这种形式的交互式证明应称为双重交互式证明：在这样的协议中，验证者执行与yes-prover的标准单证明者交互式证明，然后执行与no-prover的第二单证明者交互式证明。允许双重交互证明的问题类称为DIP。与RG相比，DIP的定义在以下方面是否稳健并不立即清楚：参数c，s的选择。但从我们的结果可以得出，DIP实际上对于c，s的选择是稳健的。此外，虽然RG在补集下是平凡封闭的，但双重交互证明的协议是不对称的，因此不能立即清楚DIP在补集下是封闭的。同样，从我们的结果可以得出DIP在补数下是封闭的。RG的另一个有趣子类的例子是有界转弯类族。对于每个正整数k，类RG（k）由允许与竞争证明者交互证明的那些问题组成，其中验证者与每个证明者交换不超过k个消息。应当理解，与证明器并行地交换消息，使得RG（k）像RG一样在补下平凡地闭合。具有竞争证明者的量子交互式证明的定义类似，除了验证者是与证明者交换量子信息的多项式时间量子计算机。类似的复杂度类表示为QRG、DQIP和QRG（k）。1.3.2先前工作如 参 考 文 献 中 所 述 。 [FKS95 ， FK97] ， Koller 和 Meggido[KM92] 以 及 Koller ， Megiddo 和 vonStengel[KMvS94]的结果表明RG是EXP。费格和基利安6⊆2⊆[FK97]，得到特征RG = EXP。这在Ref中得到了证实[2017 - 07 - 07 00：07：07]这是一个人，QRG = RG = EXP，这是著名的折叠QIP = IP = PSPACE的竞争证明者版本，用于单证明者交互式证明[LFKN92，Sha92，JJUW11]。对于有界转向类，Fortnow等人的结果。 告诉我们RG（1）本质上是SP[FIKU08]的随机化版本。 Feige和Kilian证明了RG（2）= PSPACE [FK97]。2对于有界圈量子类，[JW 09]证明了QRG（1）PSPACE。QRG（2）的复杂性是[JJUW11]的一个公开问题，本文解决了这个问题。RG（k）和QRG（k）对于所有其他k的精确复杂度是未知的。有界回合双量子交互式证明以前曾在短量子博弈的名称下进行过研究;相关的复杂性类被称为SQG。为了统一符号，让DQIP（k，l）表示由允许与竞争证明者进行双量子交互证明的问题组成的类，其中验证者与是证明者交换不超过k个消息，然后与非证明者交换不超过l个消息SQG类首先在Ref.[GW 05]等于DQIP（1，2），其中示出了该类包含QIP = DQIP（poly，0）。短量子博弈的重要性已经被QIP = PSPACE的证明所削弱，因为QIP的包容性不再是这样一个特殊的属性。然而，PSPACE包含在DQIP（1，2）中仍然是有趣的，因为不知道PSPACE是否包含在DIP（1，2）中，DIP（1，2）是这个的经典版本。课1.3.3我们的贡献正如我们在第5节中所解释的，定理1的预言机算法--以及适当选择的预言机的并行实现--意味着在双量子交互式证明中，证明者的近最优策略然后，下面的遏制来自一个标准论点（在5.4节中总结）。定理2. DQIP空间。这种包容性，当与平凡的包容性IP<$DIP<$DQIP和众所周知的事实，即PSPACE<$IP[LFKN92，Sha 92]相结合时，产生以下特征。推论2.1。 DQIP = DIP = PSPACE。作为推论2.1的一个特例，我们得到了[JJUW11]的一个公开问题的解推论2.2。QRG（2）= PSPACE。我们的结果的另一个特殊情况是多消息量子交互证明的直接多项式空间模拟，导致QIP=PSPACE的第一性原理证明。推论2.3。 QIP = PSPACE通过多消息量子交互证明的直接多项式空间模拟。[2]我们称之为RG（2）的类被Feige和Kilian称为RG（1）[FK 97]。这种符号上的冲突源于这样一个事实，即我们轮流测量交互的长度（即每个证明者的消息），而那些作者则以消息的轮数来测量交互。 这种符号的转换是由Jain和Watrous发起的，他们需要一个方便的符号来进行一轮互动[JW 09]。7≤||相比之下，所有其他已知的证明[JJUW11，Wu10]都依赖于这样一个事实，即可以假设验证者只与证明者交换三条消息[KW 00]。Jain等人的原始证明[JJUW11]还依赖于另外一个事实，即验证者给证明者的唯一消息可能只是一个经典的抛硬币[MW05]。当然，每一个其他的竞争证明复杂性类，其协议可以被转换为双重交互证明，也崩溃到PSPACE，例如前面提到的基于短量子博弈的类DQIP（1，2）从DQIP和DIP到PSPACE的崩溃可以看出，这些类在完备下是封闭的，并且它们对于参数c，s的选择是鲁棒的。（实际上，可以假设对于任何期望的多项式有界函数q（x），c = 1且s2−q--见6.3节。）在本工作之前，多项式空间算法仅已知用于两圈经典的间具有竞争证明者的主动证明（RG（2））、具有竞争证明者的单轮量子交互证明（QRG（1））以及单证明者量子交互证明（QIP）。我们的结果统一和归纳了所有这些算法.它还表明了第一次存在的多项式空间算法的竞争，证明者相互作用（经典或量子），其中一个证明者的反应自适应其他。最后，我们的研究结果说明了一个不同的效果之间的公共随机性单证明者交互式证明和竞争证明者交互式证明。 任何具有单个证明者的经典交互式证明都可以通过另一个公共硬币交互式证明来模拟，其中验证者发送给证明者的消息完全由均匀随机位组成，并且验证者不使用其他随机性[GS 89]。将公共币交互的概念扩展到竞争证明者交互，很容易看出，与公共币验证者的任何此类交互都可以通过双重交互证明来模拟[3]因此，RG的公共硬币版本是DIP的子集，我们现在知道DIP等于PSPACE。因此，与公共币IP= IP的单一证明者情况相比，在竞争证明者情况下，我们建立以下内容。推论2.4。public-coin-RG/= RG除非PSPACE = EXP。1.4技术概述1.4.1矩阵乘性权值更新法定理1的证明中给出的并行预言算法是文献[1]中提出的矩阵乘权更新方法（MMW）的一个例子。[AHK05、WK06、Kal07]。我们借鉴了最近应用这种方法并行算法的量子复杂性类[JW 09，JUW09，JJUW11，Wu10]的宝贵经验。我们还广泛使用高效的并行算法进行各种矩阵操作任务，如计算矩阵的奇异值分解或指数 读者是指冯祖尔Gathen更多的细节并行算法矩阵运算[vzG93]和工程的Jain等人。 用于讨论这些算法在矩阵乘法权重更新方法的并行实现中的使用[JUW09，JJUW11]。在其不变的形式下，MMW可用于求解密度算子-半正定矩阵X上的极小极大问题，其中Tr（X）= 1。我们引入了一个新的扩展，这种方法的最小最大问题的定义在SDP（1）的区域A-一个域的k-元组的密度算子躺在一个严格的子空间的仿射空间与k-元组的密度算子。我们的方法的高级方法如下：3证明草图：由于验证者81. 将定义域从单个密度矩阵扩展到密度矩阵的k元组这一步很简单：MMW可以同时应用于所有k个密度矩阵而不复杂（等价地，k密度矩阵可以被看作是一个更大的块对角密度矩阵。2. 将定义域限制为密度矩阵的k这一步比较难。它是通过放松问题，以允许所有的k元组，与一个额外的惩罚条款，以消除激励球员使用不一致的成绩单。3. 将松弛问题中的策略舍入为原始协议中的策略对于这一步，必须证明一个1.4.2在双量子交互证明中寻找证明者的最优策略在第5节中，我们观察到双量子交互式证明中的验证者诱导了形式为（2）的最小-最大问题，其中A的元素对应于是证明者的策略，P的元素对应于否证明者的策略因此，定理1的并行预言算法-连同用于在P上优化的预言的并行实现-可以用于在双量子交互式证明中为证明者找到最优策略。我们的实现这个预言本身是定理1的算法的一个特例，因此整个算法以两级递归的方式使用MMW方法两次。在顶层，MMW用于迭代地收敛到用于是-证明者的最优策略;在底层，MMW再次用于求解SDP，以获得用于是-证明者的给定策略的“最佳响应”。使用MMW为量子相互作用中的各方找到最佳策略的核心挑战是找到适合MMW方法的策略表示在Kitaev的抄本表示[Kit02]中，在双量子交互证明中证明者的动作由列表X1，. . . ，Xk的密度矩阵，这些密度矩阵满足由SDP（1）的可行域A的定义捕获的特殊一致性条件。直观地说，这些密度矩阵对应于验证者的量子位在相互作用期间的不同时间的状态（参见第20页的图3。）我们利用的双量子交互式证明的关键属性是能够在交互中绘制一条“时间线”，在此之前只有赞成者采取行动，之后只有反对者给定成绩单X1，. . .，Xk，则无证明者的动作可以由另一个转录本Y1，. . . 、Yl. 通过优化所有这样的成绩单，得到一个预言的“最佳对策”的无证明者的一个给定的策略的是-证明者所需的1.4.3半定规划方法的比较在QIP = PSPACE的证明中，Jain等人[JJUW 11]通过直接使用Kale论文[Kal 07]中描述的原始-对偶方法，使用MMW来解决量子交互式证明的特殊SDP。 随后的正SDP [JY11，PT12]和混合包装和覆盖SDP [JY12]的并行算法是现有线性规划算法[LN 93，You01]的矩阵推广（也基于MMW）。我们不使用任何这些方法来解决SDP。相反，我们使用MMW来解决最小-最大问题，正如Kale的论文中提出的最小-最大定理的算法证明所建议的那样9一类简单的零和量子博弈通过引入一个惩罚项的不可接受的策略，我们能够扩展该算法到一个更丰富的游戏类超越了一轮游戏认为羽衣甘蓝。我们要强调的是，我们的并行算法的SDPs出现作为一个特殊的情况下，一个更一般的最小最大算法，而以前的方法SDPs不推广到最小最大的问题，在任何明显的方式。1.4.4QIP= PSPACE的证明与本文不同，Jain等人[JJUW11]的QIP= PSPACE的原始证明没有利用任意多回合策略的转录本表示。相反，如前所述，这些作者通过调用关于量子交互证明的几个重要事实来推导出一个特殊的SDP。诚然，他们的SDP确实与Kitaev的转录条件相似，但这种相似只是表面上的，他们的事实上，他们的推导没有假设验证者只发送经典的消息给证明者。以前我们之一[Wu 10]提出了一个简化的证明QIP = PSPACE，像本论文的工作，采用Kale的算法最小-最大定理[Kal 07]，而不是原始对偶方法的SDPs中使用的原始证明由Jain等人。[JJUW11]. 量子电路可验证性问题的QIP-完备性[RW 05]意味着量子交互证明可以通过近似两个量子通道之间的差异的钻石范数来决定。Wu注意到，在这种特殊情况下，钻石范数可以通过直接应用Kale的算法最小-最大定理来近似。他的结果不需要本文介绍的惩罚方法，也不需要伴随的舍入定理。1.4.5Bures角度最后，值得注意的是，我们的舍入定理（定理5）的证明包含了布勒斯角的一个有趣而重要的应用，布勒斯角是量子态的距离度量，它是根据更熟悉的保真度函数定义的。跟踪范数的性质，它捕获的量子态的物理可验证性，是足够的量子信息中的大多数需求。当还需要保真度的某些属性时，使用Fuchs-van de Graaf不等式在迹范数和保真度之间进行转换[FvdG99]。（这些不等式在等式中列出。（第2.3节）然而，每一个这样的转换会导致相关精度参数的二次松弛。我们的研究需要重复转换，如果通过Fuchs-van de Graaf天真地进行，这将导致不可接受的指数松弛。相反，我们只做了一个单一的转换之间的迹范数和布勒斯角，然后反复利用的同时性质（i）三角不等式，（ii）量子信道下的收缩性，和（iii）子系统保真度的保存。虽然Fuchs-van de Graaf已经给出了迹范数与Bures度量之间的转换不等式所需的不等式在本文中导出（命题4）。2预赛此后，我们必须假设熟悉量子信息的标准概念，尽管我们试图尽量减少对量子形式主义的使用，以使更广泛的受众受益。读者可以参考尼尔森和庄[NC00]以及沃特罗斯[Wat11]的课堂笔记，以获得适当的介绍10→⟨ ⟩ × ⟨⟩Σǁǁ⟨ ⟩ ⟨⟩0≤≤I到外地。 本节提供了一个简短的词汇表，澄清了我们在2.1节中的符号和术语，然后回顾了量子信息中两个更罕见但仍然简单和基本的概念：2.2节中的子系统保真度的保持和2.3节中的Bures角。2.1术语和符号密度矩阵，量子态。 密度矩阵或量子态是半正定矩阵X，其中Tr（X）= 1。 到目前为止，我们已经使用了大写罗马字母（X，Y，. . . ）来表示密度矩阵以及其它矩阵。但量子信息中的标准做法是用小写希腊字母（ρ，ρ，ρ）表示密度矩阵。. . ）的。兹通过本公约。测量操作员。 度量算子是一个半正定矩阵M，其中M ∈M ∈ ≤ 1。等价地，0≤M≤I成立。量子频道。通道是从矩阵到矩阵的完全正的保迹线性映射Φ：MmMn。这些映射对应于量子态上物理上可实现的操作。伴随矩阵内积。矩阵A的伴随矩阵A的共轭转置就是A的共轭转置。两个m n矩阵A，B之间的内积A，B由A，B=Tr（A<$B）给出。两个k-矩阵元组之间的内积由和给出KA1，. . . ，Ak），（B1，. . . ，Bk）n = nAi，Bi n.i=1更一般地说，从矩阵到矩阵的线性映射Φ的伴随Φ是唯一的线性映射，其中Φ（X），Y=X，Φ∈（Y）对所有X，Y。这个公式以显而易见的方式扩展到从矩阵元组到矩阵元组的线性映射。追踪诺姆。矩阵X的迹范数XTr定义为X的奇异值之和。作为量子态之间距离的度量，迹范数由下式给出：12ρ−Tr=maxρ−，（3）对于所有的密度矩阵ρ，ρ。忠诚。 保真度是量子态的另一个距离度量，由下式给出：F（ρ，ε）=ερεTr对于所有的密度矩阵ρ，ρ。2.2保持子系统保真度考虑保真度函数的以下性质，我们称之为子系统保真度的保持：如果ρ，是具有保真度F（ρ，）的量子系统的状态，ρJ是与ρ一致的更大系统的任何状态，那么总是可以找到与一致的J，使得F（ρJ，J）=F（ρ，）。一个正式的建设，这样的一个juji出现在参考。[JUW09]。 由于其结构完全由对于初等矩阵运算，存在一种有效的并行算法，该算法将ρ、ρ、ρJ作为输入，并产生期望的状态ρJ作为输出。11∈≤−∈≤≥2TrTr命题3（子系统保真度的保持[JUW09，引理7.2]）。 设ρ，ε ∈ Mn，ρJ∈Mn是密度矩阵，TrMn（ρJ）=ρ. 存在一个密度矩阵 Mmn，其中TrMm（mJ）=m，并且F（ρJ，ρJ）= F（ρ，ρ j）. 此外，在给定ρ、ρ、ρJ的情况下，可以高效地并行计算Ρ J。2.3Bures角度量子态ρ、ρ之间的布勒斯角或简称为角A（ρ，ρ）定义为：A（ρ，ε）=defarcosF（ρ，ε）。角是量子态的度量，这意味着它是非负的，只有当ρ = π时才等于零，并且服从三角不等式[NC00]。此外，角度是收缩的，因此，A（Φ（ ρ），Φ（ρ））≤ A（ ρ，ρ）对于任何量子通道Φ。 Fuchs-van de Graaf不等式建立了保真度和迹范数之间的关系[FvdG 99]。不等式是1√21−F（ρ，）≤2ρ−Tr≤1−F（ρ，）.（四）这些不等式可以用来推导A（ρ，λ）和λρ − λ λTr之间的关系。比如说，命题4（迹范数与Bures角的关系）。 对于所有的密度矩阵ρ，1ǁρ−ξǁ≤A（ρ，ρ）≤. π πρ − ππ证据 A（ρ，λ）的下界直接由Fuchs-van de Graaf得出：1√ρ−这里我们对所有的x都用sinx x的恒等式。为了得到A（ρ，π）的上界，我们使用了对x [0，π/ 2]的恒等式cos x1x2/π，这可以用基本微积分来验证。然后我们有12<$ρ− <$$>Tr≥1−cosA（ρ，<$）≥由此得出命题。A（ρ，λ）2π3一个松弛极大极小问题的舍入定理在本节中，我们定义一个新的最小-最大表达式µε（A，P），它近似于所需的量λ（A，P）从（2）在极限ε接近零。 这个新的表达式是λ（A，P）的松弛，更适合MMW。我们证明了一个我们在引理8的证明中使用了布勒斯角，引理8用于证明我们的舍入定理。2Tr212∈克∈∈εk−1（ρ，...，ρ）P∈PKεMn我我我（ρ，...，ρ）P ∈Pε2Mn我我εMn我我我εKK Trε2Mn一期+1我我Trε2Mn定义i=1定义λ（A，P）的松弛量με（A，P），kk−1µ（A，P）=最小最大值ρ，P+Tr（ρ）−Φ（ρ），Φ（ρ）1K（2001年，...，Πk−1）k−1i=1= min1最大功率K，P<$+k<$1<$Tr（ρi=1）−Φ（ρ）这里取所有密度算子ρ1，. . . ，ρk∈ Mmn以及所有P ∈ P和所有测量算子上的最大值. . . ，k−1嗯。 第二个等式直接由2.1节的恒等式（3）得出。请注意，在定义µε（A，P）中的最小值是在所有k元组（ρ1，. . . ，ρk），而不仅仅是A.求和中的每一项都用来惩罚任何违反A中成员资格所需条件的行为，方法是将违反的幅度加到目标函数中。k/ε因子放大了惩罚，从而消除了选择A之外的元素的激励。事实上，μ limε（A，P）= λ（A，P）.ε→0下面的“舍入”定理建立了这个极限的特定收敛速度。该定理的后续扩展（命题7）提供了一种方法，通过该方法可以从με（A，P）的近最优点有效地计算λ（A，P）的近最优点。定理5（舍入定理）。 对于任何ε> 0，它保持λ（A，P）≥ με（A，P）> λ（A，P）− ε。Pr oof. 第一个不等式很简单：设（ρ1，. . . ，ρk）对于λ（A，P）是最优的，设（P，λ1，. . . ，k−1）对于με（A，P）是最优的。然后我们有λ（A，P）≥ λρ，P=ρk−1，P+Tr（ρ）− Φ（ρ），Φ ≥ μ（A，P）.i=1（第一个不等式是因为（ρ1，. . . ，ρk）对λ（A，P）是最优的. 等式成立是因为（ρ1，. . . ，ρk）∈A，所以和中的每一项都是零。最后一个不等式是因为（P，n =1，. . . ，k−1）对于με（A，P）是最优的。）第二个不平等更加困难。我们引用下面的引理，其证明将在本节后面给出。引理6（舍入引理）。 F或任意ε>0和任意态ρ1，. . . ，ρkMmn，则存在（ρJ1，. . . ，ρkJ）一个这样的k1ǁρ−ρJ<<$ε +<$Tr （ρ ）−Φ（ρ）<$。此外，ρJ1，.. . ，ρJk可以在给定ρ1，.. . ，ρk.设（ρ1，. . . ，ρk）对于με（A，P）是最优的，设（ρJ1，. . . ，ρJk）是由引理6得到的密度算子，设P ∈ P对λ（A，P）是最优的. 因为（ρ1，. . . ，ρk）对于με（A，P）是最优的，我们有k−1一期+1K一期+1TrKK一期+12K一期+1113ε我我μ（A，P）≥ μρ，P<$+k<$1<$Tr（ρi=1）−Φ（ρ）（五）Tr141≤K−KKKK2KK TrK2KKKε2Mn一期+1我我KKεMn一期+1我我我k−1i=1利用恒等式（3），量<$ρk，P<$成为ρρ，P ρ =. ρJ，P +. ρ− ρJ，P ≥. ρJ，P − 1-ρj。从引理6中代入1<$ρk−ρJk <$的界，我们看到（5）中迹范数的和取消了，离开2 Trµ ε（A，P）>. ρJk，P<$− ε≥ λ（A，P）−ε如所期望的。(The最后一个不等式是因为P对于λ（A，P）是最优的。命题7（近最优策略的构建）。对于任何δ，ε >0，以下成立：1. 如果（ρ1，. . .，ρk）对于με（A，P）是δ-最优的，则存在一个有效的并行算法来计算（ρJ1，. . . ，ρJk）∈ A，对λ（A，P）是（δ + ε）-最优的.2. 如果（P，p<1，. . . ，k−1）对于με（A，P）是δ -最优的，那么P对于λ（A，P）也是（δ+ε）-最优的。第1项的证明。 设（ρ1，. . . ，ρk）对με（A，P）是δ -最优的，设（ρJ1，. . . ，ρJk）∈ A是由引理6得到的，且设P∈P.我们有. ρJ，P≤ρ，P+< $ρ−ρJ<$k1≤<$ρ，P<$+ε+<$Tr（ρ）−Φ（ρ）<$≤με（A，P）+ε+δ ≤λ（A，P）+ε+δ（第一个不等式来自（3）;第二个来自引理6;第三个是因为（ρ1，. . . ，ρk）对于με（A，P）是δ -最优的;第四个，因为με（A，P）λ（A，P）.）因此，可以得出（ρJ1，. . . ，ρKJ）对λ（A，P）是（δ+ε）-最优的.第2项的程序。 设（P，P，1，. . . ，k−1）对于με（A，P）是δ -最优的。 F或a n y（ρ1，. . . ，ρk）∈A，则k−1kρ，P≥με（A，P）−δ > λ（A，P）−ε−δ（等式是因为（ρ1，. . . ，ρk）∈ A所以和中的每一项都为零。 第一个不等式是因为（P，n=1，. . . ，k−1）对于με（A，P）是δ -最优的。最终不等式是因为με（A，P）>λ（A，P）ε.） 因此，P对于λ（A，P）是（δ + ε）-最优的。现在我们证明引理6，它的陈述出现在定理5的证明中。给定任何状态ρ1，. . .，ρk这个引理断言这些状态可以被“舍入”到元素（ρ j 1，. . .，ρJk）∈A，使得最终状态ρk和ρJk之间的距离由以下程度的函数限定：（ρ1，. . . ，ρk）违反了A中成员资格所需的条件。让我们重新陈述引理6，钻头角度。KTri=1Tr15∈∈Σ.Σ.Σ2kkTr-是的× ≤ ≤×∈ΣΣ22δ引理8（舍入引理）。 F或任意ε>0和任意态ρ1，. . . ，ρkMmn，则存在（ρJ1，. . . ，ρkJ）一个这样的k−1A（ρk，ρjk）≤A（TrMn（ρi+1），Φi（ρi））.i=1此外，ρJ1，.. . ，ρJk可以在给定ρ1，.. . ，ρk.证据 定义ρJ1，. . . ，ρJk递归地如下。设ρJ1=ρ1。 对于每个i = 1，. . . ，k − 1通过保持子系统保真度（命题3），存在ρJi+1（可以并行有效计算），TrMn（ρJi+1）=Φi（ρJi）和A（ρi+1，ρIJ+1）=ATrMn（ρi+1），Φi（ρij）.根据三角不等式，这个量最多A（TrMn（ρi+1），Φi（ρi））+AΦi（ρi），Φi（ρIJ）.根据通道下Bures角的收缩性，右边的被加数至多为A（ρi，ρJi）。引理现在从A（ρ1，ρJ1）= 0的事实归纳得出。很容易从引理8恢复引理6：从引理8和命题4（迹范数和Bures角之间的关系）可以直接得出：1ρ−ρJ≤k−1π2<$TrMn（ρi+1）−Φi（ρi）<$Tr.i=1引理6则由以下事实得出：<对于所有x ≥ 0且所有δ> 0，都有<$π x 1 x + δ。图4求解极大极小问题的并行预言算法在这一节中，我们证明定理1（主要结果），展示了一个有效的并行预言算法的基础上毫米波寻找近似解的最小-最大问题（2）。本文中使用的毫米波方法的精确公式如下所述为定理9。 我们对这个定理的陈述有点不标准：结果通常以算法的形式给出，而我们的陈述是纯数学的。然而，粗略检查的文献，说，Kale定 理 9 （ 乘 法 权 重 更 新 方 法 [Kal07 ， 定 理 10] ） 。 固 定 γ （ 0 ， 1/2 ） 和 α> 0 。 设M（1），. . . ，M（T）是任意dd“损失”矩阵，其中0 M（t）αI. 设W（1），. . . ，W（T）是由下式给出的d个“权重”矩阵：W（1）=IW（t+1）=exp.-γ。M（1）+···+M（t）设ρ（1），.. . ，ρ（T）是通过归一化每个W（1），.. . ，W（T），使得ρ（t）= W（t）/Tr（W（t））。对于所有的密度算子ρ，不1不t=1.ρ（t），M（t）≤.ρ，不1不t=1M（t） +α。γ+lnd.γTΣ16克A，ε11εMn我我我A，ε1ε211εKk−1A，ε，i1ε我 我A，ε，k1εk−1εA，ε，11εA，ε，i1εA，ε，k1εε注意，定理9对于损失矩阵M（ 1 ），. . . ，M（ T ），包括其中每个M（ t ）基于W（1），. . . ，W（t）. 这种损耗矩阵的自适应选择在MMW的实现中是典型的。在说明我们的算法之前，让我们先建立一些符号。 设ε >0，考虑线性映射fA，ε具有以下性质，f（ρ，. .. ，ρ），（P，P，. . . ，）=ρk−1，P+Tr（ρ）−Φ（ρ），Φ（ρ）i=1这样我们就可以写µε（A，P）=min（ρ 1，...，ρk）MaxP∈P（2001年，...，k−1）ε（ρ1，. . . ，ρk），（P，ρ1，. . . ，k−1）.显然，映射fA，ε由下式给出：f：（ρ，.