XiaoMi-AI文件搜索系统
World File Search System着色
在kempe变化下着色的最短重新配置
图形的k颜色图将图的每个顶点映射到{1，2，。。。，k}，因此没有两个相邻的顶点获得相同的颜色。给定图形的k色，kempe变化通过将颜色交换在双色连接的组件中而产生新的k色。我们研究了发现给定的k颜色转换为另一个给定的k颜色所需的最小kempe变化的复杂性。我们表明，这个问题在路径图上接受了多项式的动态编程算法，事实证明这是高度不平凡的。此外，问题即使在星形图上也是np-hard，我们在此类图上表明，它可以接受恒定的因子近似算法，并且当通过颜色数k进行参数时，可固定的参数可触及。硬度结果以及算法结果基于规范转换的概念。
图着色量子算法的编译规划
摘要。最近，编译通用量子算法以便在近期量子处理器上实现的问题已被引入人工智能社区。先前的研究表明，时间规划是此编译任务的一部分的一种有吸引力的方法，具体而言，是在量子处理器架构上应用于 MaxCut 问题的量子交替算子拟定 (QAOA) 的电路的路由。在本文中，我们将早期的工作扩展到实现图着色问题 QAOA 的电路的路由。着色的 QAOA 需要在芯片上执行更多、更复杂的操作，这使得路由成为一个更具挑战性的问题。我们在领先的量子计算公司最先进的硬件架构上评估了该方法。此外，我们还研究了将规划方法应用于量子位初始化和路由。我们的实证评估表明，时间规划与合理的分析上限 [20] 相比效果良好，并且使用经典规划器解决量子比特初始化通常有助于时间规划器找到用于图着色的 QAOA 的更短完成时间编译。这些进展表明，时间规划可以成为更复杂的量子计算算法和架构的有效方法。