optimization-overview-introduction.md

author	description	ms.author	ms.date	ms.service	ms.subservice	ms.topic	title	uid
SoniaLopezBravo	Learn about optimization and key terms	sonialopez	09/27/2021	azure-quantum	optimization	overview	Introduction to optimization	microsoft.quantum.optimization.concepts.overview.introduction

What is optimization?

Optimization is the process of finding the best solution to a problem from a set of possible options, given its desired outcome and constraints.

The best solution can be defined in many ways: it could be the option with the lowest cost, the quickest runtime, or perhaps the lowest environmental impact. To keep things simple, best is usually defined as a cost to be minimized. If you wanted to maximize the cost instead (for example, if you wanted to maximize energy output from a solar cell), all you would need to do is multiply the cost by negative one and then minimize it.

To learn more about optimization problems and the terminology, see key concepts of optimization.

Optimization is a class of computing problems that are primary candidates for running on quantum computers in the future, providing a quantum advantage over classical solutions. You can already implement optimization problems using Azure Quantum solvers that run on classical hardware in Azure today faster than many other classical optimization techniques.

What is quantum-inspired optimization?

Simulating the quantum effects on classical computers has led to the development of new types of quantum solutions. Quantum-Inspired Optimization algorithms exploit some of the advantages of quantum computing on classical hardware, providing a speedup over traditional approaches.

Quantum-inspired algorithms are classical algorithms where you classically emulate the essential quantum phenomena that provide the speedup. There are many types of quantum-inspired algorithms, one commonly used algorithm is based on a computational model called adiabatic quantum computing, which consist of the following:

1. First, you prepare a system and initialize it to its lowest energy state.

2. Next, slowly transform that system into a more complex one that describes the problem you are trying to solve. The adiabatic model states that, as long as this transformation happens slowly enough, the system has time to adapt and will stay in that lowest energy configuration. When the transformations are done, you can solve the problem.

A good analogy of this is to imagine you have a glass of water. If you move that glass slowly across a table, the contents won't spill because the system has time to adapt to its new configuration. If you were to move the glass quickly however, the system has been forced to change too quickly, and you have water everywhere.

Where can quantum-inspired optimization be applied?

Applying quantum-inspired optimization to real-world problems may offer businesses new insights or help lower costs by making their processes more efficient. Quantum-inspired optimization gives us the opportunity to:

• Find a solution faster than other optimization techniques for a fixed use case and fixed quality of solution.
• Find a higher quality solution than other optimization techniques for a fixed problem and fixed amount of time.
• Use a more realistic model than other optimization techniques by extending the problem to consider more variables.

Since quantum-inspired optimization methods are heuristics, they're not guaranteed to find the optimal solution, nor do they always outperform other optimization techniques. In reality, it depends on the problem, and discovering what makes quantum-inspired optimization perform better than other methods in some situations and not others is still an active area of research.

Here are the necessary conditions for quantum-inspired optimization to perform well, compared to other classical optimization algorithms:

• Optimization landscapes should be rugged but structured. Such landscapes occur frequently in real-world problems. For more information, see Optimization landscapes.
• If the number of variables is small (for example, less than one hundred), simplistic algorithms are already sufficient. For problems that have hundreds of variables, quantum-inspired optimization has achieved improvement over previously used methods by orders of magnitude.
• Problem parameters that affect the chosen cost metric must be represented via the variables of a cost function. Express cost functions as polynomials over binary variables to obtain a PUBO problem.

How does quantum-inspired optimization solve problems?

There exist several methods for finding the global minimum of a cost function, one of the most successful and commonly used heuristic is simulated annealing. A heuristic is a technique for finding an approximate solution, especially in situations where finding an exact solution can take too long. You can think of the technique as a random walk through the search space, where each walker creates a path through the optimization landscape.

In simulated annealing, the algorithm simulates a walker that, ideally, always moves downhill but can also take uphill moves with some non-zero probability. This creates the possibility for the walker to escape from local minima and then descend into deeper neighboring minima. The uphill moves are called thermal jumps. That is because simulated annealing is an algorithm from physics that mimics the behavior of materials as they are slowly cooled.

Quantum-inspired optimization makes use of the techniques for solving combinatorial problems of simulated annealing but applying quantum mechanical effects.

Quantum annealing is a quantum algorithm that is similar in spirit to simulated annealing, but it differs in a few ways. In simulated annealing, the search space is explored by making thermal jumps from one solution to the next, while quantum annealing makes use of a quantum effect called quantum tunneling, which allows the walker to travel through these energy barriers.

In this graph, you can see the difference between the classical and the quantum approach. In simulated annealing thermal fluctuations help a walker overcome an energy barrier, and in quantum tunneling, quantum effects allow a walker to pass through the energy barrier.

Azure Quantum optimization techniques

Azure Quantum offers a range of quantum-inspired techniques to solve discrete and combinatorial optimization problems.

• Parallel Tempering: A related classical optimization approach, where copies of a system are kept at different temperatures, automating the repeated heating and cooling in tempering approaches. It can be used to accelerate both classical and (simulated) quantum annealing, as well as many other heuristics.
• Simulated Annealing: A classical stochastic simulation method that mimics the slow cooling of a material (annealing) to remove imperfections. A temperature is reduced according to a schedule. Thermal hops assist in escaping from local minima in the search space.
• Population Annealing: Just as Simulated Annealing simulates a walker that, ideally, always moves downhill, Population Annealing simulates a population of metropolis walkers, which continuously consolidate search efforts around favorable states.
• Quantum Monte Carlo: A quantum-inspired optimization that mimics the quantum annealing method by using quantum Monte-Carlo simulations. Analogous to the temperature in simulated annealing, the quantum tunneling strength is reduced over time. Quantum tunneling effects assist in escaping from local minima in the search space.
• Substochastic Monte Carlo: Substochastic Monte Carlo is a diffusion Monte Carlo algorithm inspired by adiabatic quantum computation. It simulates the diffusion of a population of walkers in the search space, where walkers are removed or duplicated based on how they perform according to the cost function.
• Tabu Search: Tabu Search looks at neighboring configurations. It can accept worsening moves if no improving moves are available and prohibits moves to previously visited solutions

Note that this is only a small subset of available techniques, and Microsoft continues to develop and add new solvers to the Azure Quantum service. For more information, see the Microsoft QIO provider list.