The Sherrington-Kirkpatrick model with random ±1 couplings is programmed on the D-Wave Two annealer featuring 509 qubits interacting on a Chimera-type graph. The performance of the optimizer compares and correlates to simulated annealing. When considering the effect of the static noise, which degrades the performance of the annealer, one can estimate an improvement on the comparative scaling of the two methods in favor of the D-Wave machine. The optimal choice of parameters of the embedding on the Chimera graph is shown to be associated to the emergence of the spin-glass critical temperature of the embedded problem. NP problems, such as classical paradigmatic computer science problems [1] as well as practical engineering problems [2] can often be formulated efficiently as Quadratic Unconstrained Binary Optimizations (QUBO). These computational challenges can be seen as the task of finding the ground states of a disordered Ising spin glass often defined on a potentially highly-connected graph [3] . One tantalizing approach to solve QUBOs in their Ising formulation is provided by programmable quantum annealing. While the founding principles of the technique have been investigated numerically [4] , analytically [5] and experimentally [6] in the last decade, the disordered, interacting, time-dependent and open nature of the many-body problem makes it very hard to draw universal conclusions about the power of the technique [7] . One very recent development that boosted scientific activity in this field has been the commercialization of D-Wave Two optimizers, which implements the annealing approach by means of a solid state architecture consisting of hundreds of interlaced superconducting flux qubits [8] . While the manufacturing methods and the computing technology are well documented, understanding the power of the machine is a formidable challenge for the aforementioned reasons, with the additional hindrance that the heavy integration of the circuitry entails the existence of static and dynamical sources of noise that are in part unknown. For these reasons groups around the world have started to experimentally benchmark the machine [9-11], nurturing a lively discussion on whether the device is making functional use of quantum mechanics for computation [12] and how to properly measure speedups between different computational/experimental algorithms [13, 14] . On a more pragmatic level, the chip was also tested to evaluate its performance on toy-application problems in the fields of network diagnostics [15] [19] . One typical occurrence in applied problems is when the QUBO to be solved is derived from a linear binary optimization problem with large number of constraints such as enforced equalities or inequalities between linear relations of variables. In this case the resulting penalty terms in the objective function form intersecting cliques whose minimization might be a hard computational problem for classical algorithms such as simulated annealing. Motivated by the great value of quantifying the power of quantum optimization on valuable applications, in this work we report on the optimal programming guidelines and performance expectation of the D-Wave Two Vesuvius chip, applied to problems defined on fully-connected graphs with random couplings in the absence of longitudinal local fields. This Hamiltonian corresponds to the Sherrington-Kirkpatrick Model (SKM) with couplings randomized from a bimodal distribution of values ±1 [20] . The SKM is directly related to the graph partitioning problem [3] which is known to be NP-hard, and supports a spin-glass phase at finite temperature with transverse fields. For these reasons, it represents one of the most interesting benchmarks to evaluate the performance of the optimizer on structured problems. Moreover, the encoding of the SKM on the D-Wave hardware has very interesting symmetry properties, allowing us to elegantly investigate general procedures common to all structured optimizations on annealers, such as the parameter setting of embedding and the error-correction, which in the general case require heuristic numerical preprocessing [21] . The D-Wave Two "Vesuvius" chip hosted at NASA Ames Research Center features 509 working flux-qubits connected by 1455 tunable composite qubits acting as Ising-interaction couplings [22] , arranged in a non-planar lattice known as a "Chimera graph" [23] . In order to implement general Hamiltonians which are defined on arbitrary graphs, it is customary to employ the graph-minor embedding [24] technique. This procedure consists of finding a set of connected subgraphs (logical bits or LB, corresponding to different colors in Fig. 1 ) of the original graph such that each LB can be associated to a node arXiv:1406.7553v1 [cond-mat.dis-nn]
Of particular relevance is work on optimization of fully-connected graphs, such as the ones used to map the ML problem REF ; the results of which showed that QA performance could match the most highly optimized simulated annealing code run on the latest Intel processors.
Quantum Optimization of Fully-Connected Spin Glasses
Phys. Rev. X 5, 031040 (2015)
Physics