近日，第53届国际自动机、语言与编程学术讨论会（The 53rd EATCS International Colloquium on Automata, Languages and Programming, ICALP 2026）公布了论文录用结果。ICALP 是欧洲理论计算机科学协会（EATCS）的旗舰年会，也是理论计算机科学领域历史最悠久、最具影响力的国际学术会议之一，涵盖算法与复杂性（Track A）和自动机、逻辑与语义（Track B）两大方向。本届会议将于2026年7月7–10日在英国伦敦举行。

1946伟德国际源自英国理论计算机科学研究所共有 5 篇论文 被 ICALP 2026 录用（Track A 四篇，Track B 一篇），研究方向涵盖在线学习与机制设计、量子计算和形式化验证，体现了理论所在多个前沿领域的研究活力和学术实力。

在理论计算机科学领域，作者按照姓氏首字母排序。

Track A（算法与复杂性，4篇）

1. Tight Regret Bounds for Fixed-Price Bilateral Trade
作者：陈厚双、金耀楠、陆品燕、张驰豪

本文是在线学习与算法博弈论两个方向的一次有机合作。理论所张驰豪副教授与其博士生陈厚双长期从事在线学习与随机算法研究，上海财经大学陆品燕教授与华为研究员金耀楠博士则是算法博弈论领域的资深专家。论文研究的多轮双边贸易（bilateral trade）问题恰好处于两个方向的交汇点：一个买家和一个卖家通过平台反复进行交易，平台需要在不知道双方估值的情况下逐步学习并设定价格，以最大化贸易收益（gains from trade）——这一问题既是机制设计中的经典模型，又天然地涉及在线决策与懊悔最小化。更具挑战性的是，平台每轮获得的反馈仅有交易是否成功这一个比特信息，而无法观测买卖双方的真实估值。论文的核心关切是在如此稀疏的反馈下，同时满足全局预算平衡（Global Budget Balance）约束——即平台不亏钱——的前提下，以最小的懊悔（regret）逐步逼近最优固定价格。

本文给出了两个紧的结果：（i）当买卖双方估值独立时，证明了  的紧懊悔界；（ii）当双方估值可能相关或由对手选择时，证明了  的下界，将此前最优的  下界大幅提升，且与已知上界匹配。

这两个结果结合前序工作，基本完整给出了固定价格双边贸易在线学习问题中的懊悔刻画。技术上，本文发展了两个具有独立价值的工具：用于处理单比特反馈的 分形消除（fractal elimination） 算法范式，以及面向预算平衡约束的新下界构造技术。

2. Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
作者：王启圣、张志成

在量子信息科学中，迹距离和保真度是衡量量子态接近程度的两个最核心指标。然而，长期困扰学界的一个问题是：【给定纯量子态的独立样本，我们能否以更少的样本量实现高精度估计？】该问题在[Wang, IEEE Trans. Inf. Theory 2024]中被列为开放问题。

本文提出的量子算法彻底回答了这一问题，首次实现了纯量子态之间的迹距离和保真度的样本复杂度为的理论最优估计方法，相比于长期沿用的“SWAP测试”方法（样本复杂度），实现了平方级别的样本复杂度提升，并与理论下界吻合。

该工作的核心洞察在于：两个纯态的 Householder 反射算子的乘积，天然编码了它们之间的夹角信息。通过对这一乘积进行相位估计，研究者巧妙地提取出迹距离和保真度。更关键的是，作者提出并构建了 “纯态多采样化器”（multi-samplizer for pure states） 这一通用工具，能够将任意基于查询的量子算法高效转换为基于样本的量子算法，且采样开销仅与查询次数的平方成正比。这一工具不仅服务于本算法，更有望在量子态层析、量子认证等任务中发挥重要作用。

本文由理论所王启圣副教授和悉尼科技大学张志成博士后研究员共同合作完成。该成果不仅填补了纯态距离估计的复杂度空白，也为量子查询与量子样本模型之间的转换提供了新范式。

3. Quantum Multi-Level Estimation of Functionals of Discrete Distributions
作者：陈柯安、高敏博、李彤阳、王启圣、王昕兆

在量子信息与经典统计的交汇处，一个长期存在的挑战是如何高效估计离散分布的泛函——例如，著名的 -Tsallis 熵。本文由宾夕法尼亚大学陈柯安博士后研究员、中国科公司软件研究所高敏博博士研究生、北京大学助理教授李彤阳、理论所王启圣副教授与北京大学王昕兆博士研究生共同合作完成，提出了一项名为 “量子多级估计”（Quantum Multi-Level Estimation） 的通用框架，为这一难题带来了全新的解决思路。

传统方法往往将所有概率值一视同仁，导致样本效率低下。该工作的关键洞见在于：将分布概率  按指数衰减的长度划分为对数多个区间，随后对每个区间内的分量进行非破坏性奇异值判别，从而隔离出目标概率，实现自适应累加。基于这个观察，本文得到了几乎最优的估计 Tsallis 熵的量子算法。与以往的变时（variable-time）量子算法不同，该框架避免了复杂的控制开销，仅需常数数量的辅助量子比特，大大降低了硬件实现门槛。

作为框架的具体应用，研究者给出了 -Tsallis 熵的量子估计算法：

• 当  时：获得接近最优的查询复杂度 ，显著改进了 [Liu and Wang, SODA 2025] 的  结果。
• 当  时：达到 ，相比于 [Jiao et al., IEEE Trans. Inf. Theory 2017] 的近似最优经典估计展现出量子加速。

据我们所知，这是首个针对非整数  的接近最优量子 -Tsallis 熵估计器。该多级框架不仅适用于 Tsallis 熵，更有望推广至其他分布泛函（如 Rényi 熵、距离度量等），为量子查询复杂度理论开辟了新方向。

