Quantum advantage for combinatorial optimization problems, Simplified

2022/12/23 by Márió Szegedy, Szegedy, Mario · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2212.12572

openalex publication_date 2022/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We observe that fault-tolerant quantum computers have an optimal advantage over classical computers in approximating solutions to many NP optimization problems. This observation however gives nothing in practice.

Cited by

• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization

Related

• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Assessing Quantum and Classical Approaches to Combinatorial Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms
• BQP is not in NP
• A brief history of quantum vs classical computational advantage
• Improving an algorithm for quantum computers