-
Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization
Authors:
Masoud Mohseni,
Daniel Eppens,
Johan Strumpfer,
Raffaele Marino,
Vasil Denchev,
Alan K. Ho,
Sergei V. Isakov,
Sergio Boixo,
Federico Ricci-Tersenghi,
Hartmut Neven
Abstract:
Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computati…
▽ More
Optimizing highly complex cost/energy functions over discrete variables is at the heart of many open problems across different scientific disciplines and industries. A major obstacle is the emergence of many-body effects among certain subsets of variables in hard instances leading to critical slowing down or collective freezing for known stochastic local search strategies. An exponential computational effort is generally required to unfreeze such variables and explore other unseen regions of the configuration space. Here, we introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy that can efficiently learn key instance-wise geometrical features of the cost function. That information is employed on-the-fly to construct spatially inhomogeneous thermal fluctuations for collectively unfreezing variables at various length scales, circumventing costly exploration versus exploitation trade-offs. We apply our algorithm to two of the most challenging combinatorial optimization problems: random k-satisfiability (k-SAT) near the computational phase transitions and Quadratic Assignment Problems (QAP). We observe significant speedup and robustness over both specialized deterministic solvers and generic stochastic solvers. In particular, for 90% of random 4-SAT instances we find solutions that are inaccessible for the best specialized deterministic algorithm known as Survey Propagation (SP) with an order of magnitude improvement in the quality of solutions for the hardest 10% instances. We also demonstrate two orders of magnitude improvement in time-to-solution over the state-of-the-art generic stochastic solver known as Adaptive Parallel Tempering (APT).
△ Less
Submitted 26 November, 2021;
originally announced November 2021.
-
Sampling diverse near-optimal solutions via algorithmic quantum annealing
Authors:
Masoud Mohseni,
Marek M. Rams,
Sergei V. Isakov,
Daniel Eppens,
Susanne Pielawa,
Johan Strumpfer,
Sergio Boixo,
Hartmut Neven
Abstract:
Sampling a diverse set of high-quality solutions for hard optimization problems is of great practical relevance in many scientific disciplines and applications, such as artificial intelligence and operations research. One of the main open problems is the lack of ergodicity, or mode collapse, for typical stochastic solvers based on Monte Carlo techniques leading to poor generalization or lack of ro…
▽ More
Sampling a diverse set of high-quality solutions for hard optimization problems is of great practical relevance in many scientific disciplines and applications, such as artificial intelligence and operations research. One of the main open problems is the lack of ergodicity, or mode collapse, for typical stochastic solvers based on Monte Carlo techniques leading to poor generalization or lack of robustness to uncertainties. Currently, there is no universal metric to quantify such performance deficiencies across various solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems. Among others, it allows benchmarking solver performance by a required time-to-diversity (TTD), a generalization of often used time-to-solution (TTS). We illustrate this metric by comparing the sampling power of various quantum annealing strategies. In particular, we show that the inhomogeneous quantum annealing schedules can redistribute and suppress the emergence of topological defects by controlling space-time separated critical fronts, leading to an advantage over standard quantum annealing schedules with respect to both TTS and TTD for finding rare solutions. Using path-integral Monte Carlo simulations for up to 1600 qubits, we demonstrate that nonequilibrium driving of quantum fluctuations, guided by efficient approximate tensor network contractions, can significantly reduce the fraction of hard instances for random frustrated 2D spin-glasses with local fields. Specifically, we observe that by creating a class of algorithmic quantum phase transitions, the diversity of solutions can be enhanced by up to 40% with the fraction of hard-to-sample instances reducing by more than 25%.
△ Less
Submitted 11 January, 2024; v1 submitted 20 October, 2021;
originally announced October 2021.
-
Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
Authors:
Masoud Mohseni,
Johan Strumpfer,
Marek M. Rams
Abstract:
We introduce a phenomenological theory for many-body control of critical phenomena by engineering causally-induced gaps for quantum Hamiltonian systems. The core mechanisms are controlling information flow within and/or between clusters that are created near a quantum critical point. To this end, we construct inhomogeneous quantum phase transitions via designing spatio-temporal quantum fluctuation…
▽ More
We introduce a phenomenological theory for many-body control of critical phenomena by engineering causally-induced gaps for quantum Hamiltonian systems. The core mechanisms are controlling information flow within and/or between clusters that are created near a quantum critical point. To this end, we construct inhomogeneous quantum phase transitions via designing spatio-temporal quantum fluctuations. We show how non-equilibrium evolution of disordered quantum systems can create new effective correlation length scales and effective dynamical critical exponents. In particular, we construct a class of causally-induced non-adiabatic quantum annealing transitions for strongly disordered quantum Ising chains leading to exponential suppression of topological defects beyond standard Kibble-Zurek predictions. Using exact numerical techniques for 1D quantum Hamiltonian systems, we demonstrate that our approach exponentially outperform adiabatic quantum computing. Using Strong-Disorder Renormalization Group (SDRG), we demonstrate the universality of inhomogeneous quantum critical dynamics and exhibit the causal zones reconstructions during SDRG flow. We derive a scaling relation for minimal causal gaps showing they narrow more slowly than any polynomial with increasing size of system, in contrast to stretched exponential scaling in standard adiabatic evolution. Furthermore, we demonstrate similar scaling behaviour for random cluster-Ising Hamiltonians with higher order interactions.
△ Less
Submitted 19 October, 2018; v1 submitted 29 April, 2018;
originally announced April 2018.
-
Search for the Wreckage of Air France Flight AF 447
Authors:
Lawrence D. Stone,
Colleen M. Keller,
Thomas M. Kratzke,
Johan P. Strumpfer
Abstract:
In the early morning hours of June 1, 2009, during a flight from Rio de Janeiro to Paris, Air France Flight AF 447 disappeared during stormy weather over a remote part of the Atlantic carrying 228 passengers and crew to their deaths. After two years of unsuccessful search, the authors were asked by the French Bureau d'Enquêtes et d'Analyses pour la sécurité de l'aviation to develop a probability d…
▽ More
In the early morning hours of June 1, 2009, during a flight from Rio de Janeiro to Paris, Air France Flight AF 447 disappeared during stormy weather over a remote part of the Atlantic carrying 228 passengers and crew to their deaths. After two years of unsuccessful search, the authors were asked by the French Bureau d'Enquêtes et d'Analyses pour la sécurité de l'aviation to develop a probability distribution for the location of the wreckage that accounted for all information about the crash location as well as for previous search efforts. We used a Bayesian procedure developed for search planning to produce the posterior target location distribution. This distribution was used to guide the search in the third year, and the wreckage was found with one week of undersea search. In this paper we discuss why Bayesian analysis is ideally suited to solving this problem, review previous non-Bayesian efforts, and describe the methodology used to produce the posterior probability distribution for the location of the wreck.
△ Less
Submitted 19 May, 2014;
originally announced May 2014.
-
Exteneded Longitudinal Scaling and the Thermal Model
Authors:
J. Cleymans,
J. Strümpfer,
L. Turko
Abstract:
The property of extended longitudinal scaling of rapidity distributions was noticed recently over a broad range of beam energies. It is shown here that this property is consistent with predictions of the statistical thermal model up to the highest RHIC beam energies, however, we expect that at LHC energies the rapidity distribution of produced particles will violate extended longitudinal scaling…
▽ More
The property of extended longitudinal scaling of rapidity distributions was noticed recently over a broad range of beam energies. It is shown here that this property is consistent with predictions of the statistical thermal model up to the highest RHIC beam energies, however, we expect that at LHC energies the rapidity distribution of produced particles will violate extended longitudinal scaling.
△ Less
Submitted 16 July, 2008; v1 submitted 14 December, 2007;
originally announced December 2007.
-
Rapidity Variation of Thermal Parameters at SPS and RHIC
Authors:
F. Becattini,
J. Cleymans,
J. Strumpfer
Abstract:
The rapidity dependence of the chemical freeze-out thermal parameters $T$ and $μ_B$ are determined at the highest RHIC and SPS energies.
These show a systematic behavior towards an increase in $μ_B$ away from mid-rapidity and a corresponding decrease in the temperature $T$.
The rapidity dependence of the chemical freeze-out thermal parameters $T$ and $μ_B$ are determined at the highest RHIC and SPS energies.
These show a systematic behavior towards an increase in $μ_B$ away from mid-rapidity and a corresponding decrease in the temperature $T$.
△ Less
Submitted 17 September, 2007;
originally announced September 2007.
