Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a comparison between quantum Monte Carlo simulation and D-Wave machines were conducted, showing that the scaling behavior of the D-Wave chip did not indicate anything special. Around the same time, Katzgraber and coauthors argue that random instances are not too useful for testing quantum speedup. They go on to propose some things specifically for Chimera spin-glasses (the Chimera graph is the name of the hardware graph used in the D-Wave chips).
What Katzgraber says makes a lot of sense--we should focus on the hard problems and see if there's anything interesting. But how to come up with these instances? There is an isomorphism between the Ising spin-glass model and quadratic unconstrained binary optimization problems (QUBOs), so you could ask the question both ways.
I am open to: any (possibly small) insights, corrections of my misconceptions, keywords, ideas, or anything else you can contribute. Also I wonder if there are ideas in the AQC context for this that I've just simply missed or haven't understood.
[*] As a matter of courtesy, I thought I should include a brief description of the quantum annealing problem that I used in my other question:
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian $H_i$ and "anneal" (adiabatically perturb) towards $H_p$, i.e.
$$ H(s) = s H_i + (1-s) H_p $$
where $s \in [0,1]$. Details about AQC: http://arxiv.org/abs/quant-ph/0001106v1