# Quantum Approximation for Wireless Scheduling
## 1 Introduction  
Nowadays, quantum computing and communications have received a lot of attention from academia and industry research communities. In particular, quantum computing-based non-deterministic polynomial-time (NP) hard problem solving is of great interest [1; 2; 3; 4]. Among the available methods, the quantum approximate optimization algorithm (QAOA) is one of the well-known quantum computing-based optimization solvers, and it has been verified that the QAOA outperforms others in many combinatorial problems that are closely related to wireless scheduling problems [5; 6; 7; 8; 9]. Therefore, it is obvious that quantum computing can be used for various communications applications [10; 11; 12; 13].  
In this paper, a wireless scheduling problem is formulated with maximum weight independent set (MWIS) formulation, where the weight is defined as the queue backlog to be transmitted over wireless channels [14; 15; 16; 17]. Due to the fact that the MWIS problem is an NP-hard problem, heuristic algorithms are desired; thus, a QAOA application algorithm, quantum approximate optimization for scheduling (QAOS), is designed to solve MWIS-based wireless scheduling problems.  
The proposed QAOS works as follows. First of all, the objective function and constraint functions are formulated for MWIS. Next, the corresponding objective Hamiltonian and constraint Hamiltonian are designed, which map the objective function and the constraint function, respectively; then, the problem Hamiltonian, which should be optimized, is formulated as the form of linearcombinations of the objective Hamiltonian and constraint Hamiltonian. In addition, the mixing Hamiltonian is formulated using the Pauli-\(X\) operator, which provides the number of different cases via bit flip. Based on the definitions of the problem Hamiltonian and the mixing Hamiltonian, two corresponding unitary operators, i.e., the problem operator and mixing operator, can be defined, respectively; then, the parameterized state can be generated by alternately applying the two unitary operators. The sample solutions can be obtained by the measurement of the expectation value of the problem Hamiltonian on the parameterized state, and the parameters can be optimized in a classical optimization loop, using--for example--stochastic gradient methods. Here, the measurement is used to project a quantum state into one of the eigenstates (=eigenkets) of the problem operator, according to the Copenhagen interpretation [18]. Finally, the optimal solution of the MWIS problem can be obtained by the measurement of the expectation value of the problem Hamiltonian on the state generated by optimal parameters. As verified in performance evaluation, the QAOS outperforms the random search and greedy search.  
QAOS is a novel attempt to carry out application research on wireless communication via QAOA. In the noisy intermediate-scale quantum (NISQ) era, research on hybrid quantum-classical algorithms such as QAOS is essential [6]. However, the research on QAOA-based applications such as QAOS is still in its infancy. Therefore, it is reasonable to increase the utilization of QAOA through convergence and transformation in various fields. From this point of view, QAOS, the novel attempt via QAOA, is very encouraging.  
The rest of this paper is organized as follows. Section 2 presents the preliminary knowledge. Section 3 introduces MWIS-based wireless scheduling modeling. Section 4 presents the details of the proposed QAOS algorithm, and the performance is evaluated in Section 5. Finally, Section 6 concludes the paper.