Physics may bring faster solutions for tough computational problems
by Staff Writers
Orlando FL (SPX) May 15, 2017
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 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," 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.
Warsaw, Poland (SPX) May 08, 2017
In classical computer science information is stored in bits, in quantum computer science - in quantum bits, i.e. qubits. Experiments at the Institute of Physical Chemistry of the Polish Academy of Sciences in Warsaw prove that not only physics, but also chemistry is suitable for storing information. The role of the chemical bit, the 'chit', can be fulfilled by a simple arrangement of three dropl ... read more
University of Central Florida
Space Technology News - Applications and Research
|The content herein, unless otherwise known to be public domain, are Copyright 1995-2024 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. All articles labeled "by Staff Writers" include reports supplied to Space Media Network by industry news wires, PR agencies, corporate press officers and the like. Such articles are individually curated and edited by Space Media Network staff on the basis of the report's information value to our industry and professional readership. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. General Data Protection Regulation (GDPR) Statement Our advertisers use various cookies and the like to deliver the best ad banner available at one time. All network advertising suppliers have GDPR policies (Legitimate Interest) that conform with EU regulations for data collection. By using our websites you consent to cookie based advertising. If you do not agree with this then you must stop using the websites from May 25, 2018. Privacy Statement. Additional information can be found here at About Us.