Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
arXiv:2308.08245 · doi:10.1109/TQE.2024.3386753
Abstract
Multi-objective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multi-objective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multi-objective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multi-objective shortest path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA) -- the go-to approach for tackling optimization problems on near-term quantum computers -- we examine the Pareto plot that results from the scheme, and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA, and identify key challenges associated with this approach. Finally, through Amazon Braket we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.
References in corpus (23)
- A variational eigenvalue solver on a quantum processor
- Ising formulations of many NP problems
- Barren plateaus in quantum neural network training landscapes
- A Quantum Approximate Optimization Algorithm
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- The Variational Quantum Eigensolver: a review of methods and best practices
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Benchmarking an 11-qubit quantum computer
- Towards Massive Machine Type Communications in Ultra-Dense Cellular IoT Networks: Current Issues and Machine Learning-Assisted Solutions
- Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
- Quantum Computing for Finance: State of the Art and Future Prospects
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Improving Variational Quantum Optimization using CVaR
- -mixers: analytical and numerical results for QAOA
- Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
- Hybrid quantum-classical algorithms for approximate graph coloring
- Generalized swap networks for near-term quantum computing
- Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
- Constrained mixers for the quantum approximate optimization algorithm
- Provable bounds for noise-free expectation values computed from noisy samples
- Dominant Reaction Pathways by Quantum Computing
- Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
- QED driven QAOA for network-flow optimization