Beijing Institute of Mathematical Sciences and Applications

Ying He

Qian Zuo

Saturday, January 11, 2025 2:00 PM - 3:00 PM

A3-3-301

Zoom 293 812 9202 (BIMSA)

We present a classical algorithm for linear feasibility problems $Ax \leq b$, where the input matrix $A$ is stored in a data structure suitable for QRAM-based state preparation. Specifically, given an matrix $A \in R^{m \times n}$ with a vector $b \in R^{m}$ which supports certain efficient $\ell_{2}$-norm importance sampling queries. Then, after $T = O(\| A \|^{2}_{F} L^2 \log (1/\epsilon^2))$ steps of iteration, for some vector $x \in R^{n}$ satisfying $d(x_{T}, P) \leq \epsilon d(x, P)$, we can output a measurement of $|x \rangle$ in the computational basis and output an entry of $x$ with classical algorithms that run in $O (\| A \|^{6}_{F} \kappa^{6}_{F} L^6/ \epsilon^2 )$ time, where $L$ be a Hoffman constant and $\kappa_{F} = \| A \|_{F} \| A^{\dagger} \|$. Our work combines techniques from sketching algorithms and optimization with the quantum-inspired literature. This avenue shows promise for feasible implementations of classical linear inequality in quantum-inspired settings, offering a basis for comparison against future quantum computers.

左钱，2022年6月毕业于武汉大学，获计算数学博士学位；2022年7月进入北京大学计算机学院前沿计算研究中心进行博士后研究，2024年12月进入安徽大学工作。研究兴趣包括随机算法、量子算法、受量子启发的经典算法等，目前主持国家自然科学基金青年基金项目1项，主持计算科学湖北省重点实验室开放课题基金项目1项，参与国家自然科学基金重大研究计划项目、面上项目。现已在Numerical Algorithms、Journal of Computational and Applied Mathematics、Numerical Linear Algebra with Applications等计算数学专业杂志上发表SCI论文8篇。