北京雁栖湖应用数学研究院 北京雁栖湖应用数学研究院

  • 关于我们
    • 院长致辞
    • 理事会
    • 协作机构
    • 参观来访
  • 人员
    • 管理层
    • 科研人员
    • 博士后
    • 来访学者
    • 行政团队
  • 学术研究
    • 研究团队
    • 公开课
    • 讨论班
  • 招生招聘
    • 教研人员
    • 博士后
    • 学生
  • 会议
    • 学术会议
    • 工作坊
    • 论坛
  • 学院生活
    • 住宿
    • 交通
    • 配套设施
    • 周边旅游
  • 新闻
    • 新闻动态
    • 通知公告
    • 资料下载
关于我们
院长致辞
理事会
协作机构
参观来访
人员
管理层
科研人员
博士后
来访学者
行政团队
学术研究
研究团队
公开课
讨论班
招生招聘
教研人员
博士后
学生
会议
学术会议
工作坊
论坛
学院生活
住宿
交通
配套设施
周边旅游
新闻
新闻动态
通知公告
资料下载
清华大学 "求真书院"
清华大学丘成桐数学科学中心
清华三亚国际数学论坛
上海数学与交叉学科研究院
BIMSA > BIMSA Lecture Quantum-Inspired Classical Algorithms for Solving Linear Feasibility Problems
Quantum-Inspired Classical Algorithms for Solving Linear Feasibility Problems
组织者
何颖
演讲者
左钱
时间
2025年01月11日 14:00 至 15:00
地点
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.
北京雁栖湖应用数学研究院
CONTACT

No. 544, Hefangkou Village Huaibei Town, Huairou District Beijing 101408

北京市怀柔区 河防口村544号
北京雁栖湖应用数学研究院 101408

Tel. 010-60661855
Email. administration@bimsa.cn

版权所有 © 北京雁栖湖应用数学研究院

京ICP备2022029550号-1

京公网安备11011602001060 京公网安备11011602001060