Quantum Approximation for Wireless Scheduling
| Autor: | Seunghyeok Oh, Jaeho Choi, Joongheon Kim |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Computer science Other Computer Science (cs.OH) Scheduling (production processes) FOS: Physical sciences 02 engineering and technology Expectation value NP-hard lcsh:Technology 01 natural sciences lcsh:Chemistry quantum approximate optimization algorithm (QAOA) symbols.namesake Quantum gate Computer Science - Other Computer Science quantum application 0103 physical sciences maximum weight independent set (MWIS) 0202 electrical engineering electronic engineering information engineering General Materials Science wireless scheduling 010306 general physics lcsh:QH301-705.5 Instrumentation Fluid Flow and Transfer Processes Quantum Physics Sequence lcsh:T Process Chemistry and Technology General Engineering Hilbert space 020206 networking & telecommunications lcsh:QC1-999 Computer Science Applications lcsh:Biology (General) lcsh:QD1-999 lcsh:TA1-2040 Independent set symbols Unitary operator lcsh:Engineering (General). Civil engineering (General) Quantum Physics (quant-ph) lcsh:Physics Hamiltonian (control theory) |
| Zdroj: | Applied Sciences Volume 10 Issue 20 Applied Sciences, Vol 10, Iss 7116, p 7116 (2020) |
| DOI: | 10.48550/arxiv.2004.11229 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|