Disorder-assisted graph coloring on quantum annealers

Abstract

We are at the verge of a new era, which will be dominated by Noisy Intermediate-Scale Quantum Devices. Prototypical examples for these new technologies are present-day quantum annealers. In the present work, we investigate to what extent static disorder generated by an external source of noise does not have to be detrimental, but can actually assist quantum annealers in achieving better performance. In particular, we analyze the graph coloring problem that can be solved on a sparse topology (i.e. chimera graph) via suitable embedding. We show that specifically tailored disorder can enhance the fidelity of the annealing process and thus increase the overall performance of the annealer.

7 pages, 5 figures

References in corpus (6)

• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Pegasus: The second connectivity graph for large-scale quantum annealing hardware
• Disorder-assisted distribution of entanglement in $XY$ spin chains
• Analog Nature of Quantum Adiabatic Unstructured Search
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks

Cited by in corpus (6)

• Kibble-Zurek scaling in quantum speed limits for shortcuts to adiabaticity
• The three phases of quantum annealing: fast, slow, and very slow
• Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
• BBQ-mIS: a parallel quantum algorithm for graph coloring problems
• Quantum annealing in the NISQ era: railway conflict management
• Effects of Graph Network Connections on The Efficiency of Quantum Annealing