基于Grover算法的圖著色問題求解

摘要： Grover量子搜索算法是針對(duì)非結(jié)構(gòu)化搜索問題設(shè)計(jì)的著名量子算法，可用于解決圖著色、最短路徑排序等問題，也可以有效破譯密碼系統(tǒng)。圖著色問題是最著名的NP-完全問題之一，文中首先將圖著色問題轉(zhuǎn)化為數(shù)學(xué)上的無向圖；然后采用布爾表達(dá)式將其轉(zhuǎn)換為布爾可滿足性問題，介紹了量子線路圖解決布爾表達(dá)式的步驟原理以及圖著色問題向布爾可滿足性問題的轉(zhuǎn)換過程；最后在IBMQ云平臺(tái)上，對(duì)三節(jié)點(diǎn)的2-著...