xQIT Focus Area 1: Algorithms to Solve Average-Case NP-Hard Problems
Team
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.
|
