Quantum annealing

Quantum annealing is a metaheuristic for finding the global minimum of a given objective function over a given set of candidate solutions, by a process using quantum fluctuations. Quantum annealing is used for problems where the search space is discrete with many local minima, it was formulated in its present form by T. Kadowaki and H. Nishimori in "Quantum annealing in the transverse Ising model" though a proposal in a different form had been made by A. B. Finilla, M. A. Gomez, C. Sebenik and J. D. Doll, in "Quantum annealing: A new method for minimizing multidimensional functions". Quantum annealing starts from a quantum-mechanical superposition of all possible states with equal weights; the system evolves following the time-dependent Schrödinger equation, a natural quantum-mechanical evolution of physical systems. The amplitudes of all candidate states keep changing, realizing a quantum parallelism, according to the time-dependent strength of the transverse field, which causes quantum tunneling between states.

If the rate of change of the transverse field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian. If the rate of change of the transverse field is accelerated, the system may leave the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final problem Hamiltonian, i.e. diabatic quantum computation. The transverse field is switched off, the system is expected to have reached the ground state of the classical Ising model that corresponds to the solution to the original optimization problem. An experimental demonstration of the success of quantum annealing for random magnets was reported after the initial theoretical proposal. An introduction to combinatorial optimization problems, the general structure of quantum annealing-based algorithms and two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems together with an overview of the quantum annealing systems manufactured by D-Wave Systems are presented in.

Quantum annealing can be compared to simulated annealing, whose "temperature" parameter plays a similar role to QA's tunneling field strength. In simulated annealing, the temperature determines the probability of moving to a state of higher "energy" from a single current state. In quantum annealing, the strength of transverse field determines the quantum-mechanical probability to change the amplitudes of all states in parallel. Analytical and numerical evidence suggests that quantum annealing outperforms simulated annealing under certain conditions; the tunneling field is a kinetic energy term that does not commute with the classical potential energy part of the original glass. The whole process can be simulated in a computer using quantum Monte Carlo, thus obtain a heuristic algorithm for finding the ground state of the classical glass. In the case of annealing a purely mathematical objective function, one may consider the variables in the problem to be classical degrees of freedom, the cost functions to be the potential energy function.

A suitable term consisting of non-commuting variable has to be introduced artificially in the Hamiltonian to play the role of the tunneling field. One may carry out the simulation with the quantum Hamiltonian thus constructed just as described above. Here, there is a choice in selecting the non-commuting term and the efficiency of annealing may depend on that, it has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed outperform thermal annealing in certain cases where the potential energy landscape consists of high but thin barriers surrounding shallow local minima. Since thermal transition probabilities depend only on the height Δ of the barriers, for high barriers, it is difficult for thermal fluctuations to get the system out from such local minima. However, as argued earlier in 1989 by Ray, Chakrabarti & Chakrabarti, the quantum tunneling probability through the same barrier depends not only on the height Δ of the barrier, but on its width w and is given by e − Δ w Γ, where Γ is the tunneling field.

