Abstract
By a News Reporter-Staff News Editor at Robotics & Machine Learning Daily News-Current study results on computational learning h ave been published. According to news reporting out of Berlin, Germany, by NewsR x editors, research stated, "It is unclear to what extent quantum algorithms can outperform classical algorithms for problems of combinatorial optimization." Our news reporters obtained a quote from the research from Technical University Berlin (TU Berlin): "In this work, by resorting to computational learning theory and cryptographic notions, we give a fully constructive proof that quantum comp uters feature a super-polynomial advantage over classical computers in approxima ting combinatorial optimization problems. Specifically, by building on seminal w ork by Kearns and Valiant, we provide special instances that are hard for classi cal computers to approximate up to polynomial factors. Simultaneously, we give a quantum algorithm that can efficiently approximate the optimal solution within a polynomial factor. The quantum advantage in this work is ultimately borrowed f rom Shor's quantum algorithm for factoring."
NETL
NSTL