Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.21716 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917169705517056 |
|---|---|
| author | Chen, Shengminjie Li, Ziyang Zhou, Hongyi Zhang, Jialin Yang, Wenguo Sun, Xiaoming |
| author_facet | Chen, Shengminjie Li, Ziyang Zhou, Hongyi Zhang, Jialin Yang, Wenguo Sun, Xiaoming |
| contents | In this work, we develop a framework aiming at designing quantum algorithms for combinatorial optimization problems while providing theoretical guarantees on their approximation ratios. The principal innovative aspect of our work is the construction of a time-dependent Lyapunov function that naturally induces a controlled Schrödinger evolution with a time dependent Hamiltonian for maximizing approximation ratios of algorithms. Because the approximation ratio depends on the optimal solution, which is typically elusive and difficult to ascertain a priori, the second novel component is to construct the upper bound of the optimal solution through the current quantum state. By enforcing the non-decreasing property of this Lyapunov function, we not only derive a class of quantum dynamics that can be simulated by quantum devices but also obtain rigorous bounds on the achievable approximation ratio. As a concrete demonstration, we apply our framework to Max-Cut problem, implementing it as an adaptive variational quantum algorithm based on a Hamiltonian ansatz. This algorithm avoids ansatz and graph structural assumptions and bypasses parameter training through a tunable parameter function integrated with measurement feedback. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees Chen, Shengminjie Li, Ziyang Zhou, Hongyi Zhang, Jialin Yang, Wenguo Sun, Xiaoming Quantum Physics In this work, we develop a framework aiming at designing quantum algorithms for combinatorial optimization problems while providing theoretical guarantees on their approximation ratios. The principal innovative aspect of our work is the construction of a time-dependent Lyapunov function that naturally induces a controlled Schrödinger evolution with a time dependent Hamiltonian for maximizing approximation ratios of algorithms. Because the approximation ratio depends on the optimal solution, which is typically elusive and difficult to ascertain a priori, the second novel component is to construct the upper bound of the optimal solution through the current quantum state. By enforcing the non-decreasing property of this Lyapunov function, we not only derive a class of quantum dynamics that can be simulated by quantum devices but also obtain rigorous bounds on the achievable approximation ratio. As a concrete demonstration, we apply our framework to Max-Cut problem, implementing it as an adaptive variational quantum algorithm based on a Hamiltonian ansatz. This algorithm avoids ansatz and graph structural assumptions and bypasses parameter training through a tunable parameter function integrated with measurement feedback. |
| title | A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2512.21716 |