Simulated Annealing (SA) is a probabilistic method calculating the global minimum of an objective function that may possess several local minima. Basically it works by emulating the physical process whereby a solid is slowly cooled so that when eventually its structure is “frozen”, a minimum energy configuration is reached.
Quantum Annealing (QA) has the same goal of simulated annealing, i.e. finding the global minimum of a given objective function over a given set of candidate solutions (in a certain search space), but this time the adopted process is based on quantum fluctuations. A “state” (i.e. a candidate solution) is randomly replaced by a randomly selected neighbor state if the latter has a lower “energy” (i.e. the value of the objective function). The process is controlled by a “tunneling field strength”, a parameter that determines the extent of the neighborhood of states explored, i.e. the mean distance between the next candidate state and the current candidate state. In other words QA has the possibility of quantum tunneling across the width of a barriers between states, instead of just scaling their heights (as in simulated annealing) with a thermal jump.
There is theoretical and experimental evidence of the advantage of solving classical optimization problems using QA over SA.
In 2011, D-Wave Systems announced the first commercial quantum annealer: D-Wave One. The company claims this system uses a 128 quantum bits (qubit) processor chipset, specifically designed for quantum annealing. Essentially, it involves preparing some sub-group of the qubits into their lowest-possible energy state, or ‘ground state’, and then performing a series of operations to put it into a more complex ground state that can’t be easily solved using classical methods.
It has been recently announced by Nature News Blog that D-Wave quantum computer can solve the protein folding problem, which is very complex (for traditional computation). The model consisted of mathematical representations of amino acids in a lattice, connected by different interaction strengths. The D-Wave computer found the lowest configurations of amino acids and interactions, which corresponds to the most economical folding of the proteins (the global minimum of the free-energy function is conjectured to be the native functional conformation of the protein).
Actually, according to the paper, 10,000 measurements using an 81 qubit version of the experiment gave the correct answer just 13 times (checked with a conventional computer). Even though this problem still can be solved on a classical computer by exact enumeration, it is remarkable that the device anneals to the ground state of a search space of 281 possible computational outcomes.
This study provides a proof-of-principle that optimization of biophysical problems such as protein folding can be studied using quantum mechanical devices. This paves the way towards studying optimization problems using quantum devices in several domains, also in future Internet (see my next post on that).