量子科技中心_量科网

该团队研究了在量子光子实验中由多部分W态生成的图论表示所产生的一类边染色图。在抽象掉物理振幅和相位后，该工作引入了W态图：配备半边二染色的匹配覆盖图，使得每个完美匹配恰好包含一条双色边，且每个顶点都与一条红色半边关联。该团队的主要贡献是对W态图给出了完整的结构刻画。该工作证明：一个图是W态图当且仅当其每个3连通分量都是一个W锥——一种由万能顶点和因子临界基定义的简单且刚性的构建模块。这一刻画表明不存在简单的W态图，并给出了一种运行速度与验证图是否为匹配覆盖图相当的识别算法。该团队还证明了向迪克态的自然推广会遇到复杂性障碍：验证两个迪克态条件之一本身就是coNP完全问题，解决了瓦尔迪（音译）和张（音译）[IJCAI 2023]的一个开放问题。该团队的研究结果将W态图牢固地置于经典匹配理论中，并精确刻画了能够在实验图框架中实现理想化W态的组合结构。