QUBO Formulations of the Downlink MIMO Scheduling Problem in 5G Base Stations

I. INTRODUCTION

• 5G downlink scheduling jointly selects users, resource blocks, MCS, and spatial streams, making optimal scheduling a combinatorial NP-hard problem.The passage notes that exhaustive search becomes computationally prohibitive even for a small number of users.Source: §I · p. 1
• The paper formulates downlink MU-MISO and SU-MIMO scheduling as QUBO and analyzes formulation scalability and the complexity–performance trade-off of suboptimal algorithms.The authors present this as insight into when optimal quantum solving may be useful in practice.Source: §I · pp. 1–2

II. DL SCHEDULING PROBLEM IN 5G

• Each resource block can carry up to NT streams, while each UE must use the same number of streams across its scheduled RBs in a TTI.The system model assumes ZF precoding and represents the NR streams of each UE as KNR virtual single-antenna users.Source: §II · p. 2, A. System model · p. 2

A. System model

• The system model derives equivalent channels and post-combining SNRs for virtual users, then selects a UE's MCS based on its scheduled RBs.It assumes constant fading within an RB, equal power allocation under ZF precoding, and excludes retransmissions.Source: A. System model · pp. 2–3

B. Problem definition

• Binary matrices X and Z represent virtual-user scheduling across RBs and MCS selection for each UE, respectively.X has dimensions KNR × B; Z has dimensions M × K.Source: B. Problem definition · p. 3
• The constraints limit scheduled streams per RB, select one MCS per UE, and require a UE's stream count to remain consistent across its scheduled RBs.The passage identifies the stream-count conditions as alternatives, with either Constraint (10d) or (10e) required.Source: B. Problem definition · p. 3
• The one-MCS and consistent-stream constraints are 5G design choices intended to limit control-signaling overhead and UE receiver complexity, not physical propagation limits.Removing the one-MCS constraint would make control-signaling overhead scale linearly with the number of RBs.Source: B. Problem definition · p. 3

1) MU-MISO:

• With one antenna per UE, MU-MISO maps each UE directly to one virtual user, reduces X to K × B, and removes the per-UE stream-consistency constraints.The passage says this removes Constraints (10d) and (10e).Source: 1) MU-MISO · p. 3

2) SU-MIMO:

• In SU-MIMO, a UE's post-combining SNR depends on its allocated stream count, and its data bits per UE scale linearly with that count.The formulation uses Y, an NR × K binary matrix, to indicate the number of streams scheduled for each UE.Source: 2) SU-MIMO · p. 3
• The SU-MIMO constraints require the same number of streams for a UE across all RBs scheduled for it.This is the stated purpose of Constraint (13d).Source: 2) SU-MIMO · p. 4

1) MU-MIMO:

• MU-MIMO exhaustive search considers MCS and stream assignments across RBs, with the optimal choice of virtual users depending on which other users share each RB.The actual search space is larger than the one presented in.Source: 1) MU-MIMO · p. 4
• A suboptimal MU-MIMO variant restricts each UE to its first n virtual users and selects its largest MCS index with nonzero rate on every scheduled RB.The passage says this variant is expected to perform well when K >> NR and reduces search complexity.Source: 1) MU-MIMO · p. 4
• The greedy MU-MIMO algorithm assigns an RB to the virtual-user set with the highest rate, then constrains later choices to preserve the selected users' stream counts.It fixes the stream counts for users in the selected set.Source: 1) MU-MIMO · p. 4
• In the greedy algorithm's stated worst case, all RBs go to one user and combinations for the other K − 1 users must be considered at each iteration.The resulting worst-case search-space expression begins with B|W|.Source: 1) MU-MIMO · p. 5

2) MU-MISO:

• Brute-force search enumerates MCS assignments and selects the highest-rate UE set for each RB, with complexity growing exponentially in K.Source: 2) MU-MISO · p. 5
• The suboptimal method first searches for the best UE set per RB, then selects each UE's largest MCS index yielding nonzero rate across its scheduled RBs.Source: 2) MU-MISO · p. 5
• Postponing MCS selection reduces the search-space size to B.Source: 2) MU-MISO · p. 5

