Quantum annealing speedup of embedded problems via suppression of Griffiths singularities

Abstract

Optimal parameter setting for applications problems embedded into hardware graphs is key to practical quantum annealers (QA). Embedding chains typically crop up as harmful Griffiths phases, but can be used as a resource as we show here: to balance out singularities in the logical problem changing its universality class. Smart choice of embedding parameters reduces annealing times for random Ising chain from $O(exp[c\sqrt{N}])$ to $O(N^2)$. Dramatic reduction in time-to-solution for QA is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues.

arXiv comment11 pages [5 pages (3 figs) main text+references; 5 pages (2 figs) appendix; 1 page code listing]

References in corpus (21)

• 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
• Dynamics of a Quantum Phase Transition
• Quantum Annealing and Analog Quantum Computation
• Dynamics of quantum phase transition: exact solution in quantum Ising model
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Quantum Optimization of Fully-Connected Spin Glasses
• Error corrected quantum annealing with hundreds of qubits
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Dynamics of a quantum phase transition in the random Ising model
• Quantum annealing correction for random Ising problems
• Quantum Annealing Correction with Minor Embedding
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Quantum annealing correction at finite temperature: ferromagnetic $p$-spin models
• Quantum annealing via environment-mediated quantum diffusion
• Inhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Minimizing minor embedding energy: an application in quantum annealing

Cited by in corpus (5)

• Quantum Annealing: An Overview
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Reducing defect production in random transverse-field Ising chains by inhomogeneous driving fields
• Exact bounds on the energy gap of transverse-field Ising chains by mapping to random walks
• Exact bounds for dynamical critical exponents of transverse-field Ising chains with a correlated disorder