NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems

Abstract

In the last decade, public and industrial research funding has moved quantum computing from the early promises of Shor's algorithm through experiments to the era of noisy intermediate scale quantum devices (NISQ) for solving real-world problems. It is likely that quantum methods can efficiently solve certain (NP-)hard optimization problems where classical approaches fail. In our perspective, we examine the field of quantum optimization where we solve optimisation problems using quantum computers. We demonstrate this through a proper use case and discuss the current quality of quantum computers, their solver capabilities, and benchmarking difficulties. Although we show a proof-of-concept rather than a full benchmark, we use the results to emphasize the importance of using appropriate metrics when comparing quantum and classical methods. We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.

15 pages, 3 figure, submitted to Frontiers in Quantum Science and Technology, section Quantum Engineering

References in corpus (20)

• A Quantum Approximate Optimization Algorithm
• Simulated Quantum Computation of Molecular Energies
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Annealing for Industry Applications: Introduction and Review
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Filtering variational quantum algorithms for combinatorial optimization
• The emerging commercial landscape of quantum computing
• Quantum approximate optimization is computationally universal
• Understanding domain-wall encoding theoretically and experimentally
• Using a quantum computer to solve a real-world problem -- what can be achieved today?
• Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
• Quantum computing for transport optimization
• PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
• Solving Linear Systems on Quantum Hardware with Hybrid HHL++
• Toward a standardized methodology for constructing quantum computing use cases
• Variational Quantum Continuous Optimization: a Cornerstone of Quantum Mathematical Analysis
• Supply Chain Logistics with Quantum and Classical Annealing Algorithms

Cited by in corpus (11)

• Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Quantum algorithms for scientific computing
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Quantum Annealing based Power Grid Partitioning for Parallel Simulation
• Zeno-effect Computation: Opportunities and Challenges
• A thermodynamic approach to optimization in complex quantum systems
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Dynamic Solutions for Hybrid Quantum-HPC Resource Allocation
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems