A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees

Quantum Physics arXiv:2512.21716 (quant-ph) [Submitted on 25 Dec 2025] Title:A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees Authors:Shengminjie Chen, Ziyang Li, Hongyi Zhou, Jialin Zhang, Wenguo Yang, Xiaoming Sun View a PDF of the paper titled A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees, by Shengminjie Chen and Ziyang Li and Hongyi Zhou and Jialin Zhang and Wenguo Yang and Xiaoming Sun View PDF Abstract: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. Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2512.21716 [quant-ph] (or arXiv:2512.21716v1 [quant-ph] for this version) https://doi.org/10.48550/arXiv.2512.21716 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Shengminjie Chen [view email] [v1] Thu, 25 Dec 2025 15:38:24 UTC (1,601 KB) Full-text links: Access Paper: View a PDF of the paper titled A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees, by Shengminjie Chen and Ziyang Li and Hongyi Zhou and Jialin Zhang and Wenguo Yang and Xiaoming SunView PDFTeX Source view license Current browse context: quant-ph new | recent | 2025-12 References & Citations INSPIRE HEP NASA ADSGoogle Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) Links to Code Toggle Papers with Code (What is Papers with Code?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs. Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)