XiaoMi-AI文件搜索系统
World File Search SystemQCMA
QMA和QCMA的oracle分离具有有限的自适应
这是量子复杂性理论中的一个长期开放问题，即复杂性NP类的两个可能的量子类似物是否等效。QMA被定义为可以通过多项式量量子量子证人访问的多项式时间量子算法可以解决的决策问题，而QCMA是可通过多项式量子算法可解决的一类决策问题，仅通过多项式量子算法可以访问多项式规定的经典证人。换句话说，问题要问：量子证明是否比经典证据更强大？虽然包含QCMA QMA很容易看出，但这两个类别是否相等的问题（首先由Aharonov和Naveh [3]提出）仍然没有解决。的确，这些类别之间的无条件分离超出了当前已知的技术。一个更容易但仍未解决的问题是显示QMA和QCMA之间的甲骨文分离。这是因为Turing Machine模型中的Oracle分离可以通过在更简单的查询复杂性模型中的分离来显示，其中相似的
经典可访问预言机下的经典与量子建议和证明
量子信息通常比经典信息具有更丰富的结构，至少直观上是如此。第一个（但通常是错误的）想法是相位和幅度是连续的，并且量子信息可能能够存储比经典信息多出指数或无限多的信息；但这始终不正确 1 。由于经典信息和量子信息具有截然不同的性质，学界在不同背景和方向研究它们之间的区别，包括建议辅助量子计算[NY04、Aar05、Aar07、AD14、NABT14、HXY19、CLQ19、CGLQ20、GLLZ21、Liu22]、QMA 与 QCMA（即具有量子或经典见证的量子 NP）[AN02、AK07、FK18、NN22]、量子与经典通信复杂性[Yao93、BCW98、Raz99、AST + 03、BYJK04、Gav08] 等等。理解它们之间差异的一种方法是研究单向通信复杂度：即 Alice 和 Bob 想要用他们的私有输入联合计算一个函数，但 Alice 和 Bob 之间只允许进行一次量子/经典通信。在众多研究中，Bar-Yossef、Jayram 和 Kerenidis [ BYJK04 ] 展示了量子和经典单向通信复杂度之间的指数分离，即所谓的隐藏匹配问题。另一种方法是研究 QMA 与 QCMA 。2007 年，Aaronson 和 Kuperberg [ AK07 ] 展示了关于黑盒量子幺正的黑盒分离，而关于经典预言机的相同分离仍是一个悬而未决的问题。十多年后，Fefferman 和 Kimmel [ FK18 ] 使用分布式就地证明了第二种黑盒分离
量子无克隆与无电报之间的计算分离
量子信息的两个基本禁忌定理是不可克隆定理（即不可能复制一般量子态）和不可传送定理（即禁止在没有预先共享纠缠的情况下通过传统信道传送或发送量子态）。已知它们是等价的，即量子态集合只有在可克隆时才是可传送的。我们的主要结果表明，当考虑计算效率时情况并非如此。我们给出了一个量子态和量子预言的集合，相对于这些量子态，这些量子态可以有效克隆，但不能有效传送。鉴于相反的情况是不可能的（可以传送的状态总是可以轻易克隆），这给出了这两个重要的禁忌性质之间最完整的量子预言分离。我们还研究了复杂性类 clonableQMA ，它是 QMA 的一个子集，其见证者可以有效克隆。作为我们的主要结果，我们给出了 clonableQMA 和 QCMA 类之间的量子预言分离，其见证仅限于经典字符串。我们还提出了一个候选无预言承诺问题来分离这些类别。我们最后展示了可克隆但不可电报状态在密码学中的应用，展示了如何使用此类状态来防止密钥泄露。