Αναρτήσεις

Προβολή αναρτήσεων από Δεκέμβριος, 2020

Using an electronic amoeba to quickly find an approximate solution to traveling salesman problem

The traveling salesman problem is about a salesman that has to start from a specific town and after visiting a number of towns only once, he/she has to return to the starting town. The real problem is to minimize the total length of the trip. It has been shown that this problem is NP-complete, which practically means that this is a very difficult problem to solve with a computer. However, Kenta Saito, Masashi Aono, and Seiya Kasai from Japan have shown that an electronic amoeba can give an approximate solution to this problem in linear time. Practically, this means that the new approach can transform a difficult problem to an easy one. The Japanese researchers reported their findings in a paper in scientific reports .

New milestone in quantum supremacy

A new kind of quantum computer that harnesses photons has achieved a new breakthrough in quantum supremacy. In particular, this machine completed a computational task in 200 seconds while an ordinary supercomputer would require 2.5 billion years. The computer employes a technique called Gaussian boson sampling (a photon is a boson) and a complete description of the machine is given in an article published in Sciece (everyone can read it for free).