A quantum wire approach to weighted combinatorial graph optimisation problems
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_ | 1866911685998018560 |
|---|---|
| author | de Oliveira, André G. Kombe, Johannes Pelegrí, Gerard Schroff, Paul Wells-Pestell, Maximillian T. Walker, Daniel M. Daley, Andrew J. Pritchard, Jonathan D. |
| author_facet | de Oliveira, André G. Kombe, Johannes Pelegrí, Gerard Schroff, Paul Wells-Pestell, Maximillian T. Walker, Daniel M. Daley, Andrew J. Pritchard, Jonathan D. |
| contents | Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light-shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17115 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A quantum wire approach to weighted combinatorial graph optimisation problems de Oliveira, André G. Kombe, Johannes Pelegrí, Gerard Schroff, Paul Wells-Pestell, Maximillian T. Walker, Daniel M. Daley, Andrew J. Pritchard, Jonathan D. Quantum Physics Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light-shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization. |
| title | A quantum wire approach to weighted combinatorial graph optimisation problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2503.17115 |