• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Scopus
  4. An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
 
  • Details
  • Full
Options
2024
Journal Article
Title

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory

Abstract
It is unclear to what extent quantum algorithms can outperform classical algorithms for problems of combinatorial optimization. In this work, by resorting to computational learning theory and cryptographic notions, we give a fully constructive proof that quantum computers feature a super-polynomial advantage over classical computers in approximating combinatorial optimization problems. Specifically, by building on seminal work by Kearns and Valiant, we provide special instances that are hard for classical 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 from Shor’s quantum algorithm for factoring. We introduce an explicit and comprehensive end-to-end construction for the advantage bearing instances. For these instances, quantum computers have, in principle, the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms.
Author(s)
Pirnay, Niklas
Ulitzsch, Vincent Quentin
Wilde, Frederik
Eisert, Jens
Fraunhofer-Institut für Nachrichtentechnik, Heinrich-Hertz-Institut HHI  
Seifert, Jean-Pierre  
Fraunhofer-Institut für Sichere Informationstechnologie SIT  
Journal
Science advances  
Open Access
DOI
10.1126/sciadv.adj5170
Language
English
Fraunhofer-Institut für Sichere Informationstechnologie SIT  
Fraunhofer-Institut für Nachrichtentechnik, Heinrich-Hertz-Institut HHI  
  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024