. 24/7 Space News .
Physics may bring faster solutions for tough computational problems
by Staff Writers
Orlando FL (SPX) May 15, 2017

Eduardo Mucciolo, Professor and Chair of the Department of Physics at the 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 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.

Research paper

The first one bit chemical memory unit: The 'chit'
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

Related Links
University of Central Florida
Space Technology News - Applications and Research

Thanks for being here;
We need your help. The SpaceDaily news network continues to grow but revenues have never been harder to maintain.

With the rise of Ad Blockers, and Facebook - our traditional revenue sources via quality network advertising continues to decline. And unlike so many other news sites, we don't have a paywall - with those annoying usernames and passwords.

Our news coverage takes time and effort to publish 365 days a year.

If you find our news sites informative and useful then please consider becoming a regular supporter or for now make a one off contribution.
SpaceDaily Contributor
$5 Billed Once

credit card or paypal
SpaceDaily Monthly Supporter
$5 Billed Monthly

paypal only

Comment using your Disqus, Facebook, Google or Twitter login.

Share this article via these popular social media networks
del.icio.usdel.icio.us DiggDigg RedditReddit GoogleGoogle

'Awesomesauce,' proclaims US astronaut on historic spacewalk

Six-legged livestock - sustainable food production

External commercial ISS platform starts second mission

NASA Receives Proposals for Future Solar System Mission

SpaceX launches Inmarsat communications satellite

Testing Prepares NASA's Space Launch System for Liftoff

N. Korea's 'new missile' has unprecedented range: experts

NASA Affirms Plan for First Mission of SLS, Orion

Opportunity Reaches 'Perseverance Valley'

Ancient Mars impacts created tornado-like winds that scoured surface

Mars Rover Opportunity Begins Study of Valley's Origin

Seasonal Flows in Valles Marineris

A cabin on the moon? China hones the lunar lifestyle

China tests 'Lunar Palace' as it eyes moon mission

China to conduct several manned space flights around 2020

Reach for the Stars: China Plans to Ramp Up Space Flight Activity

Allied Minds' portfolio company BridgeSat raises $6 million in Series A financing

AIA report outlines policies needed to boost the US Space Industry competitiveness

Blue Sky Network Targets Key Markets For Iridium SATCOM Solutions

How Outsourcing Your Satellite Related Services Saves You Time and Money

"Airbus Friedrichshafen: new satellite hub lays groundwork for the future"

Physics may bring faster solutions for tough computational problems

A bath for precision printing of 3-D silicone structures

Physical keyboards make virtual reality typing easier

'Warm Neptune' Has Unexpectedly Primitive Atmosphere

Astrophysicists find that planetary harmonies around TRAPPIST-1 save it from destruction

Two Webb instruments well suited for detecting exoplanet atmospheres

Variable Winds on Hot Giant Exoplanet Help Study of Magnetic Field

Waves of lava seen in Io's largest volcanic crater

Not So Great Anymore: Jupiter's Red Spot Shrinks to Smallest Size Ever

The PI's Perspective: No Sleeping Back on Earth!

ALMA investigates 'DeeDee,' a distant, dim member of our solar system

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.