论文标题
$ k $颜色问题的电路设计及其在近期量子设备上的实现
Circuit Design for $k$-coloring Problem and Its Implementation on Near-term Quantum Devices
论文作者
论文摘要
如今，在量子计算中，量子算法的实施引起了轰动，因为嘈杂的中间尺度量子（NISQ）设备在市场上出现。研究人员最有兴趣借助量子算法来解决NP完整问题，以加快其加速。根据karp \ cite {karp}对计算复杂性的工作，如果可以解决任何NP完整问题，则可以将任何其他NP完整问题降低到多项式时间中的该问题。在本文中，已经考虑使用Grover的搜索来解决$ k $颜色的问题（NP完整问题）。一种基于比较的方法已用于实施$ k $颜色的问题，该问题可以降低与最先进的量子成本。已经提出了一个端到端的自动化框架，以在任何可用的嘈杂的中间尺度量子（NISQ）设备上实现$ k $颜色的问题，以帮助我们推广我们的方法。
Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speed-up. As per the work on computational complexity by Karp \cite{karp}, if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, $k$-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement $k$-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the $k$-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.