3) SU-MIMO:

• Exhaustive SU-MIMO search considers per-UE stream allocations and MCS assignments, selecting the UE with the highest rate for a given RB; its search space grows exponentially with K.Source: 3) SU-MIMO · p. 5
• The greedy approach assigns an RB to the UE with the highest rate there; the first RB assigned to a UE fixes its stream count and y_k.Source: 3) SU-MIMO · p. 5
• The greedy algorithm enforces one UE per RB and a consistent stream count for each scheduled UE across RBs, while searching only nonzero-rate options reduces the search at each iteration.Source: 3) SU-MIMO · p. 5
• The greedy algorithm's worst case occurs when the first B - 1 RBs are all scheduled to the same UE.Source: 3) SU-MIMO · p. 5

III. QUBO FORMULATION OF THE PROBLEM

• QUBO uses one binary decision variable per resource-unit decision, minimizes a quadratic expression, and can encode constraints as quadratic penalties.Source: §III · p. 5

A. MU-MIMO

• MU-MIMO terms can reach order NT + 1, and converting higher-order terms to quadratic can require many auxiliary variables when NT > 2.Source: A. MU-MIMO · p. 6
• MU-MIMO constraints applying per UE across RBs are difficult to express as quadratic penalties after converting the system to virtual users, motivating the focus on MU-MISO and SU-MIMO.Source: A. MU-MIMO · p. 6

B. MU-MISO

• The MU-MISO formulation uses a binary |W| by B matrix A to indicate which UE set is scheduled on each RB; its QUBO has |W|B + MK variables.Source: B. MU-MISO · p. 6
• MU-MISO scheduling requires at most one UE set per RB and constraint (10c); the formulation converts these constraints to quadratic penalty terms.Source: B. MU-MISO · p. 6

C. SU-MIMO

• The SU-MIMO scheduling variables X, Y, and Z map to a third-order HUBO formulation.Source: C. SU-MIMO · p. 6
• Rosenberg quadratization repeatedly replaces a frequently occurring variable pair in higher-order monomials with an auxiliary variable and adds a penalty term.Source: C. SU-MIMO · p. 6
• Restricting variable pairs makes each auxiliary variable represent an RB, UE, and stream assignment; quadratization uses BKNR auxiliary variables and K(B + NR + M + BNR) total variables.Source: C. SU-MIMO · p. 7
• Because typical SNR distributions make the highest MCS indices infeasible even with one stream, the formulation can retain only indices 1 through Mk for each UE.Source: C. SU-MIMO · p. 7
• The QUBO adds a constraint allowing only one user-and-stream-count pair per RB, and converts the linear constraints into quadratic penalties.Source: C. SU-MIMO · p. 7

• Simulations verify the Section III QUBO formulations and compare the Section II-C scheduling algorithms’ complexity-performance trade-off.Source: §IV · p. 7
• The simulations use the assumptions and parameter values in Table I, including constant fading within each resource block.Source: §IV · p. 7, Table I · p. 7
• H_k,b(t) denotes the channel matrix for user k at resource block b and transmission time interval t.Source: §IV · p. 7
• M = 28 MCS thresholds are defined as θ_m = 2η_m − 1, with η_m denoting spectral efficiency, and transmitted SNR P_T/N_0 = 10.Source: Table 5.1.3.1 · p. 7

A. Empirical evaluation of the correctness of the QUBO formulations

