<p>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 <a href="http://arxiv.org/abs/1401.2910" rel="nofollow">comparison between quantum Monte Carlo simulation and D-Wave machines</a> were conducted, showing that the scaling behavior of the D-Wave chip did not indicate anything special. Around the same time, <a href="http://arxiv.org/abs/1401.1546" rel="nofollow">Katzgraber and coauthors</a> 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).</p>

<p>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.</p>

<p>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.</p>

<hr>

<p><strong>[*]</strong> 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:</p>

<p>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.</p>

<p>$$
H(s) = s H_i + (1-s) H_p
$$</p>

<p>where $s \in [0,1]$. Details about AQC: <a href="http://arxiv.org/abs/quant-ph/0001106v1" rel="nofollow">http://arxiv.org/abs/quant-ph/0001106v1</a></p>

CC BY-SA 3.0
2014-05-03T14:52:15.213Z
(?) this question seems to be about how to come up with "hard" random QUBO instances or hard contrived instances and this is indeed a common difficulty because in some sense most instances chosen at "random" are not "hard". there is a lot of theory around this issue. see eg old DIMACS competitions for SAT for theory on how to create "presumably" hard instances. another angle is studying the SAT transition point which is thought to "carry over" into all other NP complete problems and computing models, QUBO included. another common model for creating hard instances is factoring.
vzn
<reference-request><optimization><quantum-computing>
Generating quadratic optimization problems amenable to quantum annealing
hadsed
# Generating quadratic optimization problems amenable to quantum annealing

(Asked by: username_0 on 2014-04-19)

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](http://arxiv.org/abs/1401.2910) were conducted, showing that the scaling behavior of the D-Wave chip did not indicate anything special. Around the same time, [Katzgraber and coauthors](http://arxiv.org/abs/1401.1546) 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>

**Tags:** reference-request, optimization, quantum-computing
> **Comments:**
> **username_1**: (?) this question seems to be about how to come up with "hard" random QUBO instances or hard contrived instances and this is indeed a common difficulty because in some sense most instances chosen at "random" are not "hard". there is a lot of theory around this issue. see eg old DIMACS competitions for SAT for theory on how to create "presumably" hard instances. another angle is studying the SAT transition point which is thought to "carry over" into all other NP complete problems and computing models, QUBO included. another common model for creating hard instances is factoring.  

---

## 0 answers

