|
|
 |
|
Jeudi 10 Avril
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle G201 |
| Résumé: |
Quantum algorithms for optimization |
| Description: |
Camille Grange Quantum computation is a new paradigm that is increasingly being exploited today for designing methods to solve optimization problems. Although its application to numerical instances is limited, among other reasons due to the lack of quantum RAM, theoretical advantages are emerging compared to classical approaches for several classes of problems. In this talk, we provide insights into what makes quantum algorithms powerful for optimization and illustrate it with a new bounded-error quantum-classical algorithm. Specifically, this algorithm combines the generalization of Grover Search with dynamic programming to polynomially reduce the worst-case time complexity of NP-hard minimization problems satisfying certain properties. We exemplify it on several scheduling problems. |
|
|
