Quantum-inspired heuristics

Physical processes can inspire the design of algorithms and (meta)heuristics. (Many methods in this chapter are not strictly algorithms: they are not guaranteed to provide a true solution in a finite time and rarely have time estimates; but for many of them the term algorithm is most common in the literature they come from, so we mostly use it.) In recent years, a number of such algorithms, implemented on both quantum and classical computers, have been developed and applied. In this chapter, we provide an outline of the range of such algorithms, focusing on those inspired by quantum physics, and describe some applications, particularly to problems in the domain of operational research. We begin with a short introduction to the major areas of physics, since many physical concepts are central in algorithms of interest. It is not possible to discuss in detail all of these areas in one chapter, so we focus on the aspects of each area that are most helpful in understanding the range of quantum-inspired algorithms that currently exist. In subsequent sections, we describe a number of algorithms that are inspired by aspects of these physical phenomena. The degree of fidelity of these algorithms to the original natural process varies. Different algorithms could be devised depending on which aspect of the underlying phenomenon is chosen: an algorithm designer may choose the degree of fidelity to nature of an algorithm, to give an algorithm which is efficient on the problems to which it is applied, while not necessarily being perfectly true to nature.