没有合适的资源?快使用搜索试试~ 我知道了~
NP的量子特征HUGUEBLIER和 ALAIN T应用程序抽象。在本文中,我们引入了一个新的复杂性类,称为PQMA log(2)。非正式地说,这是一类语言,对于这类语言,验证者有一个具有完美完整性和可靠性的量子大小的量子证明,在验证者被提供两个未纠缠部分的证明的上下文中,该证明多项式接近1。然后我们证明了PQMAlog(2)= NP。要做到这一点,重要的是,在定义类时,不要给验证者太多的权力与QMAlog= BQP的事实相比,这个结果为我们提供了关于量子信息的力量和纠缠的影响的新关键词量子复杂性,交互式证明主题分类。68Q15复杂性等级1. 介绍在经典复杂性中,证明的概念被广泛用于定义非常有趣的复杂性类,如NP,MA和IP。 当允许验证者(和证明者)是量子力学的,我们得到复杂性类,如QMA和QIP。 量子复杂性类有时会有令人惊讶的性质。例如,与经典情况相比,我们知道量子交互式证明可以被限制为三个消息;即QIP=QIP(3)(?)。由于量子计算的概率性质,NP最自然的这是一类具有多项式大小量子证明的语言。量子证明显然需要一个量子验证者,但在完备性和可靠性方面与经典证明类似。由于QMA(?)中存在组非成员关系但是不知道是在MA中(并且因此是在NP中),我们有一个具有多项式大小的量子证明但没有已知的多项式大小的经典证明的状态的例子arXiv:0709.0738v2 [quant-ph] 2010年11月2布利尔·塔普⊆√√√氮3+在本文中,我们感兴趣的是量子尺寸的量子证明。经典上,当考虑多项式时间验证器时,对数大小的经典证明的概念并不有趣。任何具有几何规模的经典证明的语言也将在P中,因为人们可以在多项式时间内遍历所有在量子的情况下,非常短的量子证明仍然是有趣的。量子证明的任何合理的经典描述都需要多项式数量的比特,因此不能使用经典模拟器尝试所有的量子证明。也就是说,如果验证者足够简单,则找到使验证者以足够高的概率接受的证明的优化问题可以转化为半定规划问题(??)多项式的大小因此,如果验证器足够简单,那么语言是此外,如果验证者在BQP中,则仍然仅获得BQP(?)。虽然我们刚刚指出,量子规模的经典和量子证明似乎是无趣的,但通过稍微改变游戏规则,我们得到了一个有趣的复杂性类。在前期工作中,我们证明了NP ≠QMA log(2)。这个类的定义也承诺给验证器两个对数大小的非纠缠寄存器。此承诺为用户提供了更多的机会来检查该产品,并限制了该产品的可操作性。因此,这为纠缠的性质提供了一个新的视角与我们的工作并行,并独立于我们,Aaronson等人。(?)已经表明,3SAT在QMAlog(npolylog(n))(即具有n个polylog(n)非纠缠寄存器)中具有恒定的完整性和可靠性。似乎只有两个未纠缠的寄存器的证书是不够的,以检查证明与完整性和可靠性之间的一个恒定的差距;我们实现完美的完整性,但可靠性多项式接近一。他们评论了我们先前的说明(?)强调除非QMA(2)= NEXP,否则该可靠性不能被改进为常数。还要注意的是,由于证明的长度是对数的,寄存器的数量是恒定的,如果证明3COL(可以用三种颜色 着 色 的 图形 语 言 ) 在 QMAlog ( 2 ) 中 , 就 意 味 着 NP≠ QMAlog(2)。因此,在(?)代价是他们的结果不能推广到NP QMAlog(npolylog(n)),因为多项式归约将导致证明的长度多项式地增加在最近的一篇文章中(?)已经展示了如何为语言3SAT获得1-1的可靠性有两个寄存器。NP的量子刻画3∈ UU类QMAlog(2)很小(包含在QMA中),但仍然包含NP和BPP。这是一个有趣的性质,因为NP和BPP之间没有已知的关系。证明QMAlog(2)的非决定性意味着经典非决定性允许我们模拟多项式大小的量子电路。在本文中,我们表明,通过稍微改变类的定义的范式unentangled对数大小寄存器导致类NP的表征。因此,我们引入了一个新的复杂性类PQMAlog(2),并证明了NP = PQMAlog(2)。再一次,这个类被定义为在完整性和可靠性之间有一个多项式小的差距与我们的初步工作相比,我们定义了QMAlog(2),我们不认为验证器在量子多项式时间内工作,而只是能够生成作用于对数数量量子位的多项式大小的量子电路。这仍然允许验证者执行协议,例如在(?)而且还为PQMAlog(2)类定义了一个经典的多项式大小的证书,这意味着PQMAlog(2)是 NP2. 定义和定理PQMAlog(2)类(经典多项式时间量子Merlin Arthur,具有两个非纠缠对数大小证书)的正式定义如下。非正式地,它可以被看作是存在对数量子证明的语言类,并承诺它被分成两个非纠缠部分。验证器在经典多项式时间内工作它允许产生作用于对数数量的量子比特的多项式大小的量子电路下面的定义只是一个正式的声明,通常被称为一组门可以有效地近似。定义2.1. 自然门集合是作用于有限数量的量子位的酉变换的有限集合,使得对于所有U,存在可以在n中的时间多项式中近似矩阵U的每个元素直到n位的经典算法。此外,C(U)是由U的门组成的电路的集合。有了这个定义,我们可以正式定义PQMAlog(2)。4布利尔·塔普Q V ∈Up(n)定义2.2. 语言L在PQMA log(2)中,如果存在自然门集合U,多项式p和q,常数c和允许在多项式时间内运行的经典算法V,对于单词x,其中|X|= n,以产生作用于O(log(n))量子位的多项式大小q(n)的量子电路=(x)C(),使得:.log(n)log(n)1) (完备性)如果x ∈ L,存在一个状态|w∈H2[001 pdf 1st-31files] |w= accept]= 1,其中|w=|w1 |w2;S.T..log(n)log(n)2) (可靠性)如果x/∈ L,其中|X|= n,则对于所有状态|w∈ H2,[001 pdf 1st-31files] |w=accept] <1 −1,其中|w= |w1|w2主要结果是NP = PQMAlog(2)。这将使用以下众所周知的NP完全语言来证明定义2.3. 3COL是图G =(V,E)的集合(使用任何自然编码成字符串),对于它存在着色C:V → {0,1,2}使得对于E中的所有(x,y),C(x)/= C(y)。第2.4节. NP = PQMA log(2)这将在下面两个部分中得到证明在下一节中,我们将描述一种 算 法 , 表 明 3COL 在 PQMAlog ( 2 ) 中 因 此 , NP≠ PQMAlog(2)。然后证明了PQMAlog(2)≠ NP。3.3COL的对数尺寸量子证明在本节中,我们将证明以下陈述:3.1. blog NP-PQMAlog(2)为了证明这个陈述,我们将证明3COL语言属于PQMAlog(2)类。我们将在引理3.2中讨论完备性,在引理3.8中讨论可靠性证明是决定性的,因为3COL在多项式时间约简上是NP完全一方面,PQMAlog(2)中的可靠性只需多项式接近1。另一方面,证明是对数大小的,寄存器的数量是恒定的。因此,NP中的任何决策问题简化为3COL,仍然会有一个协议,该协议具有最小规模的证明和令人满意的可靠性。NP的量子刻画5′′◦| ⟩|⟩√卢恩我223n3.1. 协议和完整性。我们描述了3COL语言的验证器证明的登记册|我的朋友和|Φ n都被看作是Hn<$H3中的向量,分别是寄存器的节点部分和颜色部分。验证者以相等的概率执行以下三个测试之一。如果测试成功,他接受,否则他拒绝。◦ 测试1:(两个寄存器相等)执行交换测试(?)对|如果测试失败,则检查并拒绝。|Φ⟩and reject if the test fails.◦ 测试2:(与图表一致)|我的朋友和|在计算基础上测量Φ i,得到(i,C(i)),(i,C(i)),a) 如果i=i′,则验证C(i)=C′(i)。b) 否则,如果(i,i′)∈E,则证明C(i)/=C′(i)。测试3:(所有节点都存在)对于Φ和Φ,在傅立叶基中分别测量寄存器的索引部分和颜色部分。如 果 颜色部分的测量结果为F3| 0且索引部分的结果不是Fn|0,然后拒绝。下面的引理说明协议具有完备性1。3.2. hot water 如果x ∈ 3COL,则存在上述验证者将以概率1接受的证明。P屋顶。 让量子证明|Ψ ⟩=|Φ=1μ m|我的|C(i)其中C是图G的一个有效染色.互换测试输出的概率2等于1+| ⟨Ψ |Φ ⟩| (?). 以来|Ψ ⟩=|Φ 1,测试1成功的概率为1. 因为C是G的一个有效着色,我们有测试2成功,概率1。要看到测试3也将肯定成功,就足以看到:1Σ1Σ1<$2πic k(I)F3|c j =n|cj⟩= √nJ|j⟩ √eJKJ|k而且,如果必须在数据库中存储此颜色,|哦,那是你的状态将为1|i= Fn|0分。Q我6布利尔·塔普/∈28N| ⟩ | ⟩≥至少16岁Q4N我J3.2. 健全。现在让我们考虑的情况下,G3COL。引理3.8在这一节的末尾指出,如果G不是3-可着色的,则存在三个测试之一将失败的不可忽略的概率为了证明这一点,我们需要以下五个简单的引理。因为我们知道证明器给出的两个寄存器并不纠缠在一起,所以它们可以分别写为|Ψ⟩= Σαi|我的我Σβi,j|j|联系我们JΣαi′|我的我Σβi′,j| jJΣ哪里2Σ|α | =1和1,|β|Φ100|Φ⟩. 并不难看到使用非纠缠混合态对证明者没有下面的引理将给我们一些有用的事实,当在计算基础上测量时,状态的行为下一个引理说,如果测试1以足够高的概率成功,那么两个状态的结果分布3.3. babyBABY 让|我的朋友和|如前所述。 如果存在一个k和一个l,则||αkβk,l|−|αk′βk′,l||≥1/n3,则Test1将至少具有16的概率。P屋顶。设Pi,j= |αiβi,j|2和Qi,j= |αi′βi′,j|2是概率分布,当|Φ 0和|在计算基础上测量了平均值。 我们将使用这样一个事实,对于任何冯诺依曼测量,下面定义的距离使得D(φ,Φ)D(P,Q),其中P和Q是测量的经典结果分布。然后,√1−|⟨Ψ|Φ⟩|2d=efD(|Ψ>,|Φ)≥D(P,Q)def=1美元。α β.|α ′ β′|α′β′|二、|IJi i,j.i i,j1.一、≥|αβ.|α ′ β′|α′β′|.k k,l21 1.k k,l≥2·n3这意味着|⟨Ψ |Φ ⟩|2 ≤ 1 − 16,测试1有可能失败8N下一个引理指出,具有足够高的被观察概率的节点具有明确定义的颜色。22我i、jNP的量子刻画78Nn2| −≥−。2008N| ⟩|||||| ≤n2−100我 .βi,1.我n2453.4. babyBABY考虑到量子证明将通过测试1和部分a)试验2的失效概率不大于1.6,必须是为此|αi|≥1,0!j,使得|βi,j|2≥99。P屋顶。 为了矛盾起见,假设存在这样一个i的|αi|2 ≥1,其中两个βi,j的平方范数大于1/ 200。因此,我们可以假设,|βi,0|2> 1/200,|βi,1|2> 1/200。由于引理3.3,我们有|α′|二、. 22′≥|α ||β21 1 1因此,在测量时获得(i,0)的概率|当测量时,|Φ m至少为.- 是的Σ1 1 1 1200n2200n2−n3≥8n6当n足够大时。这与假设相矛盾。因此,三种颜色中的两种颜色的振幅的范数平方必须小于1、总结证明。Q接下来的三个引理告诉我们测试3实际上意味着什么3.5. 考虑到量子证明将通过测试1和部分a) 测试2的失败概率小于16,则测量的概率|0= F3|当n足够大时,在颜色寄存器上的傅立叶基中的0π大于1/5。P屋顶。 假设测量节点寄存器。如果结果是i,则在颜色寄存器上的傅立叶基中获得0的概率由下式给出:123|βi,0 + βi,1 + βi,2|.对于概率大于1/n2的所有i,引理3.4适用,在这种情况下,我们可以假设w.l.o. gβi , 02> 99/ 100,并且βi , 12+βi , 221/ 100。利用Cauchy-Schwarz不等式,我们得到123|βi,0 + βi,1 + βi,2|≥123||βi,0|− |βi,1+ βi,2||1≥3 ||βi,0|−1≥4.2012年10月2日(|βi,1|2个以上|βi,2|(二)|2现在,请注意,只有n1个节点的概率小于1/n2,因此在颜色寄存器上获得0的概率为最小(1−(n−1)1)1≥1对于足够大的n。Q一,1n3200N2n38布利尔·塔普2n1| ⟩≥....16n概率至少为168n6我10N3.6.BLOG给定一个状态|X= γ|这样就存在一个l,我21|,那么,|0 <= F n|当我们测量时,|0⟩when we measure|在傅立叶基中,X至少是16n2.P屋顶。设P和Q为测量时的概率分布,|在计算基础上分别求出了X_n和F_n_0。使用与引理3.3相同的技巧,我们得到:.1−|X|0⟩|2d=efD(|X,|0分)D(P,Q)- 是的 .def1.21.=2。|γi|. 我-n..1 .一、21.≥2。|γl|1≥4例-n.这意味着测试失败的概率大于12。Q第3.7章. 假设测试1、测试3和测试2的a)部分以大于1的概率成功,那么对于所有i,|α |2≥1。PROF.由于使用了Lemma3.5,因此可以根据颜色选择适当的选项在执行测试3时,寄存器至少为1/ 5。 让|X=iγi|我是国家在颜色寄存器上测量0之后,|好吧 假设在原文中有一个i|这样一来,|αi|2 <1/(10 n)。同样,由于引理3.5,我们必须有|γi|2<1/(2 n)。现在,从这个事实和引理3.6,我们得出结论,|测试3失败的概率太大了。 因此,对于所有的我,|2 ≥ 1 /(10 n)。|2 ≥ 1/(10 n).Q现在,使用引理3.3、引理3.4、引理3.5和引理3.7,可以证明我们的验证器的可靠性。3.8. 如果x/∈3COL,则所有量子证明都将失败,24n我NP的量子刻画9−8N8NQQP屋顶。 假设图G不是3可着色的,并且它将以小于1 6的概率不通过测试1、测试3和测试2的部分a)。令C(i)= max j|βij|成为一种色彩。 由于引理3.3和引理3.4,这个最大值被很好地定义了。 由于图是不可3-着色的,所以G中存在两个相邻顶点v1和v2,使得C(v1)= C(v2). 由于引理3.7,当执行测试2时,我们在第一寄存器中测量C(v1)的概率至少为1/(10 n2),并且由于引理3.3和引理3.7,我们在第二寄存器中测量C(v2)的概率为1/(10 n2)1/n3。结合这些结果,我们有大于16的失败条件的概率b) 测试2。Q4. 多项式大小语言的经典证明PQMA日志(2)在本节中,我们将证明以下陈述。4.1. blog PQMAlog(2)P屋顶。我们将证明,对于PQMAlog(2)中的所有语言L,存在该语言的完全经典多项式时间验证器V′验证者V′将接收量子证明的经典描述(密度矩阵),并以足够的精度计算量子电路Q=V(x)的接受概率。设g是与语言L相关联的验证器的可靠性和完备性之间的差距。根据定义2.2中介绍的符号,g=1/p(n)。更确切地说,(完全)经典验证者V′将做以下事情,以便接受语言L。 让我们称之为经典见证ρ。 验证者V′首先模拟V(为类PQMA log(2)定义的验证者)来计算量子电路Q=V(x)∈C(U)的描述。 设U是对应于的么正变换,并且U-accept是对应于在接受量子比特上测量1的投影器。 验证者V′以精度g/3近似值Tr(acceptU(ρρ)U<$如果接受概率大于1-g/ 2,则验证者V′ 这个值可以在多项式时间内计算,因为作用的量子位数是对数的,门的数量是多项式的。Q10布利尔·塔普√5. 结论本文证明了NP = PQMAlog(2).这给出了最重要的复杂性类别之一的量子特征此外,这种特征是有趣的,因为它是在交互式证明的范式内完成这一结果让我们了解了量子信息的力量和纠缠的微妙之处。对于未来的工作,一方面,一个非常自然的方法来改进我们的结果将是调查NP = PQMAlog(2),即使在可靠性和完整性之间的差距是常数,而不仅仅是不可忽略的。如前所述,这将是令人惊讶的,因为它可能导致结果QMA(2)= NEXP。作为一个中间结果,可以尝试在证明中使用常数数量的未纠缠部分来显示完整性和可靠性之间的更好的差距。这与QMAlog(k)是否= QMAlog(2)的问题有关,也让人想起QMA(k)与QMA(2)的问题。另一方面,Aaronson et al.(?)以需要n个polylog(n)寄存器为代价实现了恒定的间隙是否可以使用较少的非纠缠寄存器,但仍然实现恒定的间隙?最终的目标确实是证明NP中的所有语言都有对数大小的量子证明,并且具有恒定的完整性和可靠性。如果不是这样的话,为了得到一个NP完全问题的恒定间隔,这样的证明的最小长度是多少?确认我们要感谢Tsuyoshi Ito的深刻讨论。我们也希望能让Freder2009年8月收到Mandarin pt于格比列如果您想了解更多信息,请访问blierhug@iro.umontreal.cawww.example.comALAIN T应用程序如果您想了解更多信息,请访问tappa@iro.umontreal.cawww.example.com
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 构建智慧路灯大数据平台:物联网与节能解决方案
- 智慧开发区建设:探索创新解决方案
- SQL查询实践:员工、商品与销售数据分析
- 2022智慧酒店解决方案:提升服务效率与体验
- 2022年智慧景区信息化整体解决方案:打造数字化旅游新时代
- 2022智慧景区建设:大数据驱动的5A级管理与服务升级
- 2022智慧教育综合方案:迈向2.0时代的创新路径与实施策略
- 2022智慧教育:构建区域教育云,赋能学习新时代
- 2022智慧教室解决方案:融合技术提升教学新时代
- 构建智慧机场:2022年全面信息化解决方案
- 2022智慧机场建设:大数据与物联网引领的生态转型与客户体验升级
- 智慧机场2022安防解决方案:打造高效指挥与全面监控系统
- 2022智慧化工园区一体化管理与运营解决方案
- 2022智慧河长管理系统:科技助力水环境治理
- 伪随机相位编码雷达仿真及FFT增益分析
- 2022智慧管廊建设:工业化与智能化解决方案
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)