Quantum Approaches to the Quadratic Assignment Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912356037033984 |
|---|---|
| author | Daly, Nathan Krauss, Thomas Shapiro, Julia |
| author_facet | Daly, Nathan Krauss, Thomas Shapiro, Julia |
| contents | The Quadratic Assignment Problem (QAP) is an NP-hard fundamental combinatorial optimization problem introduced by Koopmans and Beckmann in 1957. The problem is to assign $n$ facilities to $n$ different locations with the goal of minimizing the cost of the total distances between facilities weighted by the corresponding flows. We initiate the study of using Rydberg arrays to find optimal solutions to the QAP and provide a complementing circuit theory to facilitate an easy representation of other hard problems. We provide an algorithm for finding valid and optimal solutions to the QAP using Rydberg arrays. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00182 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Approaches to the Quadratic Assignment Problem Daly, Nathan Krauss, Thomas Shapiro, Julia Quantum Physics The Quadratic Assignment Problem (QAP) is an NP-hard fundamental combinatorial optimization problem introduced by Koopmans and Beckmann in 1957. The problem is to assign $n$ facilities to $n$ different locations with the goal of minimizing the cost of the total distances between facilities weighted by the corresponding flows. We initiate the study of using Rydberg arrays to find optimal solutions to the QAP and provide a complementing circuit theory to facilitate an easy representation of other hard problems. We provide an algorithm for finding valid and optimal solutions to the QAP using Rydberg arrays. |
| title | Quantum Approaches to the Quadratic Assignment Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2505.00182 |