4. Strict Hierarchy for Quantum Channel Certification to Unitary
作者：陈柯安、王启圣、张志成

量子信道是否等于某个目标酉变换？这是量子设备验证中的核心问题，被称为量子信道认证（channel certification）。本文彻底解决了这一问题的查询复杂度，在三种不同访问模型下给出了最优算法，揭示了一个严格的复杂度层次结构。

本文针对  维未知信道 ，要求判断其为目标酉信道或是在钻石范数下与之有  的距离。根据访问能力的不同，最优查询复杂度展现出清晰的梯度：

1. 非相干访问模型（Incoherent Access）：每次查询只能获得一个经典输出。最优查询复杂度为 ，匹配 [Fawzi et al., COLT 2023] 的下界。
2. 相干访问模型（Coherent Access）：允许查询量子叠加态上的信道作用。复杂度降至 ，匹配 [Regev and Schiff, ICALP 2008] 的下界。
3. 源码访问模型（Source-Code Access）：最强模型，可直接获得信道的“源码”描述。复杂度进一步降为 ，匹配 [Jeon and Oh, npj Quantum Inf. 2026] 的下界。

该工作给出了三种模型下理论最优的具体量子算法，这是首次对同一认证任务在不同访问模型下进行完整的复杂度分类。三个复杂度量级 、、 之间的差距清晰展示了资源越丰富，认证代价越低的严格递进关系。

方法上，该工作通过利用 Kretschmann–Schlingemann–Werner 定理中 Stinespring 表示的连续性，揭示了纠缠保真度（entanglement fidelity）与钻石范数（diamond norm）之间的量化关系，并由此为基础给出三个不同模型下的统一算法框架。

本文由宾夕法尼亚大学陈柯安博士后研究员、理论所王启圣副教授与悉尼科技大学张志成博士后研究员共同合作完成，揭示了量子查询复杂性理论中的一个严格层次结构，为实践者提供了清晰的指引：在有限实验能力下，知道“最低需要多少次查询”；而在更强控制下，又能获得多少加速。

Track B（自动机、逻辑与语义，1篇）

5. Exploring VASS Parameterised by Geometric Dimension
作者：Wojciech Czerwiński、Roland Guttenberg、Łukasz Orlikowski、Henry Sinclair-Banks、郑扬珞

带状态的向量加法系统（VASS）或 Petri 网是研究并发系统最常用的理论模型之一。VASS 可以看作带有多个非负整数计数器的自动机，传统上，学术界对 VASS 算法问题（如可达性、可覆盖性、有界性等）的复杂度分析主要依赖于其维度 （即计数器的数量）作为参数。然而，近年来的研究发现，求解 VASS 可达性问题的最快算法，如果使用“几何维度”  （即 VASS 中由简单圈产生的向量空间的维度）作为参数，其复杂度表现与使用传统维度  是一致的。在实际的Petri网系统中，由于库所不变量（place invariant）的存在， 常常小于 ，这一发现提示几何维度可能是一个更适合衡量 VASS 问题复杂度的参数。基于此背景，本文系统性地探讨了以几何维度作为参数时，VASS 中的经典算法问题。研究的核心问题在于：既然几何维度在一般可达性算法中表现良好，那么对于可覆盖性、有界性和整数可达性这些常被用作可达性算法子程序的经典问题，我们能否将现有的基于计数器数量  的复杂度结论，全面改进并推广至基于更小的参数——几何维度 ？

文章得出了一系列重要结论，成功将几项关于可覆盖性和有界性等问题的经典结果从依赖传统维度的版本改进到了依赖几何维度。此前，这些结果的证明技术依赖于对“小格局”的刻画。在传统维度参数下小格局的概念是平凡的：即格局的所有计数器值低于某一期望的界。在本文中，作者创新性地引入了“几何小格局”（geometrically small configurations）这一核心概念，将小格局的刻画推广至几何维度参数，使现有的技术能够平滑地应用于几何维度参数。结果上，针对大小为  的 VASS 实例，可覆盖性问题的见证运行长度上限被优化为 ，改进了原先  的界；而无界性问题的见证运行长度上限也被改善至 。然而，对比几何维度与 SCC 维度（即各强联通分类几何维度的最大值）时，研究发现两者存在显著差异。虽然在固定几何维度下，各类经典问题表现出了与固定计数器数量相似的良好特性 ，但较小的 SCC 维度却能展现出极高的表达能力。文章证明了当 SCC 维度为 4 时，VASS 的可达性问题已经是 TOWER 困难的（相比之下，传统维度需达到 8 才具备同等困难度，几何维度也需要达到 7），这表明低 SCC 维度下的系统比同等传统维度下的系统要复杂得多。本文的结论有望对可达性问题这个 VASS 研究的核心问题在几何维度参数下的研究提供技术工具。

本文由理论计算机科学研究所博士生郑扬珞与波兰华沙大学 Wojciech Czerwiński 副教授课题组共同合作完成 。郑扬珞的导师傅育熙教授团队近年来深耕于向量加法系统（VASS）领域的研究。在2024年的 ICALP 会议上，该团队首次创新性地利用“几何维度”这一参数，成功改进了 VASS 可达性问题的复杂度上界，实现了该核心问题自2019年以来的首次实质性突破 。此后，“几何维度”这一概念在学界产生了广泛影响并被多项前沿研究采纳，特别是为2025年 Wojciech Czerwiński 等人设计 3-VASS 的初等复杂性算法提供了重要支撑 。此次跨国深度合作，不仅推动了该领域的理论发展，也进一步彰显了傅育熙教授课题组及理论计算机科学研究所在国际学界的学术地位与认可度。