Abstract

Quantum annealers, such as the commercially available D-Wave systems, use quantum effects to improve their effectiveness in finding solutions to discrete optimization problems that are hard to solve on classical computers. Unlike the better known universal quantum computers, which are conceptually able to tackle all problems that classical computers can solve, quantum annealers are focused on a class of quadratic optimization problems that include all NP-hard problems, such as the Maximum Clique, Graph Coloring, and Traveling Salesman problems. Thanks to this specialization, however, current D-Wave annealers have much larger number of qubits compared to the existing universal computers, and are easier to program and use. Despite this, as with all existing quantum hardware, characterized as a Noisy Intermediate-Scale Quantum (NISQ) type, getting high-quality solutions requires dealing with limitations on the size, connectivity, and fidelity of the devices and errors caused by unintended interactions with the external environment. In this talk, I will first review the basic ideas of quantum annealing and how it can be used to solve discrete optimization problems. Then I will discuss methods that we have developed, which allow solving larger problems that can directly fit in the quantum hardware of D-Wave computers, and methods to mitigate errors and biases in the hardwire, leading to higher-quality solutions.

Short Bio

Hristo Djidjev received his Ph.D. from the University of Sofia, Bulgaria. He is currently a Scientist at the Information Sciences group of Los Alamos National Laboratory, USA. Before Los Alamos, he has been with the Bulgarian Academy of Sciences, Rice University (US), and University of Warwick (UK). His interests are in graph algorithms, quantum computing, combinatorial optimization, bioinformatics, and unsupervised learning.