000060828 001__ 60828 000060828 005__ 20200221144254.0 000060828 0247_ $$2doi$$a10.1103/PhysRevA.94.012320 000060828 0248_ $$2sideral$$a96160 000060828 037__ $$aART-2016-96160 000060828 041__ $$aeng 000060828 100__ $$aMarshall, J. 000060828 245__ $$aPractical engineering of hard spin-glass instances 000060828 260__ $$c2016 000060828 5060_ $$aAccess copy available to the general public$$fUnrestricted 000060828 5203_ $$aRecent technological developments in the field of experimental quantum annealing have made prototypical annealing optimizers with hundreds of qubits commercially available. The experimental demonstration of a quantum speedup for optimization problems has since then become a coveted, albeit elusive goal. Recent studies have shown that the so far inconclusive results, regarding a quantum enhancement, may have been partly due to the benchmark problems used being unsuitable. In particular, these problems had inherently too simple a structure, allowing for both traditional resources and quantum annealers to solve them with no special efforts. The need therefore has arisen for the generation of harder benchmarks which would hopefully possess the discriminative power to separate classical scaling of performance with size from quantum. We introduce here a practical technique for the engineering of extremely hard spin-glass Ising-type problem instances that does not require “cherry picking” from large ensembles of randomly generated instances. We accomplish this by treating the generation of hard optimization problems itself as an optimization problem, for which we offer a heuristic algorithm that solves it. We demonstrate the genuine thermal hardness of our generated instances by examining them thermodynamically and analyzing their energy landscapes, as well as by testing the performance of various state-of-the-art algorithms on them. We argue that a proper characterization of the generated instances offers a practical, efficient way to properly benchmark experimental quantum annealers, as well as any other optimization algorithm. 000060828 536__ $$9info:eu-repo/grantAgreement/ES/MINECO/FIS2012-35719-C02$$9info:eu-repo/grantAgreement/ES/MINECO/FIS2015-65078-C2-1-P 000060828 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/ 000060828 592__ $$a1.482$$b2016 000060828 593__ $$aAtomic and Molecular Physics, and Optics$$c2016$$dQ1 000060828 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion 000060828 700__ $$0(orcid)0000-0002-3376-0327$$aMartin-Mayor, V. 000060828 700__ $$aHen, I. 000060828 773__ $$g94, 1 (2016), 012320 [10 pp]$$pPhys. rev., A At. mol. opt. phy.$$tPhysical review. A, Atomic, molecular, and optical physics$$x1050-2947 000060828 8564_ $$s717877$$uhttps://zaguan.unizar.es/record/60828/files/texto_completo.pdf$$yVersión publicada 000060828 8564_ $$s129380$$uhttps://zaguan.unizar.es/record/60828/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada 000060828 909CO $$ooai:zaguan.unizar.es:60828$$particulos$$pdriver 000060828 951__ $$a2020-02-21-13:29:05 000060828 980__ $$aARTICLE