Quantum Computing for Discrete Optimization: A Highlight of Three Technologies

Abstract

Quantum optimization has emerged as a promising frontier of quantum computing, providing novel numerical approaches to mathematical optimization problems. The main goal of this paper is to facilitate interdisciplinary research between the Operations Research (OR) and Quantum Computing communities by helping OR scientists to build initial intuition for-, and offering them a hands-on gateway to quantum-powered methods in the context of discrete optimization. To this end, we consider three quantum-powered optimization approaches that make use of different types of quantum hardware available on the market. To illustrate these approaches, we solve three classical optimization problems: the Traveling Salesperson Problem, Weighted Maximum Cut, and Maximum Independent Set. With a general OR audience in mind, we attempt to provide an intuition behind each approach along with key references, describe the corresponding high-level workflow, and highlight crucial practical considerations. In particular, we emphasize the importance of problem formulations and device-specific configurations, and their impact on the amount of resources required for computation (where we focus on the number of qubits). These points are illustrated with a series of experiments on three types of quantum computers: a neutral atom machine from QuEra, a quantum annealer from D-Wave, and gate-based devices from IBM.

59 pages, 24 figures, 7 tables. Technical supplement: https://alex-bochkarev.github.io/qopt-overview . Source code, problem instances, and other raw data: https://github.com/alex-bochkarev/qopt-overview

References in corpus (29)

• A Quantum Approximate Optimization Algorithm
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Mathematical Foundation of Quantum Annealing
• A practical heuristic for finding graph minors
• Quantum computing with Qiskit
• Challenges and Opportunities in Quantum Optimization
• Computational advantage of quantum random sampling
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Early Fault-Tolerant Quantum Computing
• Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition
• Pegasus: The second connectivity graph for large-scale quantum annealing hardware
• Suppressing quantum circuit errors due to system variability
• A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Aquila: QuEra's 256-qubit neutral-atom quantum computer
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Assessing the Benefits and Risks of Quantum Computers
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Opportunities and Challenges in Fault-Tolerant Quantum Computation
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Industry applications of neutral-atom quantum computing solving independent set problems
• 4-clique Network Minor Embedding for Quantum Annealers
• Synergies Between Operations Research and Quantum Information Science
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Efficient protocol for solving combinatorial graph problems on neutral-atom quantum processors