量子科技中心_量科网

该研究团队分析了“解码量子干涉测量法”（DQI）在MAX-k-XOR-SAT典型实例上的表现，这些实例的约束矩阵转置取自LDPC奇偶校验矩阵的标准集合。研究证明：若DQI的解码步骤能修正至LDPC码的经典高效解码阈值，则DQI会受到解空间近优区域内被称为“重叠间隙性质”（OGP）的拓扑特征阻碍。由于OGP被普遍认为是表征经典最优算法性能的精确指标，这一结果表明DQI在优化非结构化MAX-k-XOR-SAT实例时不具备量子优势。 研究人员通过数值实验进一步验证该猜想，发现被推测可达到OGP阈值的经典算法——近似消息传递（AMP）——在相关MAX-k-XOR-SAT实例集合上优于DQI。此外，该工作证明在相同解码阈值假设下，当k值足够大时，深度-1的量子近似优化算法（QAOA）表现会超越DQI。 该结论源于以下发现：DQI在多种标准编码集合的量子Wasserstein度量下具有近似Lipschitz连续性。研究首次确定了固定k值时MAX-k-XOR-SAT的OGP阈值（这一发现可能具有独立价值），并证明该问题同时存在OGP和被称为“混沌性质”的拓扑阻碍机制。最终，研究人员证实这两种拓扑特性会抑制DQI等近似Lipschitz算法在MAX-k-XOR-SAT问题上实现较高的近似比。