• Across all tested parameter pairs B = 10–273 and K = 2, 3, 4, multiplying the brute-force binary solution by the QUBO matrix yielded the same value as the optimal objective.Obtaining optimal brute-force solutions soon becomes infeasible when K > 4 because of long execution time.Source: A. Empirical evaluation of the… · p. 7
• When constraint penalties are too small, SU-MIMO solutions violate constraints and can exceed the optimum; the QUBO matrix marks constraint penalties separately from quadratization terms.The penalty λi is scaled with bandwidth B, and the quadratization penalty P is set slightly above the maximum single-stream data bits for an RB.Source: A. Empirical evaluation of the… · pp. 7–8, Figure 3 · p. 8
• With NT = 4, simulated annealing achieves close-to-optimal solutions for MU-MISO and SU-MIMO, never exceeding brute-force results; QUBO variables grow linearly with RB count.These comparisons support the authors’ confidence in the formulations.Source: A. Empirical evaluation of the… · p. 8, Figure 4 · p. 8, Figure 5 · p. 9
• As user count grows, search-space complexity increases exponentially in both modes, while SU-MIMO QUBO variables grow linearly and MU-MISO variables polynomially with KNT.The MU-MISO formulation is practical only for a small number of users.Source: A. Empirical evaluation of the… · p. 8, Figure 6 · p. 9
• Although SU-MIMO logical graphs can be embedded for low UE and RB counts, long physical-qubit chains make implementation infeasible on current state-of-the-art D-Wave annealers.The authors note that continued improvements in qubit connectivity could ease future embedding.Source: A. Empirical evaluation of the… · pp. 8–9

B. Complexity and performance of the scheduling algorithms

• The greedy algorithm’s search space grows only linearly with the number of users, and each plotted point averages 100 time slots.Search-space size is evaluated assuming all M MCS indices are included for all UEs.Source: B. Complexity and performance of the… · p. 9, Figure 7 · p. 9
• Brute force achieves the highest sum rate and greedy the lowest, while random path-loss draws cause non-monotonic rate curves across bandwidth values.The comparison averages sum rate over 100 time slots.Source: B. Complexity and performance of the… · p. 9, Figure 8 · p. 10
• At K = NR = NT = 4, brute force gains 10–40% over greedy, with the gain growing as the number of resource blocks increases.The reported gain is relative to the greedy algorithm.Source: B. Complexity and performance of the… · p. 10, Figure 9 · p. 10
• As the number of users increases, the performance gap between greedy and brute force shrinks; brute-force runs were limited to K ≤ 5.For K = 6, B = 200, and NR = 4, the search space is 2.4 · 10^15.Source: B. Complexity and performance of the… · p. 10, Figure 10 · p. 10

V. CONCLUSION

• The SU-MIMO QUBO formulation’s variable count grows linearly with users while its problem search space grows exponentially.The conclusion notes that tens of users may be considered during rush hours.Source: B. Complexity and performance of the… · p. 9, §V · p. 10
• Optimal SU-MIMO scheduling gains are largest with many resource blocks and few users, supporting solver selection based on system parameters.The conclusion proposes choosing between a QUBO-based optimum solver and a suboptimal low-complexity algorithm.Source: §V · p. 10
• Current D-Wave embeddings are not feasible for SU-MIMO QUBO graphs at 70 or more resource blocks, and long chains make near-optimal solutions very unlikely.The conclusion presents alternative QUBO formulations and MU-MIMO subproblems as possible future directions.Source: §V · pp. 10–11

APPENDIX A EMBEDDING TO D-WAVE TOPOLOGIES

• As SU-MIMO problem size increases, graph density decreases and average degree rises only slightly, but high maximum degree necessitates long physical-qubit chains.The reported graph properties are averages over 100 channel realizations for each {K, B} pair.Source: Appendix A · p. 11, Table III · p. 11
• The study embeds SU-MIMO QUBO graphs for NT = NR = 4 onto Pegasus P16 and Zephyr Z12 using repeated heuristic searches and retaining the embedding with the fewest qubits.The topologies correspond to D-Wave Advantage and Advantage2 annealers.Source: Appendix A · p. 11
• Zephyr Z12 produces shorter chains than Pegasus P16, but long chains threaten solution quality and embedding fails for K = 2, B ≥ 70.Long chains either require high chain strengths or increase chain-break probability; both reduce the probability of close-to-optimal solutions.Source: Appendix A · p. 11, Table V · p. 11, Table IV · p. 11