# 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

following:

the search by mathematicians for exact high-order trigonometric

identities,

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

Dimensions

(*). This talk will review some of the basic ideas of separated

product-sum

representations, and discuss how our UW Quantum System Engineering

(QSE)

Group is applying these ideas in polynomial-time simulations of

large-scale

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)

introduce

noise, and (2) convert the noise to an equivalent measurement

processes.

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-

dimensional

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

quantum

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.

(*) http://amath.colorado.edu/activities/preprints/archive/519.pdf

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

following:

the search by mathematicians for exact high-order trigonometric

identities,

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

Dimensions

(*). This talk will review some of the basic ideas of separated

product-sum

representations, and discuss how our UW Quantum System Engineering

(QSE)

Group is applying these ideas in polynomial-time simulations of

large-scale

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)

introduce

noise, and (2) convert the noise to an equivalent measurement

processes.

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-

dimensional

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

quantum

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.

(*) http://amath.colorado.edu/activities/preprints/archive/519.pdf

MSC Code:

37Fxx

Keywords: