量子科技中心_量科网

该研究团队提出了一种通用框架，通过自适应稀疏化方法解决约束条件众多（n≫d）的线性规划问题。该框架从原理上拓展了[Assadi '23]的匹配问题技术至通用线性规划领域，并强化了[Clarkson '95]经典精确求解算法的鲁棒性。该框架将线性规划求解转化为对小型自适应采样子问题“低冲突预言机”的迭代调用，研究团队通过乘性权重更新方法对此进行了理论分析。 主要研究成果展现了该范式的多重优势：首先，研究人员开发出Clarkson算法的量子版本，仅需使用约束矩阵的~O(√n d³)行查询即可找到精确解。这是通过广义Grover搜索加速经典瓶颈（冲突约束检测）实现的，使量子计算模块与经典求解器实现解耦。其次，当 packing约束具有“简单”特性时，该框架为混合packing-covering问题提供了当前最优算法。通过保留所有packing约束同时仅对covering约束进行采样，该工作显著降低了问题宽度，从而在经典与量子查询模型中都实现了更快的求解速度。 该工作为加速线性规划求解器提供了模块化且强大的方法论，其创新性体现在：1）建立量子计算与经典线性规划理论的新桥梁；2）针对混合约束问题提出突破性的宽度优化策略；3）通过低冲突预言机的创新设计统一处理精确与近似求解场景。这些理论突破有望在运筹优化、量子机器学习等领域产生重要应用价值。