Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913465452462080 |
|---|---|
| author | Grange, Camille Poss, Michael Bourreau, Eric T'kindt, Vincent Ploton, Olivier |
| author_facet | Grange, Camille Poss, Michael Bourreau, Eric T'kindt, Vincent Ploton, Olivier |
| contents | Grover Search is currently one of the main quantum algorithms leading to hybrid quantum-classical methods that reduce the worst-case time complexity for some combinatorial optimization problems. Specifically, the combination of Quantum Minimum Finding (obtained from Grover Search) with dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems currently solved by classical dynamic programming. For these problems, the classical dynamic programming complexity in $\mathcal{O}^*(c^n)$, where $\mathcal{O}^*$ denotes that polynomial factors are ignored, can be reduced by a hybrid algorithm to $\mathcal{O}^*(c_{quant}^n)$, with $c_{quant} < c$. In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems for which we give a generic description. Moreover, we extend this algorithm to tackle the 3-machine flowshop problem. Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05741 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems Grange, Camille Poss, Michael Bourreau, Eric T'kindt, Vincent Ploton, Olivier Quantum Physics Optimization and Control Grover Search is currently one of the main quantum algorithms leading to hybrid quantum-classical methods that reduce the worst-case time complexity for some combinatorial optimization problems. Specifically, the combination of Quantum Minimum Finding (obtained from Grover Search) with dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems currently solved by classical dynamic programming. For these problems, the classical dynamic programming complexity in $\mathcal{O}^*(c^n)$, where $\mathcal{O}^*$ denotes that polynomial factors are ignored, can be reduced by a hybrid algorithm to $\mathcal{O}^*(c_{quant}^n)$, with $c_{quant} < c$. In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems for which we give a generic description. Moreover, we extend this algorithm to tackle the 3-machine flowshop problem. Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor. |
| title | Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems |
| topic | Quantum Physics Optimization and Control |
| url | https://arxiv.org/abs/2408.05741 |