量子科技中心_量科网

该研究团队证明了量子平滑标签覆盖问题是RE难的。这与Kempe、Regev和Toner（FOCS'08）提出的量子唯一标签覆盖问题形成对比，后者可被高效判定。该结果与量子标签覆盖问题的RE难性一致，后者源于Ji、Natarajan、Vidick、Wright和Yuen（ACM'21）著名的MIP* = RE结果。此外，该团队还证明了量子预言化平滑标签覆盖问题同样是RE难的。这与Mousavi和Spirig（ITCS'25）提出的关于量子预言化唯一标签覆盖问题RE难性的替代性量子唯一游戏猜想相符。该技术采用了一系列从停机问题到量子平滑标签覆盖问题的归约方法，并包含了Feige从3SAT到3SAT5归约（STOC'96）的量子可靠版本，这可能具有独立的研究价值。