Emerging Techniques for Solving NP-Complete Problems<br/><br/> in Mathematics, Biology, Engineering ... and Physics

Wednesday, November 9, 2005 - 11:00am - 12:00pm
EE/CS 3-180
John Sidles (University of Washington)
Complex systems are ubiquitous in mathematics, biology,
engineering, and
physics, and the past ten years have witnessed an exponential
increase in
the literature associated such systems. A shared conceptual
framework is
becoming apparent among challenges as seemingly different as the
the search by mathematicians for exact high-order trigonometric
the search by engineers for stable control systems, the search by
biologists for stable protein structures, and the search by condensed
matter physicists for ground states.

Recent work has shown that separated product-sum representations
provide a
powerful and broadly applicable tool for analyzing complex
systems. Beylkin
and Mohlenkamp provide a good introduction to these
representations in their
recent preprint Algorithms for Numerical Analysis in High

(*). This talk will review some of the basic ideas of separated
representations, and discuss how our UW Quantum System Engineering
Group is applying these ideas in polynomial-time simulations of
quantum spin systems.

Our QSE Group has found that Beylkin and Mohlenkamp's methods can be
readily extended to dynamical systems by a two-fold trick: (1)
noise, and (2) convert the noise to an equivalent measurement
The second step exploits the same unitary invariance of operator-sum
representations that plays a central role in quantum computing
theory. The
resulting quantum trajectories are readily projected onto low-
manifolds of Beylkin-Mohlenkamp type, where they can be integrated
using polynomial-time numerical algorithms.

The practical consequence is that a broad class of problems in
physics and engineering that were previously thought to be in the
(intractable) complexity class EXP can now be solved by algorithms
that are
in the (much simpler) complexity class NP. The lecture will close
with an
informal survey of physics problems that might be addressed by
these methods.

MSC Code: