Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Journal on Selected Areas in Communications

Quantum Optimization and Local Search on Conflict Graphs for Radio Resource Allocation

Marina Gavrilovskaia, Kwang‐Cheng Chen

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Quantum optimization is expected to resolve many computationally hard problems, such as Radio Resource Allocation (RRA) in wireless communications and networking. However, given noisy intermediate-scale quantum (NISQ) computers that supply a very limited number of effective logical qubits after quantum error correction, computationally efficient algorithms are highly desirable to facilitate quantum advantages, particularly the required number of qubits. To achieve quantum advantageous optimization by small number of qubits, we formulate RRA as a Maximum Independent Set (MIS) on dense conflict graphs, which is challenging for the Quantum Approximate Optimization Algorithm (QAOA) using NISQ computing machines. We further propose a modified Quantum Local Search (QLS) framework that decomposes the global MIS into overlapping subgraphs defined by a tunable neighborhood radius. Hard (feasibility) constraints are enforced via partial mixers, while soft (adjacency) constraints are resolved in a classical post-processing step. Considering practical interference issues that are typically ignored in quantum computational research, we uniquely extend the method to accommodate minimal-adjacency scenarios by specifying shared boundaries causing limited interference. While complexity analysis shows polynomial scaling in the number of feasible placements, computational experiments demonstrate substantial savings on required qubits and simultaneously achieving optimal solutions across multiple adjacency configurations. Efficient quantum optimization of RRA by NISQ computers of significantly fewer qubits is therefore accomplished.

DOI
10.1109/jsac.2026.3690424

Related papers

A Quantum Approximate Optimization Algorithm on Conflict Graphs for Radio Resource Allocation

Marina Gavrilovskaia, Kwang‐Cheng Chen

Radio resource allocation is always a central and complex computational task in state-of-the-art wireless networks. Computationally efficient implementation of radio resource allocation is certainly desirable in wireless networks, and can be generalized to many resource allocation/management problems in C4ISR systems. Quantum optimization, an emerging quantum computation technology, suggests a new avenue toward (radio) resource allocation particularly potential to reduce computing latency in systems. Quantum approximation optimization algorithm (QAOA) was recently shown to possibly achieve resource allocation (RRA) in limited scope, while the generalization of QAOA for RRA remains an active research subject. Considering OFDMA resource allocation, this paper extends QAOA to multiple radio blocks by quantum state preparation, and takes the interference between adjacent radio resource units into account by introducing the conflict graphs to formulate quantum optimization. Computational experiments successfully verify proposed quantum optimization to RRA.

IEEE Military Communications Conference (MILCOM)•Oct 6, 2025•1 citation

Subspace-Confined QAOA with Generalized Dicke States for Multi-Channel Allocation in 5G CBRS Networks

Gunsik Min, Youngjin Seo, Jun Heo

Efficient spectrum sharing in the Citizens Broadband Radio Service (CBRS) band is essential for maximizing 5G network capacity, particularly when high-traffic base stations require simultaneous access to multiple channels. Standard formulations of the Quantum Approximate Optimization Algorithm (QAOA) impose such multi-channel constraints using penalty terms, so most of the explored Hilbert space corresponds to invalid assignments. We propose a subspace-confined QAOA tailored to CBRS multi-channel allocation, in which each node-wise channel register is initialized in a Generalized Dicke state and evolved under an intra-register XY mixer. This ansatz confines the dynamics to a tensor product of Johnson graphs that exactly encode per-node Hamming-weight constraints. For an 8-node CBRS interference graph with 24 qubits, the effective search space is reduced from the full Hilbert space of size $2^{24}$ to 2916 feasible configurations. Within this subspace, the algorithm converges rapidly to low-conflict assignments without large penalty coefficients. Simulations on instances with up to eight nodes show that the proposed ansatz achieves near-optimal conflict levels and consistently outperforms standard penalty-based QAOA and a greedy classical heuristic in terms of feasibility. Noise simulations with depolarizing channels further indicate that the constraint-preserving structure maintains a high feasibility ratio in NISQ-relevant error regimes.

quant-pharXiv:2601.16396•Scientific Reports•Jan 26, 2026•0 citations

Recursive QAOA for Interference-Aware Resource Allocation in Wireless Networks

Kuan-Cheng Chen, Hiromichi Matsuyama, Wei-hao Huang +1 more

Discrete radio resource management problems in dense wireless networks are naturally cast as quadratic unconstrained binary optimization (QUBO) programs but are difficult to solve at scale. We investigate a quantum-classical approach based on the Recursive Quantum Approximate Optimization Algorithm (RQAOA), which interleaves shallow QAOA layers with variable elimination guided by measured single- and two-qubit correlators. For interference-aware channel assignment, we give a compact QUBO/Ising formulation in which pairwise interference induces same-channel couplings and one-hot constraints are enforced via quadratic penalties (or, optionally, constraint-preserving mixers). Within RQAOA, fixing high-confidence variables or relations reduces the problem dimension, stabilizes training, and concentrates measurement effort on a shrinking instance that is solved exactly once below a cutoff. On simulated instances of modest size, including a four-user, four-channel example, the method consistently returns feasible assignments and, for the demonstrated case, attains the global optimum. These results indicate that recursion can mitigate parameter growth and feasibility issues that affect plain QAOA, and suggest a viable pathway for near-term quantum heuristics in wireless resource allocation.

