论文标题
用于图形着色问题的量子优化，并具有空间有效的嵌入
Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
论文作者
论文摘要
当前的量子计算设备根据其架构具有不同的优势和劣势。这意味着需要灵活的电路设计方法。我们通过引入图形着色问题的新型太空量子优化算法来解决此任务。我们的电路比标准方法的电路更深。但是，所需量子位的数量在颜色数量中被指数减少。我们提出了广泛的数值模拟，证明了我们的方法的性能。此外，为了探索当前可用的替代方案，我们对量子退火器上的随机图进行了研究，以测试该方法的限制因子。
Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.
