Tight Lieb–Robinson Bound for approximation ratio in quantum annealing
Abstract 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 attracted a lo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2024-04-01
|
| Series: | npj Quantum Information |
| Online Access: | https://doi.org/10.1038/s41534-024-00832-x |
| _version_ | 1797199243932336128 |
|---|---|
| author | Arthur Braida Simon Martiel Ioan Todinca |
| author_facet | Arthur Braida Simon Martiel Ioan Todinca |
| author_sort | Arthur Braida |
| collection | DOAJ |
| description | Abstract 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 attracted a lot of attention to the NISQ era. Several numerical benchmarks try to compare these two metaheuristics, however, classical computational power highly limits the performance insights. In this work, we introduce a 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. |
| first_indexed | 2024-04-24T07:12:40Z |
| format | Article |
| id | doaj.art-23aa27b369cf484f9c5889ca4dea9576 |
| institution | Directory Open Access Journal |
| issn | 2056-6387 |
| language | English |
| last_indexed | 2024-04-24T07:12:40Z |
| publishDate | 2024-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | npj Quantum Information |
| spelling | doaj.art-23aa27b369cf484f9c5889ca4dea95762024-04-21T11:26:15ZengNature Portfolionpj Quantum Information2056-63872024-04-011011910.1038/s41534-024-00832-xTight Lieb–Robinson Bound for approximation ratio in quantum annealingArthur Braida0Simon Martiel1Ioan Todinca2LIFO - Laboratoire d’Informatique Fondamentale d’Orléans, Université d’OrléansEviden Quantum LabLIFO - Laboratoire d’Informatique Fondamentale d’Orléans, Université d’OrléansAbstract 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 attracted a lot of attention to the NISQ era. Several numerical benchmarks try to compare these two metaheuristics, however, classical computational power highly limits the performance insights. In this work, we introduce a 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.https://doi.org/10.1038/s41534-024-00832-x |
| spellingShingle | Arthur Braida Simon Martiel Ioan Todinca Tight Lieb–Robinson Bound for approximation ratio in quantum annealing npj Quantum Information |
| title | Tight Lieb–Robinson Bound for approximation ratio in quantum annealing |
| title_full | Tight Lieb–Robinson Bound for approximation ratio in quantum annealing |
| title_fullStr | Tight Lieb–Robinson Bound for approximation ratio in quantum annealing |
| title_full_unstemmed | Tight Lieb–Robinson Bound for approximation ratio in quantum annealing |
| title_short | Tight Lieb–Robinson Bound for approximation ratio in quantum annealing |
| title_sort | tight lieb robinson bound for approximation ratio in quantum annealing |
| url | https://doi.org/10.1038/s41534-024-00832-x |
| work_keys_str_mv | AT arthurbraida tightliebrobinsonboundforapproximationratioinquantumannealing AT simonmartiel tightliebrobinsonboundforapproximationratioinquantumannealing AT ioantodinca tightliebrobinsonboundforapproximationratioinquantumannealing |