From the 2 of 7 linked papers with an AI index.
7 papers
A Correlation-Gap Bound for Nonlinear Gaussian PCA
Minbo Gao, Zhengfeng Ji, Chenghua Liu
The paper shows that for Gaussian data, the Karhunen–Loève (KL) basis is within a factor 1 + O(1/√d) of the optimal basis when a fixed number of coordinates are adaptively retained…
Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining
Chenghua Liu, Yuxin Zhang
The paper proposes a method to create a spectral ε‑sparsifier for any weighted hypergraph using only O(n log n / ε²) hyperedges, eliminating the dependence on the hypergraph’s rank…
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
Minbo Gao, Chenghua Liu, Guangxu Yang +1
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to…
Lévy-Khintchine Structure Enables Fast-Forwardable Lindbladian Simulation
Minbo Gao, Zhengfeng Ji, Chenghua Liu
Simulation of open quantum systems is an area of active research in quantum algorithms. In this work, we revisit the connection between Markovian open-system dynamics and averages…
Accelerating Regression Tasks with Quantum Algorithms
Chenghua Liu, Zhengfeng Ji
Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attract…
Quantum Speedup for Hypergraph Sparsification
Chenghua Liu, Minbo Gao, Zhengfeng Ji +1
Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hyperg…