Warm-Starting PCE for Traveling Salesman Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909794375303168 |
|---|---|
| author | Carmo, Rafael S. do Reis, Renato Gomes dos Silva, Samuel Fernando F Arruda, Luiz Gustavo E. Fanchini, Felipe F. |
| author_facet | Carmo, Rafael S. do Reis, Renato Gomes dos Silva, Samuel Fernando F Arruda, Luiz Gustavo E. Fanchini, Felipe F. |
| contents | Variational quantum algorithms are promising for combinatorial optimization, but their scalability is often limited by qubit-intensive encoding schemes. To overcome this bottleneck, Pauli Correlation Encoding (PCE) has emerged as one of the most promising algorithms in this scenario. The method offers not only a polynomial reduction in qubit count and a suppression of barren plateaus but also demonstrates competitive performance with state-of-the-art methods on Maxcut. In this work, we propose a warm-start PCE, an extension that incorporates a classical bias from the Goemans-Williamson (GW) randomized rounding algorithm into the loss function to guide the optimization toward improved approximation ratios. We evaluated this method on the Traveling Salesman Problem (TSP) using a QUBO-to-MaxCut transformation for up to $5$ layers. Our results show that Warm-PCE consistently outperforms standard PCE, achieving the optimum solution in $28\text{--}64\%$ of instances, versus $4\text{--}26\%$ for PCE, and attaining higher mean approximation ratios that improve with circuit depth. These findings highlight the practical value of this warm-start strategy for enhancing PCE-based solvers on near-term hardware. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14414 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Warm-Starting PCE for Traveling Salesman Problem Carmo, Rafael S. do Reis, Renato Gomes dos Silva, Samuel Fernando F Arruda, Luiz Gustavo E. Fanchini, Felipe F. Quantum Physics Variational quantum algorithms are promising for combinatorial optimization, but their scalability is often limited by qubit-intensive encoding schemes. To overcome this bottleneck, Pauli Correlation Encoding (PCE) has emerged as one of the most promising algorithms in this scenario. The method offers not only a polynomial reduction in qubit count and a suppression of barren plateaus but also demonstrates competitive performance with state-of-the-art methods on Maxcut. In this work, we propose a warm-start PCE, an extension that incorporates a classical bias from the Goemans-Williamson (GW) randomized rounding algorithm into the loss function to guide the optimization toward improved approximation ratios. We evaluated this method on the Traveling Salesman Problem (TSP) using a QUBO-to-MaxCut transformation for up to $5$ layers. Our results show that Warm-PCE consistently outperforms standard PCE, achieving the optimum solution in $28\text{--}64\%$ of instances, versus $4\text{--}26\%$ for PCE, and attaining higher mean approximation ratios that improve with circuit depth. These findings highlight the practical value of this warm-start strategy for enhancing PCE-based solvers on near-term hardware. |
| title | Warm-Starting PCE for Traveling Salesman Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2509.14414 |