If the barriers are thin enough, quantum fluctuations can bring the system out of the shallow local minima. For N -spin glasses, Δ is proportional to N, with a linear annealing schedule for the transverse field, one gets τ proportional to e N for the annealing time (instead of

Simulated annealing

Simulated annealing is a probabilistic technique for approximating the global optimum of a given function. It is a metaheuristic to approximate global optimization in a large search space for an optimization problem, it is used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent; the name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy; the simulation of annealing can be used to find an approximation of a global minimum for a function with a large number of variables. This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored.

Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the global optimal solution. In general, the simulated annealing algorithms work as follows. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, decides to move to it or to stay with the current solution based on either one of two probabilities between which it chooses on the basis of the fact that the new solution is better or worse than the current one. During the search, the temperature is progressively decreased from an initial positive value to zero and affects the two probabilities: at each step, the probability of moving to a better new solution is either kept to 1 or is changed towards a positive value; the simulation can be performed either by a solution of kinetic equations for density functions or by using the stochastic sampling method. The method is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, published by N. Metropolis et al. in 1953.

The state of some physical systems, the function E to be minimized, is analogous to the internal energy of the system in that state. The goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy. At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, probabilistically decides between moving the system to state s* or staying in-state s; these probabilities lead the system to move to states of lower energy. This step is repeated until the system reaches a state, good enough for the application, or until a given computation budget has been exhausted. Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the travelling salesman problem each state is defined as a permutation of the cities to be visited, its neighbours are the set of permutations produced by reversing the order of any two successive cities.

The well-defined way in which the states are altered to produce neighbouring states is called a "move", different moves give different sets of neighbouring states. These moves result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts. Simple heuristics like hill climbing, which move by finding better neighbour after better neighbour and stop when they have reached a solution which has no neighbours that are better solutions, cannot guarantee to lead to any of the existing better solutions – their outcome may be just a local optimum, while the actual best solution would be a global optimum that could be different. Metaheuristics use the neighbours of a solution as a way to explore the solutions space, although they prefer better neighbours, they accept worse neighbours in order to avoid getting stuck in local optima; the probability of making the transition from the current state s to a candidate new state s ′ is specified by an acceptance probability function P, that depends on the energies e = E and e ′ = E of the two states, on a global time-varying parameter T called the temperature.

States with a smaller energy are better than those with a greater energy. The probability function P must be positive when e ′ is greater than e; this feature prevents the method from becoming stuck at a local minimum, worse than the global one. When T tends to zero, the probability P must tend to zero if e

Annealing (metallurgy)

Annealing, in metallurgy and materials science, is a heat treatment that alters the physical and sometimes chemical properties of a material to increase its ductility and reduce its hardness, making it more workable. It involves heating a material above its recrystallization temperature, maintaining a suitable temperature for a suitable amount of time, cooling. In annealing, atoms migrate in the crystal lattice and the number of dislocations decreases, leading to a change in ductility and hardness; as the material cools it recrystallizes. For many alloys, including carbon steel, the crystal grain size and phase composition, which determine the material properties, are dependent on the heating, cooling rate. Hot working or cold working after the annealing process alter the metal structure, so further heat treatments may be used to achieve the properties required. With knowledge of the composition and phase diagram, heat treatment can be used to adjust between harder and more brittle, to softer and more ductile.

In the cases of copper, steel and brass, this process is performed by heating the material for a while and slowly letting it cool to room temperature in still air. Copper and brass can be cooled in air, or by quenching in water, unlike ferrous metals, such as steel, which must be cooled to anneal. In this fashion, the metal is softened and prepared for further work—such as shaping, stamping, or forming. Annealing occurs by the diffusion of atoms within a solid material, so that the material progresses towards its equilibrium state. Heat increases the rate of diffusion by providing the energy needed to break bonds; the movement of atoms has the effect of redistributing and eradicating the dislocations in metals and in ceramics. This alteration to existing dislocations allows a metal object to deform more increasing its ductility; the amount of process-initiating Gibbs free energy in a deformed metal is reduced by the annealing process. In practice and industry, this reduction of Gibbs free energy is termed stress relief.

The relief of internal stresses is a thermodynamically spontaneous process. The high temperatures at which annealing occurs serve to accelerate this process; the reaction that facilitates returning the cold-worked metal to its stress-free state has many reaction pathways involving the elimination of lattice vacancy gradients within the body of the metal. The creation of lattice vacancies is governed by the Arrhenius equation, the migration/diffusion of lattice vacancies are governed by Fick’s laws of diffusion. In steel, there is a decarburation mechanism that can be described as three distinct events: the reaction at the steel surface, the interstitial diffusion of carbon atoms and the dissolution of carbides within the steel; the three stages of the annealing process that proceed as the temperature of the material is increased are: recovery, recrystallization, grain growth. The first stage is recovery, it results in softening of the metal through removal of linear defects called dislocations and the internal stresses they cause.

Recovery occurs at the lower temperature stage of all annealing processes and before the appearance of new strain-free grains. The grain size and shape do not change; the second stage is recrystallization, where new strain-free grains nucleate and grow to replace those deformed by internal stresses. If annealing is allowed to continue once recrystallization has completed grain growth occurs. In grain growth, the microstructure starts to coarsen and may cause the metal to lose a substantial part of its original strength; this can however be regained with hardening. The high temperature of annealing may result in oxidation of the metal’s surface, resulting in scale. If scale must be avoided, annealing is carried out in a special atmosphere, such as with endothermic gas. Annealing is done in forming gas, a mixture of hydrogen and nitrogen; the magnetic properties of mu-metal are introduced by annealing the alloy in a hydrogen atmosphere. Large ovens are used for the annealing process; the inside of the oven is large enough to place the workpiece in a position to receive maximum exposure to the circulating heated air.

For high volume process annealing, gas fired conveyor furnaces are used. For large workpieces or high quantity parts, car-bottom furnaces are used so workers can move the parts in and out. Once the annealing process is completed, workpieces are sometimes left in the oven so the parts cool in a controllable way. While some workpieces are left in the oven to cool in a controlled fashion, other materials and alloys are removed from the oven. Once removed from the oven, the workpieces are quickly cooled off in a process known as quench hardening. Typical methods of quench hardening materials involve media such as air, oil, or salt. Salt is used as a medium for quenching in the form of brine. Brine provides faster cooling rates than water; this is because when an object is quenched in water steam bubbles form on the surface of the object reducing the surface area the water is in contact with. The salt in the brine reduces the formation of steam bubbles on the object's surface, meaning there is a larger surface area of the object in contact with the water, providing faster cooling rates.

Quench hardening is applicable to some ferrous alloys, but not copper alloys. In the semiconductor industry, silicon wafers are annealed, so that dopant atoms boron, phosphorus or arsenic, can diffuse into substitutional positions in the cr