Practical engineering of hard spin-glass instances
Resumen: Recent 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.
Idioma: Inglés
DOI: 10.1103/PhysRevA.94.012320
Año: 2016
Publicado en: Physical review. A, Atomic, molecular, and optical physics 94, 1 (2016), 012320 [10 pp]
ISSN: 1050-2947

Factor impacto SCIMAGO: 1.482 - Atomic and Molecular Physics, and Optics (Q1)

Financiación: info:eu-repo/grantAgreement/ES/MINECO/FIS2012-35719-C02
Financiación: info:eu-repo/grantAgreement/ES/MINECO/FIS2015-65078-C2-1-P
Tipo y forma: Artículo (Versión definitiva)

Creative Commons Debe reconocer adecuadamente la autoría, proporcionar un enlace a la licencia e indicar si se han realizado cambios. Puede hacerlo de cualquier manera razonable, pero no de una manera que sugiera que tiene el apoyo del licenciador o lo recibe por el uso que hace. No puede utilizar el material para una finalidad comercial. Si remezcla, transforma o crea a partir del material, no puede difundir el material modificado.


Exportado de SIDERAL (2020-02-21-13:29:05)


Visitas y descargas

Este artículo se encuentra en las siguientes colecciones:
Artículos



 Registro creado el 2017-03-23, última modificación el 2020-02-21


Versión publicada:
 PDF
Valore este documento:

Rate this document:
1
2
3
 
(Sin ninguna reseña)