量子科技中心_量科网

基于门的量子计算标准模型正日益受到扩展研究的关注，这些扩展引入了遵循非线性薛定谔方程的辅助自由度。通过将布尔可满足性问题SAT归约为量子态区分，Abrams和Lloyd论证了，在理想的无噪声极限下，恰当类型的非线性可用于在多项式时间内解决{\sf NP}和\#{\sf P}问题。然而，在实际实现中，该团队只能使用模拟和涌现的非线性，例如超冷原子平均场模型及类似系综中出现的非线性。一个显著的例子是扭转模型，它出现在双组分玻色-爱因斯坦凝聚体和具有全对全伊辛相互作用的自旋模型中。但基于扭转的态区分似乎不足以解决SAT问题。该工作通过构建Valiant-Vazirani定理的过滤预言机来弥补这一差距，提供了从SAT到UNIQUE SAT（一个保证最多只有一个满足赋值的承诺问题）的随机多项式时间归约。在无噪声极限下，利用扭转非线性可在多项式时间内解决UNIQUE SAT问题。量子Valiant-Vazirani归约并不比高效的经典版本更快，但结合模拟扭转的非线性量子协处理器的容错实现，将能在多项式时间内解决{\sf NP}（而非\#{\sf P}）问题。