Simulated Annealing is a popular optimization heuristic that is based on stochastic Markov Chain Monte Carlo (MCMC) methods. Recently, a quantum computing-based MCMC implementation called Quantum-enhanced Markov Chain Monte Carlo (QMCMC) has been shown to have a theoretical performance advantage over classical MCMC approaches. This thesis builds on the general idea of QMCMC to develop three quantum-enhanced variations of Simulated Annealing with the goal of realizing this performance advantage within a concrete optimization use case, namely the NP-hard multiple knapsack problem.
Two of these methods are directly based on the original QMCMC concept, while one is rooted in a different quantum optimization approach for knapsack problems, the Quantum Tree Generator (QTG), which is generalised to the multiple knapsack application and modified into a viable MCMC method.
Experimental evaluations of all three presented methods show varying degrees of promise, with the QTG-based method clearly beating out the other approaches as well as classical reference methods.