quant-pharXiv:2602.07483•Feb 10, 2026•0 citations

Quantum Approximate Optimization Algorithm for Knapsack Resource Allocation Problems in Communication Systems

Junaid ur Rehman, Hayder Al-Hraishawi, Symeon Chatzinotas

Quantum technologies have recently scaled up from laboratories into commercial applications thanks to the rapid technical developments and the growing investments in quantum computing. These developments open up the way for the emergence of the so-called noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithms (QAOAs) represent a class of algorithms tailored for the NISQera computing for provisioning tangible quantum advantages. Meanwhile, wireless communications networks have become more complex over time and the pressure to conquer communications complexity is intense for both researchers and system designers. Specifically, a major optimization problem in this context is the resource allocation in modern communications where typically appears as an intricate 0/1 knapsack (0/1-KP) problem and finding its optimal solution using classical computers is prohibitively difficult. Thus, a parallel QAOA framework for optimizing the 0/1- KP problems is proposed in this paper. The proposal has the space complexity of$\mathcal{O} (n)$and pseudopolynomial time complexity of$\mathcal{O} (nW)$, where$W$is the knapsack's total capacity and$n$is the total number of items. However, the proposed QAOA solution is highly parallel and can be implemented on$M$NISQ devices of n-qubits each to obtain$\mathcal{O}(n W / M)$time complexity and$\mathcal{O} (nM)$space complexity. Numerical experiments show high approximation ratios even for shallow depth QAOA instances.

International Conference on Communications•May 28, 2023•12 citations

The Divided-QUBO-Based Quantum Algorithm for Optimal Wireless Link Scheduling

Yue Ruan, Pengyue Chen, Zhongge Yang +4 more

Link scheduling in wireless communication aims to minimize interference and maximize channel utilization. When accurate channel state information (CSI) is available, optimal scheduling can be achieved by modeling link interference as a conflict graph and solving the weighted maximum independent set problem (WMIS). However, the NP-hard nature of WMIS presents significant computational challenges in obtaining high-quality solutions efficiently. To tackle this challenge, we first propose a divided QUBO model, which formulates the original problem into sub-models within non-overlapping subspaces. Building upon this, we then develop a corresponding algorithm called DQAOA, which further narrows the search space within solution bounds established by classical greedy algorithms and semi-definite programming. Using a specialized mixing operator (the XY-mixer), the algorithm confines the evolution to each reduced subspace and runs in parallel. Additionally, an auxiliary Hamiltonian inspired by counter-diabatic driving is introduced into the core evolution equation to accelerate convergence. The experimental results on the IBM Qiskit platform demonstrate that DQAOA outperforms classical methods and other QAOA variants, providing an efficient and reliable solution for optimal link scheduling in wireless networks.

IEEE Transactions on Emerging Topics in Computing•Nov 13, 2025•0 citations

Efficient hybrid variational quantum algorithm for solving graph coloring problem

Dongmei Liu, Li, Jian, Cheng, Xiubo +3 more

In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the $k$-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.

