XiaoMi-AI文件搜索系统
World File Search System谓词
匹配对称谓词的上界...
在本文中，我们重点研究形式为 f ◦ G = f ( G ( X 1 , Y 1 ), . . . , G ( X n , Y n )) 的函数的量子通信复杂度，其中 f : { 0 , 1 } n →{ 0 , 1 } 是对称函数，G : { 0 , 1 } j × { 0 , 1 } k →{ 0 , 1 } 是任意函数，并且给定 Alice (或 Bob) ( X i ) i ∈ [ n ] (或 ( Y i ) i ∈ [ n ])。最近，Chakraborty 等人。 [STACS 2022] 证明，当允许双方使用共享纠缠时，f ◦ G 的量子通信复杂度为 O ( Q ( f )QCC E ( G ))，其中 Q ( f ) 是 f 的查询复杂度，QCC E ( G ) 是 G 的精确通信复杂度。在本文中，我们首先证明相同的陈述在没有共享纠缠和共享随机性的情况下成立，这推广了他们的结果。基于改进的结果，我们接下来在两个模型中证明任何对称函数 f (其中 AND 2 : { 0 , 1 } × { 0 , 1 } →{ 0 , 1 } 表示 2 位 AND 函数) 的 f ◦ AND 2 的严格上界：具有共享纠缠和不具有共享纠缠。这与 Razborov [Izv. Math. 67(1) 145, 2003]当允许共享纠缠时，我们改进了Razborov的界限，当不允许共享纠缠时。
定量最弱的超级pre：通过谓词变形金刚统一正确性和不正确性超副词
我们提出了一种新型最弱的微积分，用于对非确定性和概率程序的定量超普罗代理进行推理。现有的计算允许对数量从单个初始状态终止后假定的预期值进行推理，但我们这样做是为初始状态或初始概率分布的集合。因此，我们（i）获得了高hoare逻辑的最弱的前计算，（ii）启用有关所谓的高素质的推理，包括预期值但也包括数量（例如，差异）以前的工作范围。作为副产品，我们为加权程序获得了一个新颖的最强帖子，该职位既扩展了现有的最强和最强的自由主义后的计算。我们的框架揭示了前向和向后变压器之间的新颖二元性，正确性和不正确性以及不终止和不可收拾。
量子计算谓词绑定承诺及其在 NP 量子零知识论证中的应用
量子比特承诺方案是通过利用量子通信和量子计算来实现比特（而不是量子位）承诺。在本文中，我们研究了通过并行组成通用量子完美（或统计）隐藏计算绑定比特承诺方案（可基于量子安全单向排列（或函数）实现）获得的量子弦承诺方案的绑定性质。我们表明，与平凡的诚实绑定相比，所得方案满足更强的量子计算绑定性质，我们将其称为谓词绑定。直观且粗略地讲，谓词绑定性质保证，给定一组字符串上的任何不一致谓词对（即，该集合中没有字符串可以满足两个谓词），如果可以打开（声称的）量子承诺，使得所揭示的字符串肯定满足一个谓词，则不能打开相同的承诺，使得所揭示的字符串满足另一个谓词（除了可忽略的概率）。作为一种应用，我们在 Blum 的零知识协议中为 NP 完全语言汉密尔顿循环插入了一个通用的量子完美（或统计）隐藏计算绑定位承诺方案。由此产生的协议的量子计算健全性将直接来自承诺的量子计算谓词绑定属性。结合可以类似地建立为 Watrous [Wat09] 的完美（或统计）零知识属性，这产生了第一个量子完美（或统计）零知识论证系统（健全性误差为 1/2），适用于所有 NP 语言，仅基于量子安全单向置换（或函数）。