Quantum Approximation for Multi-Scale Scheduling
This paper proposes a quantum approximate optimization algorithm (QAOA) method for multi-scale wireless scheduling problems. The QAOA is one of the promising hybrid quantum-classical algorithms for many applications and it provides highly accurate optimization solutions in NP-hard problems. QAOA maps the given problems into Hilbert spaces, and then it generates Hamiltonian for the given objectives and constraints. Then, QAOA finds proper parameters from classical optimization approaches in order to optimize the expectation value of generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. First of all, this paper formulates a multi-scale scheduling problem using maximum weight independent set (MWIS) formulation. Then, for the given MWIS, the proposed QAOS designs the Hamiltonian of the problem. After that, the iterative QAOS sequence solves the scheduling problem. This paper verifies the novelty of the proposed QAOS via simulations implemented by Cirq and TensorFlow-Quantum.
Code (1)
Tasks
SchedulingSimilar Papers 제목 키워드 기반
Hybrid Heuristic Algorithms for Adiabatic Quantum Machine Learning Models
Numerous established machine learning models and various neural network architectures can be restructured as Quadratic Unconstrained Binary Optimization (QUBO) problems. A significant challenge in Adiabatic Quantum Machi…
Fraud DetectionQuantum Machine LearningSchedulingAdaptive Enhanced Quantum-inspired Simulated Bifurcation Algorithm for Population State Perception
Existing quantum-inspired simulated bifurcation algorithms rely on dynamic scheduling methods but lack the ability to adapt effectively to different problem instances. Additionally, during the evolutionary stage, balanci…
Minimizing Delay in Network Function Visualization with Quantum Computing
Network function virtualization (NFV) is a crucial technology for the 5G network development because it can improve the flexibility of employing hardware and reduce the construction of base stations. There are vast servi…
SchedulingQuantum Annealing for Staff Scheduling in Educational Environments
We address a novel staff allocation problem that arises in the organization of collaborators among multiple school sites and educational levels. The problem emerges from a real case study in a public school in Calabria, …
Solving the Extended Job Shop Scheduling Problem with AGVs -- Classical and Quantum Approaches
The subject of Job Scheduling Optimisation (JSO) deals with the scheduling of jobs in an organization, so that the single working steps are optimally organized regarding the postulated targets. In this paper a use case i…
Job Shop SchedulingScheduling