The performance of a D-Wave Vesuvius quantum annealer was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum c
oupling strength to increase with problem size. As a result, larger instances are subject to amplified analog control error, and are effectively annealed at higher temperatures in both hardware and software. We generate similar constraint satisfaction instances with limited range of coupling strength and perform a similar comparison to classical algorithms. On these instances the D-Wave Vesuvius processor, run with a fixed 20$mu$s anneal time, shows a scaling advantage over the software solvers for the hardest regime studied. This scaling advantage opens the possibility of quantum speedup on these problems. Our results support the hypothesis that performance of D-Wave Vesuvius processors is heavily influenced by analog control error, which can be reduced and mitigated as the technology matures.
The second authors $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chi leq lceil frac 12 (Delta+1+omega)rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem
of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $chi$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.
In 1998 the second author proved that there is an $epsilon>0$ such that every graph satisfies $chi leq lceil (1-epsilon)(Delta+1)+epsilonomegarceil$. The first author recently proved that any graph satisfying $omega > frac 23(Delta+1)$ contains a sta
ble set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Halls Theorem, Brooks Theorem, the Lovasz Local Lemma, and Talagrands Inequality.
I show that extreme beaming factors $b$ are not needed to explain ULXs as stellar--mass binaries. For neutron star accretors one typically requires $b sim 0.13$, and for black holes almost no beaming ($b sim 0.8$). The main reason for the high appare
nt luminosity is the logarithmic increase in the limiting luminosity for super--Eddington accretion. The required accretion rates are explicable in terms of thermal--timescale mass transfer from donor stars of mass $6 - 10msun$, or possibly transient outbursts. Beaming factors $la 0.1$ would be needed to explain luminosities significantly above $10^{40}L_{40}$ erg s$^{-1}$, but these requirements are relaxed somewhat if the accreting matter has low hydrogen content.
