QUBO Resolution of the Job Reassignment Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909117567729664 |
|---|---|
| author | Delgado, Iñigo Perez Markaida, Beatriz García Ali, Alejandro Mata de Leceta, Aitor Moreno Fdez. |
| author_facet | Delgado, Iñigo Perez Markaida, Beatriz García Ali, Alejandro Mata de Leceta, Aitor Moreno Fdez. |
| contents | We present a subproblemation scheme for heuristical solving of the JSP (Job Reassignment Problem). The cost function of the JSP is described via a QUBO hamiltonian to allow implementation in both gate-based and annealing quantum computers. For a job pool of $K$ jobs, $\mathcal{O}(K^2)$ binary variables -- qubits -- are needed to solve the full problem, for a runtime of $\mathcal{O}(2^{K^2})$. With the presented heuristics, the average variable number of each of the $D$ subproblems to solve is $\mathcal{O}(K^2/2D)$, and the expected total runtime $\mathcal{O}(D2^{K^2/2D})$, achieving an exponential speedup. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16473 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | QUBO Resolution of the Job Reassignment Problem Delgado, Iñigo Perez Markaida, Beatriz García Ali, Alejandro Mata de Leceta, Aitor Moreno Fdez. Quantum Physics 81P68 We present a subproblemation scheme for heuristical solving of the JSP (Job Reassignment Problem). The cost function of the JSP is described via a QUBO hamiltonian to allow implementation in both gate-based and annealing quantum computers. For a job pool of $K$ jobs, $\mathcal{O}(K^2)$ binary variables -- qubits -- are needed to solve the full problem, for a runtime of $\mathcal{O}(2^{K^2})$. With the presented heuristics, the average variable number of each of the $D$ subproblems to solve is $\mathcal{O}(K^2/2D)$, and the expected total runtime $\mathcal{O}(D2^{K^2/2D})$, achieving an exponential speedup. |
| title | QUBO Resolution of the Job Reassignment Problem |
| topic | Quantum Physics 81P68 |
| url | https://arxiv.org/abs/2309.16473 |