Disorder-assisted graph coloring on quantum annealers
arXiv:1903.07056 · doi:10.1103/PhysRevA.100.062304
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.
arXiv comment7 pages, 5 figures
References in corpus (33)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- 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
- Defining and detecting quantum speedup
- Quantum Computation by Adiabatic Evolution
- Experimental signature of programmable quantum annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Quantum Optimization of Fully-Connected Spin Glasses
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Entanglement in a quantum annealing processor
- Experimental Demonstration of a Robust and Scalable Flux Qubit
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- MAX 2-SAT with up to 108 qubits
- Unraveling Quantum Annealers using Classical Hardness
- Numerical approaches to time evolution of complex quantum systems
- Quantum annealing for the number partitioning problem using a tunable spin glass of ions
- Quantum fluctuation theorem to benchmark quantum annealers
- Analog Errors in Ising Machines
- Constrained quantum annealing of graph coloring
- Quantum neural networks to simulate many-body quantum systems
- Disorder-assisted distribution of entanglement in spin chains
- Analog Nature of Quantum Adiabatic Unstructured Search
- Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
- Disorder-assisted quantum transport in suboptimal decoherence regimes
- GPU Based Parallel Ising Computing for Combinatorial Optimization Problems in VLSI Physical Design
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