  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.
