Computing’s Search for Quantum QuestionsLearn about the...

Computing’s Search for Quantum Questions

Learn about the viability of quantum annealing to solve NP-hard problems.

Unlike a universal quantum computer, which is designed to tackle a range of problems, a quantum annealer is designed to tackle a specific type of problem called an NP-hard optimization problem. These can arise in many situations, but here’s an example: Say you went to a city and wanted to find the largest cluster of people who all know each other. (This is called the “maximum clique problem” in computer science.) You could try to tackle the problem with a brute-force approach, identifying every group of friends and comparing sizes until you settled on the largest. Such a strategy would work for a small village, but it becomes untenable if you want to identify and compare every group of friends in, say, Tokyo. […] To solve this kind of problem, the D-Wave 2X uses a process called annealing, which gets its name from a 7,000-year-old metallurgical practice. Early metalworkers figured out that if they made a material hot enough and then let it cool down slowly, it would make the final product stronger. The process works because the heat randomly jiggles around all the atoms in the metal, and then as it cools, the atoms slowly arrange themselves into their lowest-energy (and therefore most stable) configuration. Bartenders may also recognize the process: The secret to creating a flawless and clear ice cube is to let the water freeze very, very slowly.

Quanta Magazine - Image by Daan Botlek