A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
arXiv:1807.11135 · doi:10.4204/EPTCS.273.1
Abstract
Quantum annealing has shown significant potential as an approach to near-term quantum computing. Despite promising progress towards obtaining a quantum speedup, quantum annealers are limited by the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding can be costly to perform and may destroy any computational speedup. Here we present a hybrid quantum-classical paradigm to help mitigate this limitation, and show how a raw speedup that is negated by the embedding time can nonetheless be exploited in certain circumstances. We illustrate this approach with initial results on a proof-of-concept implementation of an algorithm for the dynamically weighted maximum independent set problem.
arXiv commentIn Proceedings PC 2018, arXiv:1807.10563
References in corpus (13)
- Quantum Computing
- The theory of variational hybrid quantum-classical algorithms
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Quantum Computation by Adiabatic Evolution
- What is the Computational Value of Finite Range Tunneling?
- Probing for quantum speedup in spin glass problems with planted solutions
- Quantum Annealing Implementation of Job-Shop Scheduling
- Quantum Annealing Correction with Minor Embedding
- How "Quantum" is the D-Wave Machine?
- Benchmarking a quantum annealing processor with the time-to-target metric
- Algorithm engineering for a quantum annealing platform
- Performance of a quantum annealer on range-limited constraint satisfaction problems