Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913162097328128 |
|---|---|
| author | Baldazzi, Alessio Azzini, Stefano Pavesi, Lorenzo |
| author_facet | Baldazzi, Alessio Azzini, Stefano Pavesi, Lorenzo |
| contents | The travelling salesman problem is a well-known example of computationally-hard combinatorial problem for classical machines. Here, we propose a novel variational quantum algorithm to solve it. The method is based on the preparation of two maximally entangled quantum registers whose correlations are assigned to different paths between pairs of cities. For $N$ cities, this encoding requires $2 \lceil\log_2 N\rceil$ qubits and the solution to the problem is directly found in the correlation matrix of the two registers composing the overall trial state. As a proof-of-concept experiment, we implement this algorithm for generic problems with four cities on a reconfigurable room-temperature silicon photonic circuit with integrated photon-pair sources, used to initialize maximally entangled path-encoded single-photon states. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02696 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation Baldazzi, Alessio Azzini, Stefano Pavesi, Lorenzo Quantum Physics The travelling salesman problem is a well-known example of computationally-hard combinatorial problem for classical machines. Here, we propose a novel variational quantum algorithm to solve it. The method is based on the preparation of two maximally entangled quantum registers whose correlations are assigned to different paths between pairs of cities. For $N$ cities, this encoding requires $2 \lceil\log_2 N\rceil$ qubits and the solution to the problem is directly found in the correlation matrix of the two registers composing the overall trial state. As a proof-of-concept experiment, we implement this algorithm for generic problems with four cities on a reconfigurable room-temperature silicon photonic circuit with integrated photon-pair sources, used to initialize maximally entangled path-encoded single-photon states. |
| title | Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2511.02696 |