  In this paper we introduce and formalize Substochastic Monte Carlo (SSMC)
algorithms. These algorithms, originally intended to be a better classical foil
to quantum annealing than simulated annealing, prove to be worthy optimization
algorithms in their own right. In SSMC, a population of walkers is initialized
according to a known distribution on an arbitrary search space and varied into
the solution of some optimization problem of interest. The first argument of
this paper shows how an existing classical algorithm, "Go-With-The-Winners"
(GWW), is a limiting case of SSMC when restricted to binary search and
particular driving dynamics.
  Although limiting to GWW, SSMC is more general. We show that (1) GWW can be
efficiently simulated within the SSMC framework, (2) SSMC can be exponentially
faster than GWW, (3) by naturally incorporating structural information, SSMC
can exponentially outperform the quantum algorithm that first inspired it, and
(4) SSMC exhibits desirable search features in general spaces. Our approach
combines ideas from genetic algorithms (GWW), theoretical probability
(Fleming-Viot processes), and quantum computing. Not only do we demonstrate
that SSMC is often more efficient than competing algorithms, but we also hope
that our results connecting these disciplines will impact each independently.
An implemented version of SSMC has previously enjoyed some success as a
competitive optimization algorithm for Max-$k$-SAT.
