Constrained quantum annealing of graph coloring
arXiv:1806.05782 · doi:10.1103/PhysRevA.98.022301
Abstract
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.
arXiv comment6 pages, 8 figures
References in corpus (20)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Quantum Annealing and Analog Quantum Computation
- Phase Transitions in the Coloring of Random Graphs
- Anderson localization casts clouds over adiabatic quantum optimization
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum annealing of the Traveling Salesman Problem
- Experimental determination of Ramsey numbers
- Quantum Annealing Correction with Minor Embedding
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Quantum Annealing for Constrained Optimization
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
- Ramsey numbers and adiabatic quantum computing
- Residual Energies after Slow Quantum Annealing
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Driver Hamiltonians for constrained optimization in quantum annealing
- Graph isomorphism and adiabatic quantum computing
Cited by in corpus (14)
- A Grover search-based algorithm for the list coloring problem
- Quantum pricing-based column-generation framework for hard combinatorial problems
- Fermionic Quantum Approximate Optimization Algorithm
- Quantum annealing with twisted fields
- Collective dynamics of phase-repulsive oscillators solves graph coloring problem
- A theory of non-equilibrium local search on random satisfaction problems
- Disorder-assisted graph coloring on quantum annealers
- Dynamical chaotic phases and constrained quantum dynamics
- Localization in the constrained quantum annealing of graph coloring
- BBQ-mIS: a parallel quantum algorithm for graph coloring problems
- The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
- Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
- Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
- Approximate Approximation on a Quantum Annealer