Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
arXiv:2409.01373 · doi:10.1016/j.ejor.2025.07.063
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 (53)
- Quantum Computing in the NISQ era and beyond
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Quantum Computational Supremacy
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Perspectives of quantum annealing: Methods and implementations
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Mathematical Foundation of Quantum Annealing
- Realization of an Error-Correcting Surface Code with Superconducting Qubits
- Warm-starting quantum optimization
- A practical heuristic for finding graph minors
- Improving Variational Quantum Optimization using CVaR
- Quantum computing with Qiskit
- Challenges and Opportunities in Quantum Optimization
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Computational advantage of quantum random sampling
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Digitized-counterdiabatic quantum approximate optimization algorithm
- Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
- Randomness in Quantum Mechanics: Philosophy, Physics and Technology
- Early Fault-Tolerant Quantum Computing
- Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition
- On the representation of Boolean and real functions as Hamiltonians for quantum computing
- A cross-disciplinary introduction to quantum annealing-based algorithms
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- Suppressing quantum circuit errors due to system variability
- Constrained mixers for the quantum approximate optimization algorithm
- 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
- Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
- Quantum Algorithms for Scientific Computing and Approximate Optimization
- 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
- Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
- 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
- Synergies Between Operations Research and Quantum Information Science
- 4-clique Network Minor Embedding for Quantum Annealers
- 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