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

　　8月18日下午，大会特设“女性学者论坛”如期举行，北京大学孔雨晴助理教授和中国科学院计算技术研究所张家琳副研究员共同主持。小编为大家带来4场报告小结，以及备受关注的“理论计算机领域女性研究人员面对的机会与挑战”云讨论精彩回顾。

Optimize the Size and Depth of CNOT Circuits
吴步娇，中国科学院计算技术研究所

　　量子计算由于其并行性，相对于经典计算有着极大的效率上的提升。类似于经典计算需要在经典电路上进行，量子计算的实现则依靠量子电路和量子门。对于一个量子电路而言，如果门数量过多或是电路层数过多，一方面增加了计算中的噪声，另一方面量子脱散现象的产生也容易使系统出现信息丢失。因此我们希望量子电路的门数量以及层数能被优化。

　　这篇文章从 CNOT 电路的角度出发，给出了一种优化的方法。CNOT 电路可以方便地组成 Clifford 电路，是量子电路重要的基本组成部分。本文对于逻辑电路以及物理电路中的 CNOT 电路都给出了优化方法，在深度和电路大小上都做到了阶上的最优。从而作为直接的应用，本文给出了 Clifford 电路以及 Fp 域中的高斯消元算法的优化。此外，他们也给出了一些优化复杂性的结果：在一定情况下对具体的一个 CNOT 电路的优化是 NP-hard 的。

Optimization of Scoring Rules
吴怡凡，北京大学

　　计分法则（scoring rule）常用来对人们对某一个事件的预测进行打分，设计相应法则时，我们通常期望预测者只有在诚实的说出自己对这一事件的真实看法时才能获得最高的分数，也就是满足恰当的（proper）的性质。现实场景往往是所有预测者都对这一预测事件有一个先验的知识，而只要他们再稍加努力，就可以获得更多的信息，从而拥有对应的后验知识。直觉上来说，设计规则者会希望人们都能够去获得后验知识，并将其诚实的报告。而对一些常用的计分法则，存在一些场景使得回答的是否是后验知识对最后的得分影响微小，从而预测者们并没有动机去努力，而只满足于给出基于先验的回答。

　　基于上述背景，这个报告介绍了对恰当记分法则（proper scoring rule）的优化问题。在这个工作中考虑的优化目标是最大程度地增加预测者努力后所获得的期望收益。此处预测者的努力程度是二元的。在这个框架下，这项工作给出了一些简单问题的最优计分法则，为复杂问题给出了最优计分法则的计算方法，并提出了一种近似最优的简单记分法则；而相比下，理论和实践中常见的一些计分法则，例如二次的计分法则（quadratic score）、对多个给分（score）求和等方法，都离最优的计分法则的表现差距较大。在这些结果的证明中，可以看到计分法则的优化问题与传统拍卖设计（auction design）的联系与区别，尤其是对激励相容的刻画是十分相似的。

A 1/2-approximation Algorithm for Maximizing a Non-monotone Weak-submodular Function on a Bounded Integer Lattice
巩素宁，中国海洋大学

　　边际效用递减是一个很常见的概念；在数学上，我们将其形式化为次模函数（submodular function）。对于集合来说，给定集合 S 和不属于 S 的元素 e，次模函数使得在 S 中添加 e的“效用”小于等于在 S 子集中添加 e 的“效用”。类似的，次模函数可以推广到整数格点（integer lattice）上。特别的，将格点表示成向量，我们定义弱次模函数（weak submodular function）：对向量 y 和“小于等于”y 的向量 x，仅在 x 和 y 在某一分量上相等时，才要求在该分量上出现边际效用递减。

　　给定次模函数，我们希望求解 USM（unconstrained submodular maximization）问题，即找到定义域中某一元素，使得其效用最大。对于整数格点和弱次模性质，之前有达到1/3近似比的确定型算法，而作者提出了一个1/2近似比的随机算法。作者的启发来自于定义域为集合时的 Double Greedy 算法，并将其拓展到了整数格点。

Quantum Composite Control for Nonorthogonal States against Decoherence
曹雅，北京邮电大学

　　在量子计算的过程中，会有噪声出现。为了减少噪声对量子状态造成影响，存在着许多不同的方法进行量子态保护，例如量子编码修正，动态解耦（dynamical decoupling），无消相干子空间（decoherence-free subspace）以及基于弱测量的量子控制（weak-measurement based quantum control）。

