A Fully Quantum Constraint Satisfying Allocation Method for Multi Resource Cloud Scheduling

Abstract

Cloud computing resource management is a multi-dimensional optimization problem with numerous constraints that is very complex and difficult to solve by the traditional heuristic and hybrid algorithms due to constraints satisfaction and scalability. In this paper, we present a new approach that we call Quantum Constraint-Satisfying Allocation (QCSA), a completely quantum scheduling approach that incorporates the feasibility properties directly into the quantum state space. In contrast to penalty-based Quantum Approximate Optimization Algorithms (QAOA), QCSA only searches through feasible allocations, thereby avoiding post-repair overhead and decreasing sensitivity to the parameterization of the penalties. The proposed approach takes advantage of the constraint-satisfying quantum walks and multi-objective phase biasing to concentrate the computational probability mass on optimal solutions. We offer formal proof of feasibility invariance, bounds on success probability, and study convergence properties. Empirical tests on both synthetic and trace-based workloads on cloud configurations clearly show that QCSA outperforms classical and quantum baselines with respect to packing efficiency, SLA violations, and energy usage. In addition, QCSA is robust to workload variability, scalable across job sizes, and latency of quantum execution is low, which are valuable properties for future quantum-native cloud scheduling frameworks.