4 papers
Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
Shengminjie Chen, Yiwei Gao, Kaifeng Lin +2
Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. W…
A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees
Shengminjie Chen, Ziyang Li, Hongyi Zhou +3
In this work, we develop a framework aiming at designing quantum algorithms for combinatorial optimization problems while providing theoretical guarantees on their approximation ra…
A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation
Jingheng Wang, Shengminjie Chen, Xiaoming Sun +1
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and prac…
Stochastic Quantum Hamiltonian Descent
Sirui Peng, Shengminjie Chen, Xiaoming Sun +1
Stochastic Gradient Descent (SGD) and its variants underpin modern machine learning by enabling efficient optimization of large-scale models. However, their local search nature lim…