  Despite rapid recent progress towards the development of quantum computers
capable of providing computational advantages over classical computers, it
seems likely that such computers will, initially at least, be required to run
in a hybrid quantum-classical regime. This realisation has led to interest in
hybrid quantum-classical algorithms allowing, for example, quantum computers to
solve large problems despite having very limited numbers of qubits. Here we
propose a hybrid paradigm for quantum annealers with the goal of mitigating a
different limitation of such devices: the need to embed problem instances
within the (often highly restricted) connectivity graph of the annealer. This
embedding process can be costly to perform and may destroy any computational
speedup. In order to solve many practical problems, it is moreover necessary to
perform many, often related, such embeddings. We will show how, for such
problems, a raw speedup that is negated by the embedding time can nonetheless
be exploited to give a real speedup. As a proof-of-concept example we present
an in-depth case study of a simple problem based on the maximum weight
independent set problem. Although we do not observe a quantum speedup
experimentally, the advantage of the hybrid approach is robustly verified,
showing how a potential quantum speedup may be exploited and encouraging
further efforts to apply the approach to problems of more practical interest.
