Assessing Quantum and Classical Approaches to Combinatorial
Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms
Assessing Quantum and Classical Approaches to Combinatorial
Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms
Many recent investigations conclude, based on asymptotic complexity analyses, that quantum computers could accelerate combinatorial optimization (CO) tasks relative to a purely classical computer. However, asymptotic analysis alone cannot support a credible claim of quantum advantage. Here, we highlight the challenges involved in benchmarking quantum and classical heuristics for combinatorial …