Constrained quantum annealing of graph coloring

We investigate a quantum annealing approach based on real-time quantum dynamics for graph coloring. In this approach, a driving Hamiltonian is chosen so that constraints are naturally satisfied without penalty terms and the dimension of the Hilbert space is considerably reduced. The total Hamiltonian, which consists of driving and problem Hamiltonians, resembles a disordered quantum spin chain. The ground state of the problem Hamiltonian for graph coloring is degenerate. This degeneracy is advantageous and is characteristic of this approach. Real-time quantum simulations in a small system demonstrate interesting results and provide some insight into quantum annealing.

Figure 1

Schematic of the model which consists of Eqs. (4) and (5). The solid lines represent the edges of a graph, namely, the interaction in the problem Hamiltonian. The broken lines correspond to the driving Hamiltonian.

Figure 2

Annealing-time dependence of residual energy $E_{\mathrm{res}}$ for (a) linear annealing and (b) exponential annealing. Data for two different driving Hamiltonians are compared: NN and FC types. If the annealing process is adiabatic, the residual energy is expected to obey the power law with respect to the annealing time: $E_{\mathrm{res}}/J\propto {\tau }_{\mathrm{li}}^{-2},{\tau }_{\mathrm{ex}}^{-2}$.

Figure 3

Annealing-time dependence of the success probability $P_{\mathrm{suc}}$ for (a) linear annealing and (b) exponential annealing. Data for NN and FC types of driving Hamiltonians are compared.

Figure 4

Energy gap ${\mathrm{\Delta }}_{\mathrm{g}}\left(s\right)/J$ between the ground and the first-excited states of the Hamiltonian of an example. The graph corresponding to the problem Hamiltonian is given by Fig. 5. Data for the NN and the FC types of driving Hamiltonians are compared.

Figure 5

Examples of graphs that correspond to the problem Hamiltonian. (a) Regular random graph with connectivity $c=3$. (b) Graph with only $4!$ degenerate solutions in a four-coloring problem.

Figure 6

Time dependence of the instantaneous residual energy, which is measured in units of $J$, for NN-type and FC-type driving Hamiltonians. Annealing time is ${\tau }_{\mathrm{li}}=20$. The problem Hamiltonians for (a) and (b) correspond to Figs. 5 and 5, respectively.

Figure 7

Time evolution of the population $f_g\left(s\right)={\left|\langle {\varphi }_0|\mathrm{\Psi }\left(s\right)\rangle \right|}^2$ of the instantaneous ground state for NN-type and FC-type driving Hamiltonians. Annealing time is ${\tau }_{\mathrm{li}}=20$. The problem Hamiltonians for (a) and (b) correspond to Figs. 5 and 5, respectively.

Figure 8

Population distributions in a low-energy range for (a) NN-type and (b) FC-type driving Hamiltonians. The problem Hamiltonian corresponds to Fig. 5. Annealing time is ${\tau }_{\mathrm{li}}=20$. Energy is measured in units of $J$.