首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-22日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

　　8月19-22日，大会“量子计算”分论坛如期举行，中国科学院计算技术研究所孙晓明研究员主持。小编为大家带来论坛精彩回顾。

Quantum Algorithms for Convex and Nonconvex Optimization
李彤阳，Massachusetts Institute of Technology

　　优化理论问题在机器学习等领域起到了重要的基础性作用。针对凸优化问题和非凸优化问题，讲者介绍了两个量子算法，都达到了相比于传统算法的多项式级别量子加速。

　　讲者对非凸优化算法展开了详细的介绍。算法主要框架是基于梯度下降。用 Jordan 算法中的量子估值预言机（quantum evaluation oracle）来计算梯度。当梯度大时，用传统的加速梯度下降算法（Accelerated Gradient Descent）；而当梯度小时，用量子模拟（quantum simulation），讲者强调这样可以避免鞍点（saddle point）的问题，进而可以加速梯度下降过程。

　　最后，讲者给出了两个开放性问题，一个是我们能给出 quantum-inspired 传统算法来避免鞍点的问题吗？另一个是量子算法能在全局最优的问题上提供优势吗？

Spooky Complexity at a Distance
季铮锋，University of Technology Sydney

　　讲者为我们带来了关于他与合作者近期的一个重大结果 MIP*=RE 的证明大体想法以及其在数学、物理学等领域得到的推论。所谓 MIP 即有两个 prover 试图在多项式时间内向一个 verifier 证明一件事。一个经典的结论是 MIP=NEXP，即这两个 prover 能证明的事件的集合和一个非确定性图灵机在指数时间内能得到结果的问题集合是相同的。而这里的 MIP* 则是让这两个 prover 能够共享一些量子纠缠，直觉上讲，便是使 verifier 能更好的判断出两个 prover 的回答是否彼此兼容，从而更好的分 辨prover 们是否提供了真实的信息，进而可以获得更多问题的验证。

　　MIP*=RE 的结论直接否定了数学家 Tsirelson 关于任何系统都能够被有限系统逼近的猜想，也否定了算子代数中的 Connes' embedding conjecture，讲者最后对于反例的具体构造、证明过程的进一步简化等问题作出了展望。

Nonlocal Games With Noisy Maximally Entangled States are Decidable
姚鹏晖，南京大学

　　讲者首先介绍了 non-local game 的定义以及推广到量子比特后量子纠缠可能对结果带来的影响，之前的报告已经说明即使共享的量子纠缠态是 EPR state，要得到常数的精确度依然是 RE-complete 的，换言之便是该问题无法保证经典图灵机停机。

　　讲者研究了一类更特定的子问题，并论证了即使在有噪声情况下，如果玩家能够分享最大量子纠缠态，并且有足够多的这样的态的备份，是可以在这个游戏中取得离最优值足够近的答案的。最后，讲者对这一方向的研究前景作出了展望。

Unpredictable Functions and Quantum-secure Authentication
宋方，Portland State University

　　讲者为我们讲解了传统密码学的理论概念如何自然的推广到量子密码学。通过引入关于 unpredictable function 的新定义（blind unpredictable），讲者展示出新的定义能够自然的证明随机函数是不可预测的，并且新定义严格比之前的定义（+1 unpredictable）强。有了对于不可预测方程的新定义，在量子情况下也能很自然的定义出伪随机函数。最后，讲者指出了新的概念在理论上定义量子通信的真实性上的应用以及一些潜在的问题，例如没有特别高效的构造方法、缺乏理论上对于量子电子签名的机制，以及目前只能保证单次通讯的真实性，无法同时验证多个 quantum state 的真实性。

Utility Optimization in a Quantum Key Distribution Network
马雄峰，清华大学

　　相较于前面几个讲座，本次报告更偏向于硬件与实际应用。讲者首先指出，虽然短期来看量子通讯不会直接取代目前依然看似很可靠的经典方法，但量子通讯依然是大势所趋，例如我国已经建成的从北京到上海的量子安全网络以及设想中的全球量子通讯基础设施建设。因此，研究如何分配成本相对较高的 trust node 以及如何构建量子网络能够获得最大收益的研究将十分重要。

　　讲者从潜在的大规模协同攻击、量子密钥的生成与分发、物理学的限制、网络稳定性等多个方面指出了要平衡安全性与效率的潜在问题，并对该领域将来的研究方向作出了展望。

Error Mitigated Quantum Simulation with Near-term Quantum Hardware
袁骁，北京大学

　　本次报告主要探索了在有噪声干扰的量子比特实现的量子电路中，如何修正干扰得到需要的结果。由于在短时期内用物理方法得到的量子比特的精度远低于传统比特的精度，在量子电路的现实应用中往往需要通过去噪声和增加容错位来保证所得到的结果的正确性，而讲者针对几年内就可能出现的由近千个被噪声干扰的量子比特构成的量子计算模块提出了一种减少误差的方法。

　　通过一个量子计算模块在化学问题中的模仿解法，讲者展示了在这样一个动态连续计算环境下的去噪声方法以及其相对于传统计算机的最速下降法能更准确快速的找到能量最低点，特别的是，这一方法不需要假设施加在每个量子比特上的干扰是独立的，这也潜在的为将来带噪声的量子电路的实际运用打下理论基础。最后，讲者指出该方向目前面临的挑战是需要更经济的编码手段、同时测量多个量子比特的方法，而对于特定用途的量子计算模块的特定噪声处理方法也有待探索。