Optimization with spin glass models

Abstract

(English) With applicability on almost every aspect of our lives, optimization problems are ubiquitous to a broad range of fields within both scientific research and industrial environments. As such, these are growing in size and complexity at a fast pace, and are only expected to continue to do so. Accordingly, the urgency for better methods that can yield more optimal solutions in shorter times is increasing and, while the development of quantum computing technologies that are capable of tackling these problems evolves steadily, it does so too slowly for the challenges that nowadays society's demands represent. Consequently, a lot of effort is being invested to further develop classical methods and machines that are specially designed to solve optimization problems of relevant enough sizes. The present thesis is framed within this paradigm: classical optimization techniques are studied from various different perspectives, with the goal of improving their efficiency.

To this end, we first dive into basic concerns related to the physical properties of the systems that allow for the convenient formulation of industrially-relevant optimization problems, namely spin glasses with quenched disorders. The understanding of such properties is of utmost importance for the correct designing of the annealing schedules used by thermally-based optimization methods. We then study the impact that the hidden correlations of the pseudo random number streams used in their simulations have in the results by comparing simulations using PRNGs of various qualities and perfectly random QRNGs. To conclude, we investigate novel ways, inspired by quantum-mechanical systems, to efficiently navigate the energy landscapes of spin glasses in classical algorithms, which has the potential of preventing the simulations getting stuck into local energy minima and thus reaching more optimal solutions.

(Català) Amb aplicacions en gairebé tots els aspectes de les nostres vides, els problemes d’optimització són omnipresents en un rang molt ample de camps pertanyents tant a la recerca científica com als ambients industrials. Com a tals, aquests problemes estan creixent en mida i en complexitat a un ritme accelerat, i no s’espera que deixin de fer-ho. Així doncs, la urgència per obtenir mètodes capaços de trobar solucions més òptimes en menys temps no para de créixer i, mentre que el desenvolupament de les tecnologies de computació quàntica capaces d’afrontar aquests problemes avança sense pausa, ho fa a un ritme massa lent per als reptes que les necessitats de la societat actual representen. Conseqüentment, actualment una gran quantitat d’esforços està essent invertida en millorar els mètodes de resolució clàssics i les plataformes específicament dissenyades per a executar-los, per tal de poder resoldre problemes d’optimització de grandàries suficientment rellevants. La present tesi està emmarcada en aquest paradigma: s’estudien tècniques d’optimització clàssiques des de diferents perspectives, amb l’objectiu d’incrementar-ne la seva eficiència. Amb aquesta finalitat, en primer lloc ens endinsem en qüestions relacionades amb les propietats físiques dels sistemes que permeten formular problemes d’optimització rellevants des del punt de vista industrial en un llenguatge matemàtic convenient: els cristalls de spín amb acoblaments fixes. Entendre’n les seves propietats és de màxima importància per a un disseny apropiat dels procediments de refredament utilitzats en els algoritmes d’optimització basats en la simulació de processos tèrmics. Seguidament s’estudia l’impacte que les correlacions ocultes en les seqüències de nombres pseudoaleatoris utilitzats en aquestes simulacions tenen en els seus resultats, comparant simulacions que utilitzen generadors pseudoaleatoris de diverses qualitats i un generador de nombres aleatoris quàntic. Per finalitzar, s’investiguen nous mecanismes, inspirats en processos de caràcter quàntic, de millorar la forma en què els algoritmes clàssics naveguen els perfils d’energia dels cristalls d’espín, amb la finalitat d’evitar que les simulacions quedin atrapades en mínims d’energia locals i així obtenint solucions més òptimes.