Physics may bring faster solutions for tough computational problems – Phys.Org

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 statistical mechanics 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 phase transitions 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 parallelismthe 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," 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 model.

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

Imaginary numbers are a solution to a very real problem in a study published today in Scientific Reports.

While technologies that currently run on classical computers, such as Watson, can help find patterns and insights buried in vast amounts of existing data, quantum computers will deliver solutions to important problems where ...

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.

How fast will a quantum computer be able to calculate? While fully functional versions of these long-sought technological marvels have yet to be built, one theorist at the National Institute of Standards and Technology (NIST) ...

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

Physicists have developed a quantum machine learning algorithm that can handle infinite dimensionsthat is, it works with continuous variables (which have an infinite number of possible values on a closed interval) instead ...

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 ...

By precisely measuring the entropy of a cerium copper gold alloy with baffling electronic properties cooled to nearly absolute zero, physicists in Germany and the United States have gleaned new evidence about the possible ...

When Northwestern Engineering's Erik Luijten met Zbigniew Rozynek, they immediately became united by a mystery.

It's a material world, and an extremely versatile one at that, considering its most basic building blocksatomscan be connected together to form different structures that retain the same composition.

Researchers at the National Institute of Standards and Technology (NIST) have produced and precisely measured a spectrum of X-rays using a new, state-of-the-art machine. The instrument they used to measure the X-rays took ...

Scientists have discovered a way to solve a problem that has baffled humans for so long it is mentioned in the Bible: achieving the most efficient packing of objects such as grains and pharmaceutical drugs.

Adjust slider to filter visible comments by rank

Display comments: newest first

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.

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.

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.

Einsteins quote about everything being explained as simply as possible is sort of similar - less energy expenditure.

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.

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

Read more from the original source:

Physics may bring faster solutions for tough computational problems - Phys.Org