Minbo Gao

2 accepted papers

2025

Quantum Speedup for Hypergraph Sparsification

Chenghua Liu, Minbo Gao, Zhengfeng Ji, Mingsheng Ying

ICML 2025poster

Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and othe…

Cited by 0 Source ↗PDF ↗Scholar ↗

2023

Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

Minbo Gao, Zhengfeng Ji, Tongyang Li, Qisheng Wang

NeurIPS 2023poster

We propose the first online quantum algorithm for zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{…

Cited by 12 Source ↗PDF ↗Scholar ↗