孙晓明
博士 研究员 博士生导师
中国科学院计算技术研究所 前瞻研究实验室、计算机体系结构国家重点实验室
量子计算；算法复杂性；社会网络近似算法；通信复杂性；判定树复杂性；组合数学
个性化签名
 姓名：孙晓明
 目前身份：在职研究人员
 担任导师情况：博士生导师
 学位：博士

学术头衔：
博士生导师
 职称：高级研究员

学科领域：
软件理论
 研究兴趣：量子计算；算法复杂性；社会网络近似算法；通信复杂性；判定树复杂性；组合数学
孙晓明
简历:
1997年9月2001年7月：清华大学计算机系，学士毕业
2001年9月2005年7月：清华大学计算机系，博士毕业
2005年8月2008年12月：清华大学高等研究院，助理研究员
2008年12月2011年9月：清华大学高等研究院，副研究员
2011年9月至今：中国科学院计算技术研究所
研究方向：量子计算；算法复杂性；社会网络近似算法；通信复杂性；判定树复杂性；组合数学
社会任职:
中国计算机学会理论计算机专业委员会主任和学术工作委员会委员，中国密码学会密码数学专委委员，全国量子计算与测量标准化技术委员会委员，国际学术会议COCOON指导委员会委员，《软件学报》,《计算机研究与发展》，《JCST》《FCS》等杂志编委和《中国科学:信息科学》青年编委。
获奖及荣誉:
中国科学院优秀导师奖、朱李月华优秀教师奖，中国密码学会密码创新奖、中国密码学会优秀青年奖，获首批国家自然科学基金优秀青年基金资助，清华大学学术新人奖、青年教师教学优秀奖等。
承担科研项目情况:
[1] 国家自然科学基金重点项目：大数据结构与关系的发现与简约计算方法，项目负责人；
[2] 中国科学院王宽诚率先人才计划卢嘉锡国际团队项目：“网络数据科学与大数据引擎系统”国际团队，项目负责人；
[3] 中科院战略性先导科技专项：量子计算与量子模拟理论，课题负责人；
[4] 国家自然科学基金优秀青年科学基金项目：理论计算机科学，项目负责人。

主页访问
4

关注数
0

成果阅读
26

成果数
7
【期刊论文】Revisiting Online Quantum State Learning
AAAI20 Technical Tracks 4 ，2020，34（4）：
2020年04月03日
In this paper, we study the online quantum state learning problem which is recently proposed by Aaronson et al. (2018). In this problem, the learning algorithm sequentially predicts quantum states based on observed measurements and losses and the goal is to minimize the regret. In the previous work, the existing algorithms may output mixed quantum states. However, in many scenarios, the prediction of a pure quantum state is required. In this paper, we first propose a FollowthePerturbedLeader (FTPL) algorithm that can guarantee to predict pure quantum states. Theoretical analysis shows that our algorithm can achieve an O(√T) expected regret under some reasonable settings. In the case that the pure state prediction is not mandatory, we propose another deterministic learning algorithm which is simpler and more efficient. The algorithm is based on the online gradient descent (OGD) method and can also achieve an O(√T) regret bound. The main technical contribution of this result is an algorithm of projecting an arbitrary Hermitian matrix onto the set of density matrices with respect to the Frobenius norm. We think this subroutine is of independent interest and can be widely used in many other problems in the quantum computing area. In addition to the theoretical analysis, we evaluate the algorithms with a series of simulation experiments. The experimental results show that our FTPL method and OGD method outperform the existing RFTL approach proposed by Aaronson et al. (2018) in almost all settings. In the implementation of the RFTL approach, we give a closedform solution to the algorithm. This provides an efficient, accurate, and completely executable solution to the RFTL method.
无
0

4浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】On the Degree of Boolean Functions as Polynomials over Zm
arXiv，2020，（）：
2020年05月01日
Polynomial representations of Boolean functions over various rings such as Z and Zm have been studied since Minsky and Papert (1969). From then on, they have been employed in a large variety of fields including communication complexity, circuit complexity, learning theory, coding theory and so on. For any integer m≥2, each Boolean function has a unique multilinear polynomial representation over ring Zm. The degree of such polynomial is called modulom degree, denoted as degm(⋅). In this paper, we investigate the lower bound of modulom degree of Boolean functions. When m=pk (k≥1) for some prime p, we give a tight lower bound that degm(f)≥k(p−1) for any nondegenerated function f:{0,1}n→{0,1}, provided that n is sufficient large. When m contains two different prime factors p and q, we give a nearly optimal lower bound for any symmetric function f:{0,1}n→{0,1} that degm(f)≥n2+1p−1+1q−1.
无
0

2浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】Revisiting Online Quantum State Learning
arXiv，2019，（）：
2019年07月11日
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envyfreeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols [16]. For envyfreeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envyfree protocol for any number of players. However, the protocol suffers from high multipleexponential query complexity and it remains open to find simpler and more efficient envyfree protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envyfreeness: its existence is guaranteed by that of an envyfree allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graphs. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envyfree protocol given in [5].
无
0

3浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】Structured Decomposition for Reversible Boolean Functions
IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2019，39（10）：2410  242
2019年07月16日
Reversible Boolean function (RBF) is a onetoone function which maps nbit input to nbit output. Reversible logic synthesis has been widely studied due to its connection with lowenergy computation as well as quantum computation. In this paper, we give a structured decomposition for even RBFs. Specifically, for n ≥ 6, any even nbit RBF can be decomposed to 7 blocks of (n1)bit RBF, where 7 is a constant independent of n and the positions of these blocks have a large degree of freedom. Moreover, if the (n1)bit RBFs are required to be even as well, we show for n ≥ 10, even nbit RBF can be decomposed to 10 even (n  1)bit RBFs. In short, our decomposition has block depth 7 and even block depth 10. Our result improves Selinger's work in block depth model, by reducing the constant from 9 to 7 and from 13 to 10, when the blocks are limited to be even. We emphasize that our setting is a bit different from Selinger's work. In Selinger's constructive proof, each block is placed in one of two specific positions and thus the decomposition has an alternating structure. We relax this restriction and allow each block to act on arbitrary (n  1) bits. This relaxation keeps the block structure and provides more candidates when choosing the positions of blocks.
无
0

6浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】Local Equivalence of Multipartite Entanglement
IEEE Journal on Selected Areas in Communications，2020，38（3）： 568  574
2020年01月23日
Let R be an invariant polynomial ring of a reductive group acting on a vector space, and let d be the minimum integer such that R is generated by those polynomials in R of degree no more than d. To upper bound such d is a long standing open problem since the very initial study of the invariant theory in the 19th century. Motivated by its significant role in characterizing multipartite entanglement, we study the invariant polynomial rings of local unitary groups  the direct product of unitary groups acting on the tensor product of Hilbert spaces, and local general linear groups  the direct product of general linear groups acting on the tensor product of Hilbert spaces. For these two group actions, we prove explicit upper bounds on the degrees needed to generate the corresponding invariant polynomial rings. On the other hand, systematic methods are provided to construct all homogeneous polynomials that are invariant under these two groups for any fixed degree. Thus, our results can be regarded as a complete characterization of the invariant polynomial rings. As an interesting application, we show that multipartite entanglement is additive in the sense that two multipartite states are local unitary equivalent if and only if rcopies of them are local unitary equivalent for some r.
无
0

4浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】Speedup in Classical Simulation of Gaussian Boson Sampling
arXiv，2019，（）：
2019年08月27日
Gaussian boson sampling is a promising model for demonstrating quantum computational supremacy, which eases the experimental challenge of the standard bosonsampling proposal. Here by analyzing the computational costs of classical simulation of Gaussian boson sampling,we establish a lower bound for achieving quantum computational supremacy for a class of Gaussian bosonsampling problems, where squeezed states are injected into every input mode. Specifically, we propose a method for simplifying the bruteforce calculations for the transition probabilities in Gaussian boson sampling, leading to a significant reduction of the simulation costs. Particularly, our numerical results indicate that we can simulate 18 photons Gaussian boson sampling at the output subspace on a normal laptop, 20 photons on a commercial workstation with 256 cores, and suggest about 30 photons for supercomputers. These numbers are significantly smaller than those in standard boson sampling, suggesting Gaussian boson sampling may be more feasible for demonstrating quantum computational supremacy.
无
0

3浏览

0点赞

0收藏

0分享

0下载

0评论

引用
【期刊论文】Quantum Supremacy Circuit Simulation on Sunway TaihuLight
IEEE Transactions on Parallel and Distributed Systems，2019，31（4）：805  816
2019年10月15日
With the rapid progress made by industry and academia, quantum computers with dozens of qubits or even larger size are being realized. However, the fidelity of existing quantum computers often sharply decreases as the circuit depth increases. Thus, an ideal quantum circuit simulator on classical computers, especially on highperformance computers, is needed for benchmarking and validation. We design a largescale simulator of universal random quantum circuits, often called “quantum supremacy circuits”, and implement it on Sunway TaihuLight. The simulator can be used to accomplish the following two tasks: 1) Computing a complete output statevector; 2) Calculating one or a few amplitudes. We target the simulation of 49qubit circuits. For task 1), we successfully simulate such a circuit of depth 39, and for task 2) we reach the 55depth level. To the best of our knowledge, both of the simulation results reach the largest depth for 49qubit quantum supremacy circuits.
无
0

4浏览

0点赞

0收藏

0分享

0下载

0评论

引用