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 Transactions on Emerging Topics in Computing

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

Yue Ruan, Pengyue Chen, Zhongge Yang, Wei Zhao, Fengxiao Tang, Zhi Liu, Nei Kato

Published Nov 13, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/tetc.2025.3630066

Related papers

Quantum Approximation for Wireless Scheduling

Jaeho Choi, Seunghyeok Oh, Joongheon Kim

This paper proposes an application algorithm based on a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms to solve combinatorial optimization problems and it provides great approximate solutions to non-deterministic polynomial-time (NP) hard problems. QAOA maps the given problem into Hilbert space, and then it generates the Hamiltonian for the given objective and constraint. Then, QAOA finds proper parameters from the classical optimization loop in order to optimize the expectation value of the generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of the Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. The proposed QAOS designs the Hamiltonian of the wireless scheduling problem which is formulated by the maximum weight independent set (MWIS). The designed Hamiltonian is converted into a unitary operator and implemented as a quantum gate operation. After that, the iterative QAOS sequence solves the wireless scheduling problem. The novelty of QAOS is verified with simulation results implemented via Cirq and TensorFlow-Quantum.

arXiv:2004.11229•Applied Sciences•Oct 13, 2020•44 citations

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

Marina Gavrilovskaia, Kwang‐Cheng Chen

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.

IEEE Journal on Selected Areas in Communications•Jan 1, 2026•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

QTIS: A QAOA-Based Quantum Time Interval Scheduler

José A. Tirado-Domínguez, Eladio Gutiérrez, Oscar Plata

Task scheduling with constrained time intervals and limited resources remains a fundamental challenge across domains such as manufacturing, logistics, cloud computing, and healthcare. This study presents a novel variant of the Quantum Approximate Optimization Algorithm (QAOA) designed to address the task scheduling problem formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. The proposed method, referred to as Quantum Time Interval Scheduler (QTIS), integrates an ancilla-assisted quantum circuit to dynamically detect and penalize overlapping tasks, enhancing the enforcement of scheduling constraints. Two complementary implementations are explored for overlap detection: a quantum approach based on RY rotations and CCNOT gates, and a classical alternative relying on preprocessed interval comparisons. QTIS decomposes the problem Hamiltonian, Hp, into two components, each parameterized by a distinct angle. The first component encodes the objective function, while the second captures penalty terms associated with overlapping intervals, which are controlled by the auxiliary circuit. Subsequently, three minimization strategies are evaluated: standard QAOA, T-QAOA, and HT-QAOA, showing that employing separate parameters for the different components of the problem Hamiltonian leads to lower energy values and improved solution quality. Results confirm the efficiency of QTIS in scheduling tasks with fixed temporal windows while minimizing conflicts, demonstrating its potential to advance hybrid quantum-classical optimization in complex scheduling environments.

quant-pharXiv:2511.15590•Future Generation Computer Systems•Nov 20, 2025•1 citation

Neutral-Atom-based Quantum Optimization for Resource Allocation in NOMA Networks

Patatchona Keyela, Remon A. Polus, Soumaya Cherkaoui +1 more

In wireless communication networks, many resource optimization problems are nondeterministic polynomial-time hard (NP-hard) due to their combinatorial nature and high computational complexity. Recently, neutral-atom-based quantum computing has emerged as a promising platform for efficiently solving such problems by leveraging quantum superposition and entanglement. However, its application to wireless communication optimization problems remains largely unexplored. In this paper, we investigate the use of neutral-atom quantum platforms to solve the maximum access problem (MAP), formulated as a mixed-integer programming task that jointly considers admission control, user clustering, channel assignment, and power allocation in a non-orthogonal multiple access (NOMA)-enabled uplink network. To reduce the computational burden, the MAP is equivalently reformulated as a maximum independent set (MIS) problem in graph theory. This reformulation enables the use of the neutral atom platform based on Rydberg atom arrays, where the MIS problem is naturally encoded into the physical geometry and blockade constraints of the quantum system. Numerical results demonstrate the feasibility and potential of this approach for addressing large-scale wireless resource optimization problems.

arXiv:2609.26556•Sep 22, 2026•0 citations

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
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.
This paper proposes an application algorithm based on a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms to solve combinatorial optimization problems and it provides great approximate solutions to non-deterministic polynomial-time (NP) hard problems. QAOA maps the given problem into Hilbert space, and then it generates the Hamiltonian for the given objective and constraint. Then, QAOA finds proper parameters from the classical optimization loop in order to optimize the expectation value of the generated Hamiltonian. Based on the parameters, the optimal solution to the given problem can be obtained from the optimum of the expectation value of the Hamiltonian. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed. The proposed QAOS designs the Hamiltonian of the wireless scheduling problem which is formulated by the maximum weight independent set (MWIS). The designed Hamiltonian is converted into a unitary operator and implemented as a quantum gate operation. After that, the iterative QAOS sequence solves the wireless scheduling problem. The novelty of QAOS is verified with simulation results implemented via Cirq and TensorFlow-Quantum.
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.
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.
Task scheduling with constrained time intervals and limited resources remains a fundamental challenge across domains such as manufacturing, logistics, cloud computing, and healthcare. This study presents a novel variant of the Quantum Approximate Optimization Algorithm (QAOA) designed to address the task scheduling problem formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. The proposed method, referred to as Quantum Time Interval Scheduler (QTIS), integrates an ancilla-assisted quantum circuit to dynamically detect and penalize overlapping tasks, enhancing the enforcement of scheduling constraints. Two complementary implementations are explored for overlap detection: a quantum approach based on RY rotations and CCNOT gates, and a classical alternative relying on preprocessed interval comparisons. QTIS decomposes the problem Hamiltonian, Hp, into two components, each parameterized by a distinct angle. The first component encodes the objective function, while the second captures penalty terms associated with overlapping intervals, which are controlled by the auxiliary circuit. Subsequently, three minimization strategies are evaluated: standard QAOA, T-QAOA, and HT-QAOA, showing that employing separate parameters for the different components of the problem Hamiltonian leads to lower energy values and improved solution quality. Results confirm the efficiency of QTIS in scheduling tasks with fixed temporal windows while minimizing conflicts, demonstrating its potential to advance hybrid quantum-classical optimization in complex scheduling environments.
In wireless communication networks, many resource optimization problems are nondeterministic polynomial-time hard (NP-hard) due to their combinatorial nature and high computational complexity. Recently, neutral-atom-based quantum computing has emerged as a promising platform for efficiently solving such problems by leveraging quantum superposition and entanglement. However, its application to wireless communication optimization problems remains largely unexplored. In this paper, we investigate the use of neutral-atom quantum platforms to solve the maximum access problem (MAP), formulated as a mixed-integer programming task that jointly considers admission control, user clustering, channel assignment, and power allocation in a non-orthogonal multiple access (NOMA)-enabled uplink network. To reduce the computational burden, the MAP is equivalently reformulated as a maximum independent set (MIS) problem in graph theory. This reformulation enables the use of the neutral atom platform based on Rydberg atom arrays, where the MIS problem is naturally encoded into the physical geometry and blockade constraints of the quantum system. Numerical results demonstrate the feasibility and potential of this approach for addressing large-scale wireless resource optimization problems.
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.