　　本文给出了一种基于弱测量的量子控制的方法 Quantum Composite Control（QCC）。QCC 以一种精心设计的方式综合了两篇相关的工作，量子反馈控制（QFBC）以及量子前馈控制（QFFC）。QCC 首先对量子态进行预弱测量（pre-weak measurement），在经过噪声信道后进行后弱测量（post-weak measurement），最后通过反馈旋转（feedback rotation）得到结果。本文也通过实验证明，QCC 方法相比于 QFBC、QFFC 以及简单合并他们的方法在表现上有了很大的提高，即给定成功概率的情况下能达到最大保真度，以及给定保真度的情况下可以得到最大的成功概率。

Opportunities and Challenges for Female Researchers in Theoretical Computer Science
主持人
张家琳，中国科学院计算技术研究所
孔雨晴，北京大学

　　论坛以“理论计算机领域女性研究人员面对的机会与挑战”为题，由中国科学院计算技术研究所张家琳副研究员和北京大学孔雨晴助理教授共同主持，邀请中国海洋大学方奇志教授、浙江师范大学张昭教授、苏州科技大学程郁琨教授、美国纽约州立大学石溪分校陈婧助理教授、香港科技大学祁琦助理教授，并特邀复旦大学陈翌佳教授作为嘉宾共同参与讨论，就近年来理论计算机领域选择学术道路的女性不断减少、女学生如何在科研中建立自信、科研资源共享中看不见的性别隔阂等问题分享了自己的观点和看法。以下就部分讨论较为热烈的话题做摘录如下，以飨读者。

女学生似乎在减少，毕业后继续科研的就更少了，主要是什么原因呢？女性选择学术道路的主要挑战是什么？

FQZ：近年来，感觉很多女学生硕士、博士毕业后就停了下来，转去一些个人认为挑战性没那么强的领域，也许和现在的社会压力有关。

CYK：赞同，进入高校教职以后，相对于男性，很多女性需要在多重身份中间平衡，可以把精力集中在科研领域的人越来越少了。

QQ：我不觉得女学生在本科期间成绩有什么区别，很多女学生在博士期间也很优秀，但是到找工作的时候，适合的教职需要一定的时间等待机会，但很多女生有来自家庭或者社会的压力，需要迫切找到一个工作。这是个人选择，我觉得在做理论这一块，没有看到男生和女生的差距，但男孩子更有可能坚持。

CJ：在北美的学术界，大家会有意保持女性的比例，而在国内这个比例仿佛正在减少，可能和现在的社会有关。在中国，一个平衡的家庭对女性来说非常重要，很多女性在就业的时候会首先考虑对家庭的影响。

ZJL：就自己的经历来说，女性做教职其实是有优势的。许多男博士到临近毕业的时候，一想到做教职，会有经济压力，但女性就不需要有这方面的压力。

ZZ：其实有很多女性科研者把家庭和工作兼顾得很好，家庭和工作实际上可以不矛盾。希望更多的女性可以跳出自己设置的天花板，来证明自己的家庭和事业都能获得成功。

CYJ：犹太和以色列CS社群的女性学者越来越多了，许多优秀的女性科学家证明女性也可以做出很出色的科研工作。但不可否认，女性需要花费大量的时间在家庭方面。许多女性会有一种自我暗示：女生就是不行，女生做数学物理就是非常非常少。不应该给人们性别上的差异。需要从一开始就鼓励对科研感兴趣的女生放手去做一些科研，也许从政策层面也需要有一些改变。

女生在科研中如何建立自信呢？

CYK：其实对于男生、女生都是一样的，一开始不要着急，做科研不是一蹴而就的，需要一定时间的积累。等有了第一篇论文之后，慢慢自信就会建立。

ZZ：记得硕士刚毕业的时候，觉得自己什么都不会，必须要获得博士学位。又过了半年获得自己非常满意的文章后发现，原来我还能做成这件事？我觉得需要坚持，到了一定的程度后，水到渠成。对男生和女生都是一样的。

希望对观众们说的话

FQZ：希望女生不要给自己设限，一生很长，积累，尤其在科研上的积累很重要。希望选择家庭的女性也可以给孩子留下一个积极、优秀的母亲。

CYK：坚持之后会有质的飞跃。

ZZ：男性和女性在思维上有一定的差别是可以的，但这不一定是坏事，女生可能在某些领域有更大的优势，重在发现自己。

CJ：很多障碍是自己给自己设的，障碍只存在于自己的想象之中。

CYJ：有许多优秀的成功的女性例子，可以给后来的年轻女性更多的激励。

QQ：以我个人的经历来说，没有明显感受到男女的差别。坚持自己，就不会后悔。