Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909779874545664 |
|---|---|
| author | Braida, Arthur Martiel, Simon Todinca, Ioan |
| author_facet | Braida, Arthur Martiel, Simon Todinca, Ioan |
| contents | Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has brought lots of attention to the NISQ era. Several numerical benchmarks try to classify these two metaheuristics however, classical computational power highly limits the performance insights. In this work, we introduce a new parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb-Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_12732 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing Braida, Arthur Martiel, Simon Todinca, Ioan Quantum Physics Data Structures and Algorithms Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has brought lots of attention to the NISQ era. Several numerical benchmarks try to classify these two metaheuristics however, classical computational power highly limits the performance insights. In this work, we introduce a new parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb-Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms. |
| title | Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.12732 |