  Hard optimization problems are often approached by finding approximate
solutions. Here, we highlight the concept of proportional sampling and discuss
how it can be used to improve the performance of stochastic algorithms for
optimization. We introduce an NP-Hard problem called Max-Haf and show that
Gaussian boson sampling (GBS) can be used to enhance any stochastic algorithm
for this problem. These results are applied by enhancing the random search,
simulated annealing, and greedy algorithms. With numerical simulations, we
confirm that all algorithms are improved when employing GBS, and that
GBS-enhanced random search performs the best despite being the one with the
simplest underlying classical routine.