arXiv:2504.21335•Apr 30, 2025•0 citations
Quantum optimization is expected to resolve many computationally hard problems, such as Radio Resource Allocation (RRA) in wireless communications and networking. However, given noisy intermediate-scale quantum (NISQ) computers that supply a very limited number of effective logical qubits after quantum error correction, computationally efficient algorithms are highly desirable to facilitate quantum advantages, particularly the required number of qubits. To achieve quantum advantageous optimization by small number of qubits, we formulate RRA as a Maximum Independent Set (MIS) on dense conflict graphs, which is challenging for the Quantum Approximate Optimization Algorithm (QAOA) using NISQ computing machines. We further propose a modified Quantum Local Search (QLS) framework that decomposes the global MIS into overlapping subgraphs defined by a tunable neighborhood radius. Hard (feasibility) constraints are enforced via partial mixers, while soft (adjacency) constraints are resolved in a classical post-processing step. Considering practical interference issues that are typically ignored in quantum computational research, we uniquely extend the method to accommodate minimal-adjacency scenarios by specifying shared boundaries causing limited interference. While complexity analysis shows polynomial scaling in the number of feasible placements, computational experiments demonstrate substantial savings on required qubits and simultaneously achieving optimal solutions across multiple adjacency configurations. Efficient quantum optimization of RRA by NISQ computers of significantly fewer qubits is therefore accomplished.
Radio resource allocation is always a central and complex computational task in state-of-the-art wireless networks. Computationally efficient implementation of radio resource allocation is certainly desirable in wireless networks, and can be generalized to many resource allocation/management problems in C4ISR systems. Quantum optimization, an emerging quantum computation technology, suggests a new avenue toward (radio) resource allocation particularly potential to reduce computing latency in systems. Quantum approximation optimization algorithm (QAOA) was recently shown to possibly achieve resource allocation (RRA) in limited scope, while the generalization of QAOA for RRA remains an active research subject. Considering OFDMA resource allocation, this paper extends QAOA to multiple radio blocks by quantum state preparation, and takes the interference between adjacent radio resource units into account by introducing the conflict graphs to formulate quantum optimization. Computational experiments successfully verify proposed quantum optimization to RRA.
Efficient spectrum sharing in the Citizens Broadband Radio Service (CBRS) band is essential for maximizing 5G network capacity, particularly when high-traffic base stations require simultaneous access to multiple channels. Standard formulations of the Quantum Approximate Optimization Algorithm (QAOA) impose such multi-channel constraints using penalty terms, so most of the explored Hilbert space corresponds to invalid assignments. We propose a subspace-confined QAOA tailored to CBRS multi-channel allocation, in which each node-wise channel register is initialized in a Generalized Dicke state and evolved under an intra-register XY mixer. This ansatz confines the dynamics to a tensor product of Johnson graphs that exactly encode per-node Hamming-weight constraints. For an 8-node CBRS interference graph with 24 qubits, the effective search space is reduced from the full Hilbert space of size 2242^{24}224 to 2916 feasible configurations. Within this subspace, the algorithm converges rapidly to low-conflict assignments without large penalty coefficients. Simulations on instances with up to eight nodes show that the proposed ansatz achieves near-optimal conflict levels and consistently outperforms standard penalty-based QAOA and a greedy classical heuristic in terms of feasibility. Noise simulations with depolarizing channels further indicate that the constraint-preserving structure maintains a high feasibility ratio in NISQ-relevant error regimes.
Discrete radio resource management problems in dense wireless networks are naturally cast as quadratic unconstrained binary optimization (QUBO) programs but are difficult to solve at scale. We investigate a quantum-classical approach based on the Recursive Quantum Approximate Optimization Algorithm (RQAOA), which interleaves shallow QAOA layers with variable elimination guided by measured single- and two-qubit correlators. For interference-aware channel assignment, we give a compact QUBO/Ising formulation in which pairwise interference induces same-channel couplings and one-hot constraints are enforced via quadratic penalties (or, optionally, constraint-preserving mixers). Within RQAOA, fixing high-confidence variables or relations reduces the problem dimension, stabilizes training, and concentrates measurement effort on a shrinking instance that is solved exactly once below a cutoff. On simulated instances of modest size, including a four-user, four-channel example, the method consistently returns feasible assignments and, for the demonstrated case, attains the global optimum. These results indicate that recursion can mitigate parameter growth and feasibility issues that affect plain QAOA, and suggest a viable pathway for near-term quantum heuristics in wireless resource allocation.
Quantum technologies have recently scaled up from laboratories into commercial applications thanks to the rapid technical developments and the growing investments in quantum computing. These developments open up the way for the emergence of the so-called noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithms (QAOAs) represent a class of algorithms tailored for the NISQera computing for provisioning tangible quantum advantages. Meanwhile, wireless communications networks have become more complex over time and the pressure to conquer communications complexity is intense for both researchers and system designers. Specifically, a major optimization problem in this context is the resource allocation in modern communications where typically appears as an intricate 0/1 knapsack (0/1-KP) problem and finding its optimal solution using classical computers is prohibitively difficult. Thus, a parallel QAOA framework for optimizing the 0/1- KP problems is proposed in this paper. The proposal has the space complexity ofO(n)\mathcal{O} (n)O(n)and pseudopolynomial time complexity ofO(nW)\mathcal{O} (nW)O(nW), whereWWWis the knapsack's total capacity andnnnis the total number of items. However, the proposed QAOA solution is highly parallel and can be implemented onMMMNISQ devices of n-qubits each to obtainO(nW/M)\mathcal{O}(n W / M)O(nW/M)time complexity andO(nM)\mathcal{O} (nM)O(nM)space complexity. Numerical experiments show high approximation ratios even for shallow depth QAOA instances.
Link scheduling in wireless communication aims to minimize interference and maximize channel utilization. When accurate channel state information (CSI) is available, optimal scheduling can be achieved by modeling link interference as a conflict graph and solving the weighted maximum independent set problem (WMIS). However, the NP-hard nature of WMIS presents significant computational challenges in obtaining high-quality solutions efficiently. To tackle this challenge, we first propose a divided QUBO model, which formulates the original problem into sub-models within non-overlapping subspaces. Building upon this, we then develop a corresponding algorithm called DQAOA, which further narrows the search space within solution bounds established by classical greedy algorithms and semi-definite programming. Using a specialized mixing operator (the XY-mixer), the algorithm confines the evolution to each reduced subspace and runs in parallel. Additionally, an auxiliary Hamiltonian inspired by counter-diabatic driving is introduced into the core evolution equation to accelerate convergence. The experimental results on the IBM Qiskit platform demonstrate that DQAOA outperforms classical methods and other QAOA variants, providing an efficient and reliable solution for optimal link scheduling in wireless networks.
In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the kkk-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve kkk-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.