xQIT W. M. Keck Foundation Center For Extreme Quantum Information Theory at the Massachusetts Institute of Technology
News About People Research Publications Events Courses Positions Contact

< Back to Research


Problem Importance

  Research > Projects

Algorithms to Solve Average-Case NP-Hard Problems

xQIT Focus Area 1: Algorithms to Solve Average-Case NP-Hard Problems


Prof. Edward Farhi, Team Leader
Prof. Jeffrey Goldstone
Prof. Seth Lloyd
Prof. Peter Shor
Postdoctoral Fellow
Graduate Student
Visiting Scientists

Why it is important to solve the problem?

A large number of socially-relevant optimization problems having to do with networking, finance, and design are in a computational-complexity class called NP-complete. It is apparently very difficult to find solutions to such problems, though if a solution is found, it can easily be verified to be correct. Indeed, this feature is what defines the class of problems called NP (NP stands for non-deterministic polynomial time). For example, the travelling salesman problem is in NP. In this problem, a salesman (or saleswoman) has to drive between a number of cities, visiting each of them once. The problem is to find a route shorter than a particular bound. As the number of cities grows, the number of possible routes grows very rapidly. Thus, finding the shortest route is typically hard. But, if someone gives you a potential answer—"first drive to Cleveland, then to Buffalo, . . . " — you can easily check whether that route is shorter than the bound.

The range of problems in NP is very broad. The question, "Can a computer be programmed to perform a particular task efficiently" is in NP: if someone presents you with a program for performing the task, you can verify that it makes a computer perform the task efficiently simply by running the program. The class of problems in NP possesses a hardest subset called NP-complete problems. They share the feature that if you can solve one efficiently, than you can also solve all other NP problems efficiently. The travelling salesman problem is NP-complete, as is the efficient computer programming problem. To see that the efficient computer programming problem is also NP-complete, simply note that one such problem is, "Can a computer be programmed to solve the travelling salesman problem efficiently?" If the answer is "Yes," then the travelling salesman problem can be solved efficiently.

At present, very few researchers believe that NP-complete problems can be solved efficiently by a computer, be it classical or quantum. Nevertheless, algorithms exist that seem to allow the solution for average cases of such hard problems. In particular, Farhi and Goldstone’s adiabatic algorithm for quantum computation, which is based on the physical technique of adiabatic passage, appears to solve many such problems efficiently. In adiabatic passage a system’s Hamiltonian—its energy functional—is slowly deformed from a simple initial structure to a more complicated form. If the system was initially in its ground state, and if the transformation was sufficiently slow, i.e., adiabatic, then the quantum system will still be in its ground state at the end of the Hamiltoniantransformation process. Adiabatic quantum computation works by choosing an initial Hamiltonian whose ground state is easily prepared, and a final Hamiltonian whose ground state encodes the solution to the problem at hand. The adiabatic algorithm currently represents quantum computers’ best hope for solving NP-complete problems.Since its proposal by Farhi et al., the adiabatic algorithm has been the topic of intense investigation by researchers in quantum information and quantum statistical mechanics.




"The class of problems in NP possesses a hardest subset called NP-complete problems. They share the feature that if you can solve one efficiently, than you can also solve all other NP problems efficiently."