From Electron Glasses to Quantum Machine Learning: A Study in Quadratic Unconstrained Binary Optimization

Abstract

Quadratic unconstrained binary optimization (QUBO) problems are of paramount importance in scientific and industrial applications as many interesting non-deterministic polynomial (NP)- hard problems can be mapped to them. QUBO is a subset of combinatorial optimization in which one seeks the global minimum of an objective function within a finite by occasionally towering set of possible configurations. Many simplistic algorithms, such as the gradient descent, fail to solve hard QUBO problems within a reasonable time frame as they find themselves lingering through the myriad of valleys and hills, hardly ever advancing toward the true ground state. Hence, designing new heuristics that can efficiently find solutions to such problems, as well as studying new instances of them can be extremely fruitful. QUBO problems have also shown great utility in quantum computing applications via quantum annealing, which has proven to be a promising endeavor to demonstrate the superiority of quantum devices over their classical counterparts. This work is, therefore, dedicated to studying quadratic optimization problems from several perspectives. We develop and benchmark physics-inspired algorithms such as population annealing Monte Carlo and thermal cycling. Using the designed algorithms, we study electron glasses, an instance of hard QUBO problems. Here, we show numerically that a transition to a spin-glass phase occurs at extremely low temperatures, which previous numerical studies have not been able to capture. We also study another case of QUBO problems, where we investigate the distribution of spin avalanches in systems with quench disorder. We establish new quantities similar to the concept of natural time in Seismology used as a potential measure for predicting large earthquakes. Finally, we turn to another exciting application of QUBO, namely quantum machine learning, an effort to use quantum devices in order to perform artificial intelligence algorithms more efficiently. Here, in addition to showing the advantage of physics-inspired solvers over the conventional heuristics such as Ridge regression, we propose a new way to uncover the power of quantum annealers in conducting machine learning tasks.