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.

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

References in corpus (47)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• The Variational Quantum Eigensolver: a review of methods and best practices
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Towards Practical Quantum Variational Algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum computing for finance: overview and prospects
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Defining and detecting quantum speedup
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Quantum Computation by Adiabatic Evolution
• Perspectives of quantum annealing: Methods and implementations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Computing for Finance: State of the Art and Future Prospects
• Quantum Annealing for Industry Applications: Introduction and Review
• Architectural considerations in the design of a superconducting quantum annealing processor
• Warm-starting quantum optimization
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• 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
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Filtering variational quantum algorithms for combinatorial optimization
• The emerging commercial landscape of quantum computing
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• On the Universality of the Quantum Approximate Optimization Algorithm
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Quantum approximate optimization is computationally universal
• Quantum speedup of branch-and-bound algorithms
• Quantum Computing for Quantum Tunnelling
• Understanding domain-wall encoding theoretically and experimentally
• Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
• Using a quantum computer to solve a real-world problem -- what can be achieved today?
• 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