Statistical physics may speed up finding solutions for computational problems

Boston University's picture

EMBARGOED FOR RELEASE UNTIL: May 12, 2017, 5 a.m. EST
CONTACT: Margaret Waterman, at 617-358-4266 or mhw@bu.edu

Statistical physics may speed up finding solutions for computational problems
Novel physics-inspired model takes on difficult computational challenges from a new perspective

(BOSTON) – The field of statistical mechanics was initially developed to study the behavior of macroscopic numbers of atoms or molecules in gasses and liquids, and evolved to describe the properties of complex states of matter that display magnetism, superconductivity and other types of exotic behavior. Techniques inspired by statistical mechanics have also been applied to understand traffic patterns, the behavior of networks of neurons and stock market fluctuations. Researchers at Boston University (BU) and the University of Central Florida have now discovered a new way of applying statistical mechanics to certain classes of highly complex problems in computer science.

The novel approach suggests how one could create more efficient algorithms that run on traditional computers or on a new generation of hybrid classical/quantum computational hardware, says Andrei Ruckenstein, BU professor of physics and co-author on a paper introducing a new statistical mechanics representation of reversible classical computation published in the journal Nature Communications.

“Statistical mechanics studies complex systems made up of a very large number of constituents,” Ruckenstein explains. “For example, atoms that organize themselves into materials with properties, such as magnetism or superconductivity, that could not be understood in terms of the individual constituents alone.

“Some difficult problems in classical computation have already been addressed with great success by mapping them onto a certain class of statistical mechanics models, for which the result of the computation is encoded in the lowest energy state of the system,” he says.

However, previous models of this class display transitions between different thermodynamic phases with substantively different physical properties (for example, the transition from liquid to gas). In these previous models relevant to computation the phase transition takes the system into a so-called glassy phase characterized by many competing low-energy states.

“As a result of this large number of low-energy options, finding the absolute lowest state corresponding to the solution of the computational problem is an extremely slow process,” says Claudio Chamon, a BU professor of physics and co-author on the paper. “This prevents the system from reaching its lowest energy state even for problems that could be solved efficiently by other methods.”

The research team overcame this barrier with an elegant “vertex model” of computation employing a two-dimensional lattice with reversible logic gates at the vertices of the lattice. “This model exhibits no bulk thermodynamic phase transition, so one of the obstructions for reaching a solution present in previous models is eliminated,” says Chamon. “It’s a new way of thinking about the problem.”

The vertex model may help solve complex problems in machine learning, circuit optimization and other major computational challenges. Additionally, the researchers are exploring whether the model can be applied to the factoring of semi-primes, numbers that are the product of two prime numbers. (The difficulty of performing this operation with very large semi-primes underlies modern cryptography and has offered a key rationale for the creation of large-scale quantum computers.)

Moreover, the model can be generalized to add another path to solutions of complex classical computational problems by taking advantage of quantum mechanical parallelism – the fact that, according to quantum mechanics, a system can be in many classical states at the same time.

“Our paper also presents a natural framework for programming special-purpose computational devices, such as D-Wave Systems machines, that use quantum mechanics to speed up the time to solution of classical computational problems,” says Ruckenstein. “This kind of model could be implemented into many architectures of these hybrid classical/quantum computing machines, which could help us find the ground state of the system by using quantum mechanics as an accelerator.”

In addition to its findings about computational modeling, the paper hypothesizes the existence of a novel family of glasses which do not display a thermodynamic glass transition but exhibit extremely long times scales for finding the system’s lowest energy state.

Zhi-Cheng Yang, a graduate student in physics at BU, and Eduardo Mucciolo, professor of physics at the University of Central Florida in Orlando, are co-authors on the paper. The universities have applied for a patent on aspects of the quantum vertex model.

“Our work shows that the boundary between physics and computer science is a two-way street,” Ruckenstein comments. “We physicists want to use our approaches to solve computer science problems, but we also want to bring back into physics ideas from computer science that would be very hard to articulate on the basis of physics thinking alone.”

“Interdisciplinary work like this rests on involving collaborators with strong and deep backgrounds in the various disciplines, and on figuring out how one can learn each other’s language in order to communicate effectively at these boundaries,” he adds.

Founded in 1839, Boston University is an internationally recognized institution of higher education and research. With more than 33,000 students, it is the fourth-largest independent university in the United States. BU consists of 16 schools and colleges, along with a number of multi-disciplinary centers and institutes integral to the University’s research and teaching mission. In 2012, BU joined the Association of American Universities, a consortium of 62 leading research universities in the United States and Canada.

Copy this html code to your website/blog to embed this press release.

Comments

Post new comment

6 + 0 =

To prevent automated spam submissions leave this field empty.