  We lay the foundation for a benchmarking methodology for assessing current
and future quantum computers. We pose and begin addressing fundamental
questions about how to fairly compare computational devices at vastly different
stages of technological maturity. We critically evaluate and offer our own
contributions to current quantum benchmarking efforts, in particular those
involving adiabatic quantum computation and the Adiabatic Quantum Optimizers
produced by D-Wave Systems, Inc. We find that the performance of D-Wave's
Adiabatic Quantum Optimizers scales roughly on par with classical approaches
for some hard combinatorial optimization problems; however, architectural
limitations of D-Wave devices present a significant hurdle in evaluating
real-world applications. In addition to identifying and isolating such
limitations, we develop algorithmic tools for circumventing these limitations
on future D-Wave devices, assuming they continue to grow and mature at an
exponential rate for the next several years.
