Optimization through quantum annealing: theory and some applications

Quantum annealing is a promising tool for solving optimization problems, similar in some ways to the traditional ( classical) simulated annealing of Kirkpatrick et al. Simulated annealing takes advantage of thermal fluctuations in order to explore the optimization landscape of the problem at hand, whereas quantum annealing employs quantum fluctuations. Intriguingly, quantum annealing has been proved to be more effective than its classical counterpart in many applications. We illustrate the theory and the practical implementation of both classical and quantum annealing - highlighting the crucial differences between these two methods - by means of results recently obtained in experiments, in simple toy-models, and more challenging combinatorial optimization problems ( namely, Random Ising model and Travelling Salesman Problem). The techniques used to implement quantum and classical annealing are either deterministic evolutions, for the simplest models, or Monte Carlo approaches, for harder optimization tasks. We discuss the pro and cons of these approaches and their possible connections to the landscape of the problem addressed.

On the solvability of Hamilton's equations in Hilbert spaces

We construct a bounded function $H : l_2\times l_2 \to R$ with continuous Frechet derivative such that for any $q_0\in l_2$ the Cauchy problem $\dot p= - {\partial H\over\partial q}$, $\dot q={\partial H\over\partial p}$, $p(0) = 0$, q(0) = q_0$ has no solutions in any neighborhood of zero in R.

Sound Synthesis for Contact-Driven Musical Instruments via Discretisation of Hamilton's Equations

Physical modelling of musical instruments involves studying nonlinear interactions between parts of the instrument. These can pose several difficulties concerning the accuracy and stability of numerical algorithms. In particular, when the underlying forces are non-analytic functions of the phase-space variables, a stability proof can only be obtained in limited cases. An approach has been recently presented by the authors, leading to unconditionally stable simulations for lumped collision models. In that study, discretisation of Hamilton’s equations instead of the usual Newton’s equation of motion yields a numerical scheme that can be proven to be energy conserving. In this paper, the above approach is extended to collisions of distributed objects. Namely, the interaction of an ideal string with a flat barrier is considered. The problem is formulated within the Hamiltonian framework and subsequently discretised. The resulting nonlinearmatrix equation can be shown to possess a unique solution, that enables the update of the algorithm. Energy conservation and thus numerical stability follows in a way similar to the lumped collision model. The existence of an analytic description of this interaction allows the validation of the model’s accuracy. The proposed methodology can be used in sound synthesis applications involving musical instruments where collisions occur either in a confined (e.g. hammer-string interaction, mallet impact) or in a distributed region (e.g. string-bridge or reed-mouthpiece interaction).

Directed Selection using Reinforcement Learning for the Examination Timetabling Problem

Traditional heuristic approaches to the Examination Timetabling Problem normally utilize a stochastic method during Optimization for the selection of the next examination to be considered for timetabling within the neighbourhood search process. This paper presents a technique whereby the stochastic method has been augmented with information from a weighted list gathered during the initial adaptive construction phase, with the purpose of intelligently directing examination selection. In addition, a Reinforcement Learning technique has been adapted to identify the most effective portions of the weighted list in terms of facilitating the greatest potential for overall solution improvement. The technique is tested against the 2007 International Timetabling Competition datasets with solutions generated within a time frame specified by the competition organizers. The results generated are better than those of the competition winner in seven of the twelve examinations, while being competitive for the remaining five examinations. This paper also shows experimentally how using reinforcement learning has improved upon our previous technique.