  Benchmarking Quantum Process Units (QPU) at an application level usually
requires considering the whole programming stack of the quantum computer. One
critical task is the minor-embedding (resp. transpilation) step, which involves
space-time overheads for annealing-based (resp. gate-based) quantum computers.
This paper establishes a new protocol to generate graph instances with their
associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers
(QA). This set of favorable mappings is used to generate a wide diversity of
optimization problem instances. We use this method to benchmark QA on large
instances of unconstrained and constrained optimization problems and compare
the performance of the QPU with efficient classical solvers. The benchmark aims
to evaluate and quantify the key characteristics of instances that could
benefit from the use of a quantum computer. In this context, existing QA seem
best suited for unconstrained problems on instances with densities less than
$10\%$. For constrained problems, the penalty terms used to encode the hard
constraints restrict the performance of QA and suggest that these QPU will be
less efficient on these problems of comparable size.
