To quantum or not to quantum: towards algorithm selection in near-term quantum optimization

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) constitutes one of the often mentioned candidates expected to yield a quantum boost in the era of near-term quantum computing. In practice, quantum optimization will have to compete with cheaper classical heuristic methods, which have the advantage of decades of empirical domain-specific enhancements. Consequently, to achieve optimal performance we will face the issue of algorithm selection, well-studied in practical computing. Here we introduce this problem to the quantum optimization domain. Specifically, we study the problem of detecting those problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm. As our case study, we compare QAOA against the well-understood approximation algorithm of Goemans and Williamson (GW) on the Max-Cut problem. As exactly predicting the performance of algorithms can be intractable, we utilize machine learning to identify when to resort to the quantum algorithm. We achieve cross-validated accuracy well over 96\%, which would yield a substantial practical advantage. In the process, we highlight a number of features of instances rendering them better suited for QAOA. While we work with simulated idealised algorithms, the flexibility of ML methods we employed provides confidence that our methods will be equally applicable to broader classes of classical heuristics, and to QAOA running on real-world noisy devices.

arXiv commentMinor changes

References in corpus (9)

• Quantum Computing in the NISQ era and beyond
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Reachability Deficits in Quantum Approximate Optimization
• Error-Mitigated Quantum Gates Exceeding Physical Fidelities in a Trapped-Ion System
• Multistart Methods for Quantum Approximate Optimization
• Quantum machine learning and quantum biomimetics: A perspective
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles

Cited by in corpus (25)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Filtering variational quantum algorithms for combinatorial optimization
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Biology and medicine in the landscape of quantum advantages
• A case study of variational quantum algorithms for a job shop scheduling problem
• Challenges of variational quantum optimization with measurement shot noise
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum Architecture Search with Meta-learning
• Evaluation of QAOA based on the approximation ratio of individual samples
• Quantum approximate optimization algorithm for qudit systems
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Architectural Vision for Quantum Computing in the Edge-Cloud Continuum
• An evolving objective function for improved variational quantum optimisation
• GSQAS: Graph Self-supervised Quantum Architecture Search
• Incremental Data-Uploading for Full-Quantum Classification
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Hyperparameter Importance of Quantum Neural Networks Across Small Datasets
• Quantum Approximate Optimization Algorithm Parameter Prediction Using a Convolutional Neural Network
• Resource frugal optimizer for quantum machine learning
• Application of quantum-inspired generative models to small molecular datasets
• On Optimizing Hyperparameters for Quantum Neural Networks
• Tabu-driven Quantum Neighborhood Samplers
• Using machine learning for quantum annealing accuracy prediction
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm