Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
arXiv:2311.11621 · doi:10.1007/s11128-024-04560-1
Abstract
The optimization of the power consumption of antenna networks is a problem with a potential impact in the field of telecommunications. In this work, we investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA), to the solution of a prototypical model in this field. We use statevector emulation in a high-performance computing environment to compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics. We estimate the circuit depth scaling with the problem size while maintaining a certain level of solution quality, and we extend our analysis up to 31 qubits, which is rarely addressed in the literature. Our calculations show that as the problem size increases, the probability of measuring the exact solution decreases exponentially for both algorithms. This issue is particularly severe when we include constraints in the problem, resulting in full connectivity between the sites. Nonetheless, we observe that the cumulative probability of measuring solutions close to the optimal one remains high also for the largest instances considered in this work. Our findings keep the way open to the application of these algorithms, or variants thereof, to generate suboptimal solutions at scales relevant to industrial use-cases.
14 pages, 12 Figures
References in corpus (36)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Quantum Computing in the NISQ era and beyond
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Efficient Deployment of Multiple Unmanned Aerial Vehicles for Optimal Wireless Coverage
- Quantum annealing with more than one hundred qubits
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Theory of variational quantum simulation
- Training variational quantum algorithms is NP-hard
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Warm-starting quantum optimization
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- A case study in programming a quantum annealer for hard operational planning problems
- Reachability Deficits in Quantum Approximate Optimization
- Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
- Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis
- Digitized-counterdiabatic quantum approximate optimization algorithm
- MAXCUT QAOA performance guarantees for p >1
- The emerging commercial landscape of quantum computing
- Adiabatic Quantum Computing for Random Satisfiability Problems
- On the Universality of the Quantum Approximate Optimization Algorithm
- Quantum algorithms applied to satellite mission planning for Earth observation
- 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
- Evaluation of QAOA based on the approximation ratio of individual samples
- Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
- Shortcuts to Quantum Approximate Optimization Algorithm
- Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
- Fermionic Quantum Approximate Optimization Algorithm
- Elementary Proof of QAOA Convergence
- A Hybrid Classical Quantum Computing Approach to the Satellite Mission Planning Problem
- Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits