量子科技中心_量科网

此前，所有已知的量子可满足性问题（QSAT）变体——即判定某个k局部（k体）哈密顿量是否无阻挫——均能被归类为属于P类，或对NP、MA、QMA1完全的问题。该研究团队在此揭示了该问题的新量子比特变体，它们分别对BQP1、coRP、QCMA、PI(coRP, NP)、PI(BQP1, NP)、PI(BQP1, MA)、SoPU(coRP, NP)、SoPU(BQP1, NP)和SoPU(BQP1, MA)完全。这一结果表明，若要对量子约束满足问题（QCSP）进行类似于Schaefer经典CSP二分定理的完全分类，则必须纳入这13个复杂度类，或证明其中某些类别等价。 该工作还展示了两类可高效判定的新型QSAT问题，以及首个非平凡的BQP1完全问题。研究人员首先证明存在对BQP1、coRP和QCMA完全的量子高维体系（qudit）QSAT问题。通过将哈密顿量集合限定为包含类似“电路转哈密顿量”构造中Hinit、Hprop和Hout的元素，并引入高维数据量子位、时钟量子位、三值逻辑，以及纠缠单配性或特定时钟编码等机制，确保所有由此生成的哈密顿量可在对应复杂度类中判定。该团队进而证明了一个非平凡结论：任何QCSP均可保复杂度地归约至量子比特问题——这被认为是经典计算无法实现的。其余六个问题通过前述七类QSAT问题的“和”与“积”构造获得。此前同类方法生成的QSAT问题仅能产生与NP、MA或QMA1平凡等价的PI和SoPU完全问题，该研究首次开启了这些新型非平凡复杂度类的系统性探索。 需指出的是，[Meiburg, 2021]虽最早尝试证明coRP、BQP1和QCMA完全性，但其构造存在缺陷导致证明错误。该工作不仅修正了这些构造，还优化了所需量子高维体系的维度要求。