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

arXiv:2004.11229 · Applied Sciences

Quantum Approximation for Wireless Scheduling

Jaeho Choi, Seunghyeok Oh, Joongheon Kim

Published Oct 13, 2020• 47 citations
arXivHTMLPDF

Abstract

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.

DOI
10.3390/app10207116

Related papers

Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching Problem

Jinyuan Dong, yao zhao, Zhiqiang Li +3 more

Abstract The three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm.

•May 26, 2025•0 citations

An Efficient QAOA via a Polynomial QPU-Needless Approach

Francisco Chicano, Zakaria Abdelmoiz Dahi, Gabriel Luque

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum algorithm described as ansatzes that represent both the problem and the mixer Hamiltonians. Both are parameterizable unitary transformations executed on a quantum machine/simulator and whose parameters are iteratively optimized using a classical device to optimize the problem's expectation value. To do so, in each QAOA iteration, most of the literature uses a quantum machine/simulator to measure the QAOA outcomes. However, this poses a severe bottleneck considering that quantum machines are hardly constrained (e.g. long queuing, limited qubits, etc.), likewise, quantum simulation also induces exponentially-increasing memory usage when dealing with large problems requiring more qubits. These limitations make today's QAOA implementation impractical since it is hard to obtain good solutions with a reasonably-acceptable time/resources. Considering these facts, this work presents a new approach with two main contributions, including (I) removing the need for accessing quantum devices or large-sized classical machines during the QAOA optimization phase, and (II) ensuring that when dealing with some k-bounded pseudo-Boolean problems, optimizing the exact problem's expectation value can be done in polynomial time using a classical computer.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•3 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

Application of quantum approximate optimization algorithm to job shop scheduling problem

Krzysztof Kurowski, Tomasz Pecyna, Mateusz Slysz +3 more

The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.

European Journal of Operational Research•Mar 12, 2023•74 citations

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Gavin E. Crooks

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

arXiv:1811.08419•Bulletin of the American Physical Society•Nov 20, 2018•340 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.

•Apr 22, 2025•0 citations
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.
Abstract The three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum algorithm described as ansatzes that represent both the problem and the mixer Hamiltonians. Both are parameterizable unitary transformations executed on a quantum machine/simulator and whose parameters are iteratively optimized using a classical device to optimize the problem's expectation value. To do so, in each QAOA iteration, most of the literature uses a quantum machine/simulator to measure the QAOA outcomes. However, this poses a severe bottleneck considering that quantum machines are hardly constrained (e.g. long queuing, limited qubits, etc.), likewise, quantum simulation also induces exponentially-increasing memory usage when dealing with large problems requiring more qubits. These limitations make today's QAOA implementation impractical since it is hard to obtain good solutions with a reasonably-acceptable time/resources. Considering these facts, this work presents a new approach with two main contributions, including (I) removing the need for accessing quantum devices or large-sized classical machines during the QAOA optimization phase, and (II) ensuring that when dealing with some k-bounded pseudo-Boolean problems, optimizing the exact problem's expectation value can be done in polynomial time using a classical computer.
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.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.