arXiv:2511.08362quant-phcs.LG2025-11被引 2

用最小几何结构实现高效量子优化,显著提升大规模图分割求解效率。

An Information-Minimal Geometry for Qubit-Efficient Optimization

  • 基于配对统计的一致性约束构建凸多面体,仅用对数宽度电路编码关键信息
  • 在2000节点的无权最大割问题上逼近最优解率超95%,且深度极浅
  • 为量子低宽优化提供可解释基线,适合研究量子优势边界的研究者

量子窄宽优化关注如何用远小于逻辑变量数的量子比特解决大规模组合问题。在无约束二次二值优化(QUBO)中,目标函数仅依赖一阶与二阶统计量,但标准变分算法仍探索指数级大的希尔伯特空间。本文将该问题重构为几何问题:目标本身所需的最小信息表示是什么?聚焦于QUBO,我们证明强制配对统计量之间相互一致性可定义一个凸体——二级Sherali-Adams多面体,该结构恰好捕捉了二次目标所依赖的信息。我们提出一个最小化变分流程:对数宽度电路生成配对矩,可微信息投影确保局部可行性,最大熵集合实现合理全局解码。该信息最小构造在高达N=2000的大规模无权最大割实例上达到近最优近似比,表明在此尺度下,配对多面体几何已充分捕获问题本质结构。本工作通过显式揭示信息最小几何,为量子窄宽优化建立了清晰基准,并明确了真正量子结构出现的必要条件。

原文摘要 · Abstract (English)

Qubit-efficient optimization studies how large combinatorial problems can be addressed with quantum circuits whose width is far smaller than the number of logical variables. In quadratic unconstrained binary optimization (QUBO), objective values depend only on one- and two-body statistics, yet standard variational algorithms explore exponentially large Hilbert spaces. We recast qubit-efficient optimization as a geometric question: what is the minimal representation the objective itself requires? Focusing on QUBO problems, we show that enforcing mutual consistency among pairwise statistics defines a convex body -- the level-2 Sherali-Adams polytope -- that captures the information on which quadratic objectives depend. We operationalize this geometry in a minimal variational pipeline that separates representation, consistency, and decoding: a logarithmic-width circuit produces pairwise moments, a differentiable information projection enforces local feasibility, and a maximum-entropy ensemble provides a principled global decoder. This information-minimal construction achieves near-optimal approximation ratios on large unweighted Max-Cut instances (up to N=2000) at shallow depth, indicating that pairwise polyhedral geometry already captures the relevant structure in this regime. By making the information-minimal geometry explicit, this work establishes a clean baseline for qubit-efficient optimization and sharpens the question of where genuinely quantum structure becomes necessary.

量子优化几何建模低宽量子最大割

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。