Physics may bring faster solutions for tough computational problems

May 12, 2017
Eduardo Mucciolo, Professor and Chair of the Department of Physics at the University of Central Florida. Credit: University of Central Florida

A well-known computational problem seeks to find the most efficient route for a traveling salesman to visit clients in a number of cities. Seemingly simple, it's actually surprisingly complex and much studied, with implications in fields as wide-ranging as manufacturing and air-traffic control.

Researchers from the University of Central Florida and Boston University have developed a novel approach to solve such difficult computational problems more quickly. As reported May 12 in Nature Communications, they've discovered a way of applying statistical mechanics, a branch of physics, to create more efficient algorithms that can run on traditional computers or a new type of quantum computational machine, said Professor Eduardo Mucciolo, chair of the Department of Physics in UCF's College of Sciences.

Statistical mechanics was developed to study solids, gasses and liquids at macroscopic scales, but is now used to describe a variety of complex states of matter, from magnetism to superconductivity. Methods derived from statistical mechanics have also been applied to understand traffic patterns, the behavior of networks of neurons, sand avalanches and stock market fluctuations.

There already are successful algorithms based on that are used to solve computational problems. Such algorithms map problems onto a model of binary variables on the nodes of a graph, and the solution is encoded on the configuration of the model with the lowest energy. By building the model into hardware or a computer simulation, researchers can cool the system until it reaches its lowest energy, revealing the solution.

"The problem with this approach is that often one needs to get through similar to those found when going from a liquid to a glass phase, where many competing configurations with low energy exist," Mucciolo said. "Such phase transitions slow down the cooling process to a crawl, rendering the method useless."

Mucciolo and fellow physicists Claudio Chamon and Andrei Ruckenstein of BU overcame this hurdle by mapping the original computational problem onto an elegant statistical model without phase transitions, which they called the vertex model. The model is defined on a two-dimensional lattice and each vertex corresponds to a reversible logic gate connected to four neighbors. Input and output data sit at the boundaries of the lattice. The use of reversible logic gates and the regularity of the lattice were crucial ingredients in avoiding the phase-transition snag, Mucciolo said.

"Our method basically runs things in reverse so we can solve these very hard problems," Mucciolo said. "We assign to each of these logic gates an energy. We configured it in such a way that every time these logic gates are satisfied, the energy is very low - therefore, when everything is satisfied, the overall energy of the system should be very low."

Chamon, a professor of physics at BU and the team leader, said the research represents a new way of thinking about the problem.

"This model exhibits no bulk thermodynamic-phase transition, so one of the obstructions for reaching solutions present in previous models was eliminated," he said.

The vertex model may help solve complex problems in machine learning, circuit optimization, and other major computational challenges. The researchers are also 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 toward the solution 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 ," said Ruckenstein.

Zhi-Cheng Yang, a graduate student in physics at BU, is also a co-author on the paper. The universities have applied for a patent on aspects of the vertex .

Explore further: Study offers new theoretical approach to describing non-equilibrium phase transitions

More information: C. Chamon et al, Quantum vertex model for reversible classical computing, Nature Communications (2017). DOI: 10.1038/ncomms15303

Related Stories

Spin glass physics with trapped ions

May 27, 2016

One of the most striking discoveries of quantum information theory is the existence of problems that can be solved in a more efficient way with quantum resources than with any known classical algorithm.

D-Wave uses quantum method to solve protein folding problem

August 21, 2012

(Phys.org) -- While there has been some skepticism as to whether the Canadian company D-Wave’s quantum computing system, the D-Wave One, truly involves quantum computing, the company is intent on proving that the system ...

Recommended for you

Brittle starfish shows how to make tough ceramics

December 8, 2017

An international team lead by researchers at Technion-Israel Institute of Technology, together with colleagues from the European Synchrotron, Grenoble, France, have discovered how an echinoderm called Ophiocoma wendtii, known ...

7 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

EmceeSquared
5 / 5 (1) May 12, 2017
If this tech solves the traveling salesman problem in non-polynomial time without quantum computers, the Nobel Committee should create a Computer Science prize for it.
kochevnik
3 / 5 (2) May 13, 2017
Stimulate-annealing problem was a bitch due to phase transition. This seems like actually innovation, rather than the descriptive and iceberg-meting garbage permeating the site.
luke_w_bradley
not rated yet May 13, 2017
Really cool work, love to see physicists in CS. Simulated Annealling is the beginning, I think there's a lot more: a principle of least information in AI will emerge, I predict, matching physics principle of least action, and in time computation will illuminate more physics. For instance, imagine if its NOT the case that there is physical solution to Travelling salesman or other NP complete problems, (meaning no physical system computes their solution) that's profound as a solution. It implies an anonymity to photons for instance, the fact that they have no history. It also lends a lot of credence to those weird ideas that we're all living in a computer simulation.
Whydening Gyre
not rated yet May 14, 2017
Einsteins quote about everything being explained as simply as possible is sort of similar - less energy expenditure.
luke_w_bradley
not rated yet May 14, 2017
Right, Occam's razor has formal statements in information theory too. Its really just kind of common sense: if we encoded the world around us smartly, common things, like an orange in an orange tree, would little information to encode, but uncommon things, like a traffic cone in an orange tree would take more info. So an AI, on seeing something orange between the leaves of an orange tree, should assume its an orange, as our brains would.
MaryTormey
not rated yet May 15, 2017
If there are 3 known partials with establish predictable behavior than we can simulate that behavior in a fairly simple manor. I discovered a shape that had beat chance thus increasing it's provability of existing later at grandmas house. This would be the shape of 120 Maryium 313, this mobile spiral would not only have a 100% provability of existing spontaneously over time, but would actually reproduce make choices and evolve under the right conditions.
EmceeSquared
not rated yet May 15, 2017
Please post the link to the peer-reviewed article you published explaining it. Especially the "grandma's house" part.

Or else don't make public claims that are merely wishful thinking. This is a science site, and science has requirements.

MaryTormey:
If there are

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.