计算理论之美 (Summer 2021): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>TCSseminar
imported>TCSseminar
 
(83 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Infobox
{{Infobox  
|name        = Infobox
|name        = Infobox
|bodystyle    =  
|headerstyle  = background:#4D72BE;
|title        = <font size=3>计算理论之美</font>
|labelstyle   = background:#DAE1F0;
|titlestyle   =  


|image        =  
|header1 = <font size=3, color=white>计算理论之美</font>
|imagestyle  =  
|label2 = {{Nowrap|负责人}}
|caption      =  
|data2  = 姚鹏晖 ([mailto:pyao@nju.edu.cn pyao@nju.edu.cn])
|captionstyle =
|label4 = 时间
|headerstyle = background:#ccf;
|data4 = 2021.7.8 2021.7.11
|labelstyle  = background:#ddf;
|label5 = 地点
|datastyle    =
|data5 = {{Nowrap|南京大学仙林校区计算机系楼111报告厅}}
 
|label6 = 助教
|header1 =负责人
|data6 = {{Nowrap|钦明珑 ([mailto:mf1833054@smail.nju.edu.cn mf1833054@smail.nju.edu.cn])}}
|label1  =
|belowstyle = background:#DAE1F0;
|data1  =
|header2 =
|label2  =
|data2  = 姚鹏晖
|header3 =
|label3  = Email
|data3  = pyao@nju.edu.cn
|header4 = 日期
|label5 =
|data5  = 2021.7.8-2021.7.11
|header6 = 地点
|header7 =
|label7 =  
|data7  = 南京大学仙林校区计算机系楼111报告厅
|header8 =
|label9  =
|data9  =
|header10 =
|label10  =
|data10  =
|header11 =
|label11  =  
|data11  =  
|header12 = 助教
|data13= 钦明珑
|label14= Email
|data14=  mf1833054@smail.nju.edu.cn
|belowstyle = background:#ddf;
|below =  
|below =  
}}
}}
由中国计算机学会(CCF)支持的首届“计算理论之美”暑期讲习班将由南京大学承办,于2021年7月8日至7月11日在江苏省南京市南京大学仙林校区开班。本次讲习班将选取理论计算机领域备受关注的四个话题,面向高年级本科生与研究生,安排四天的高级课程。内容深入浅出,由国内一线的优秀青年学者讲授,使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法,为有志于从事理论计算机科学研究的学者打下一定的基础,也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。


= 课程安排 =
= 课程安排 =
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"  
:{|border="2" width="70%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"  
|-
 
|bgcolor="#A7C1F2" align="center" colspan="3" |'''10月19日'''
|-
|-
|style="width: 140px;" align="center"|9:00 '''am''' -- 9:50 '''am'''
|bgcolor="#4D72BE" align="center" style="width: 21%"|<font size=3, color=white>'''时间'''</font>
|style="width: 180px;" align="center"|[https://physics.nju.edu.cn//ry/gk/hwgccqnrc/20190904/i18322.html 马小松] <br>
|bgcolor="#4D72BE" align="center" |<font size=3, color=white>'''讲题'''</font>
南京大学
|bgcolor="#4D72BE" align="center" style="width: 20%"|<font size=3, color=white>'''发言人'''</font>
|
:<font size=3>'''Title''': Harnessing Single Photons in Quantum Technology</font>
:'''Abstract''':Quantum technology employs the ‘spooky’ phenomena of quantum physics such as superposition, randomness and entanglement to process information in a novel way. Quantum photonics provides a promising path for both delivering quantum-enhanced technologies and exploring fundamental physics. In this talk, I will introduce our recent work on quantum delayed-choice experiment based on multiphoton entangled states, which shows that a photon can not only be a particle or wave, but the superposition of them, even under Einstein’s locality condition. In the second part of my talk, I will present our recent endeavors in developing functional nodes for quantum information processing based on integrated optics architecture and their potential applications in a metropolitan fiber network.


|-
|-
|style="background: silver;" align="center" colspan="3" |'''茶歇'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月8日'''
|-
|-
|align="center"|10:15 '''am''' -- 11:05 '''am'''
|align="center"|8:20 — 8:30
|align="center"|[http://ioe.sxu.edu.cn/kyry/b1514d870eb64cf6b925e9facee08f26.htm 苏晓龙] <br>
 
山西大学
|align="center"|开幕致辞
|
|
:<font size=3>'''Title''': 基于光场量子态的量子计算和量子纠错</font>
:'''Abstract''':基于光学模的连续变量量子信息处理,以光场量子态为量子资源,结合各种量子操控手段,完成信息的传输和处理,是量子信息处理的一种有效途径。量子逻辑门序列是进行量子计算的基础。我们以连续变量六组份cluster纠缠态光场为资源,实验实现了一个包含单模压缩门和可控位相门的量子逻辑门序列。实验结果表明,输出态之间存在量子纠缠,且量子纠缠依赖于两个逻辑门。这证实了量子逻辑门序列的特性。输出态的保真度高于未使用cluster纠缠态作为辅助态时的保真度。这个实验展现了通过逻辑门序列实现高斯量子计算的可行性。
:量子纠错是量子计算和量子通信中比不可少的一个重要环节。我们实验实现了一个针对单个随机误差的五波包编码的连续变量量子纠错方案。连续变量五组份纠缠的五个子模被用作五个编码信道。特别是,在我们的编码方案中,输入态被编码到五个编码信道中的其中三个信道中,而其余两个信道不包含输入态的信息。因此,输出的量子态免疫于不包含输入态的量子信道中的误差。如果误差发生在这两个信道中,我们不需要执行纠错操作,而且此时输出态的保真度接近1。我们实验演示了输入态为真空态和单模压缩态时量子纠错方案的执行情况,实验得到的保真度均高于相应的经典极限。近期,我们提出了基于连续变量八组份cluster态实现拓扑纠错的方案。研究表明,我们可以实现拓扑量子关联对任意一个光学模式的相空间平移误差的拓扑保护。


|-
|-
|align="center"|11:10 '''am''' -- 12:00 '''pm'''
|align="center"|8:30 — 11:30
|align="center"|[http://ooe.ustc.edu.cn/hr15.html 许金时] <br>
|align="center"|参数算法
中国科学与技术大学
|align="center"|{{Nowrap|[https://basics.sjtu.edu.cn/~chen/ 陈翌佳](上海交通大学)}}<br>[https://sites.google.com/site/bingkai314159/ 林冰凯](南京大学)
|
:<font size=3>'''Title''': 面向高维多模式的光量子模拟</font>
:'''Abstract''':量子模拟是用一个可控的量子系统来模拟另一个量子系统的性质和演化。线性光学系统能够有效地屏蔽环境对系统的影响,并且能够方便地实现高维多模式的编码和操作,是量子模拟一个很重要的方向。在这个报告中我将首先介绍利用对光子多空间模式的编码和操作,模拟马约拉纳零模交换性质及探测非阿贝尔拓扑Berry相位的实验工作。另一方面光子轨道角动量数目原理上可以无限,是量子模拟很好的信息载体。轨道角动量简并腔可以同时容纳很多轨道角动量,因此提供了一个同时操控多维度的量子平台。我将介绍利这一方向的实验进展,包括实现了超过46阶轨道角动量简并光学腔的搭建以及新型轨道角动量简并腔的设计等。


|-
|-
|style="background: silver;" align="center" colspan="3" |'''午餐'''
| align="center" colspan="3" |午休
|-
|-
|align="center"|2:00 '''pm''' -- 2:50 '''pm'''
|align="center"|[https://person.zju.edu.cn/0017098 王大伟] <br>
浙江大学
|
:<font size=3>'''Title''':Synthesis of Anti-symmetric Spin Exchange Interaction in Superconducting Circuits </font>
:'''Abstract''':According to quantum mechanics, chiral states cannot be non-degenerate eingenstates of a parity-conserving Hamiltonian. This is in contradiction to the existence of chiral molecules—a fact known as as the Hund paradox. The origin of molecular and biological chirality is conjectured to be related to parity-breaking interactions or environmental decoherence, but a quantum superposition of two chiral molecular states with distinctive optical activities has never been observed. To make progress in addressing these questions, it would be helpful to construct an artificial quantum system that breaks the parity symmetry and that can be prepared in a superposition of two chiral states. Here we report the synthesis of the parity-breaking antisymmetric spin exchange interaction in all-to-all connected superconducting circuits, which allows us to show various chiral spin dynamics in up to five-spin clusters. We also demonstrate the entanglement of up to five qubits in Greenberger–Horne–Zeilinger states based on a three-spin chiral logic gate. Our results are a step towards quantum simulation of magnetism with antisymmetric spin exhange interaction and quantum computation with chiral spin states.


|-
|-
|align="center"|2:55 '''pm''' -- 3:45 '''pm'''
|align="center"|14:00 — 16:00
|align="center"|[http://quantum.ustc.edu.cn/web/index.php/node/638 戴汉宁] <br>
|align="center"|参数算法
中国科学与技术大学
|align="center"|[https://sites.google.com/site/bingkai314159/ 林冰凯](南京大学)
|
:<font size=3>'''Title''': Mass Production of Entanglement in a Defect-free Ultracold Atom Lattice </font>
:'''Abstract''':Scalable, coherent many-body systems are of fundamental interest, which could ultimately enable a quantum machine outperforming conventional computers. A paradigmatic quantum simulator is composed of neutral atoms in optical lattice with great potential for quantum technologies. However,  previous experiments achieved neither sufficient number of qubits nor qualified two-qubit gates for future applications. Here we report the creation of a defect-free quantum simulator with ten-thousand atoms and mass production of high-fidelity entangled pairs. In a two-dimensional (2D) plane, we cool the Mott-insulator samples by immersing them into removable superfluid reservoirs and a record-low entropy per particle of 0.0019 $k_B $ is achieved ($k_B$ is the Boltzmann constant). The atoms are then rearranged into a 2D lattice free of defects. Afterwards, we realize parallel two-qubit gates for entangling 1250 atom pairs with a fidelity of 0.993(1). This experiment opens an avenue for large-scale quantum simulation and computation.


|-
|-
|style="background: silver;" align="center" colspan="3" |'''茶歇'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月9日'''
 
|-
|-
|align="center"|4:10 '''pm''' -- 5:00 '''pm'''
|align="center"|8:30 — 11:30
|align="center"|Lovász Local Lemma
|align="center"|[http://tcs.nju.edu.cn/yinyt/ 尹一通](南京大学)


|align="center"|[https://www.sustech.edu.cn/zh/ludawei.html 鲁大为]  <br>
|-
南方科技大学
| align="center" colspan="3" |午休
|
|-
:<font size=3>'''Title''': Experimental Implementation of Efficient Quantum Pseudorandomness on a 12-spin System</font>


:'''Abstract''':Quantum pseudorandomness, also known as unitary designs, comprises a powerful resource for emergent quantum technologies. Although in theory pseudorandom unitary operators can be constructed efficiently, realizing these objects in realistic physical systems is a challenging task. Here, we demonstrate experimental generation and detection of quantum pseudorandomness on a 12-qubit nuclear magnetic resonance system. We first apply random sequences to the interacting nuclear spins, leading to random quantum evolutions that can quickly form unitary designs. Then, in order to probe the growth of quantum pseudorandomness during the time-evolutions, we propose the idea of using the system’s multiple-quantum coherence distribution as an indicator. Based on this indicator, we measure the spreading of quantum coherences and find that substantial quantum pseudorandomness has been achieved at the 12-qubit scale. This may open up a path to experimentally explore quantum randomness on forthcoming large-scale quantum processors.
|-
|align="center"|14:00 — 16:00
|align="center"|Lovász Local Lemma
|align="center"|[https://theory.ict.ac.cn/en/members/hekun/ 何昆](中科院计算所)


:
|-
|}
|align="center"|16:15 — 17:00
|align="center"|学术报告:Perfect Sampling for (atomic) Lovász Local Lemma
|align="center"|[https://shlw.github.io/ 吴克文](UC Berkeley)


:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
|-
|bgcolor="#A7C1F2" align="center" colspan="3" |'''10月20日'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月10日'''
 
|-
|-
|style="width: 140px;" align="center"|9:00 '''am''' -- 9:50 '''am'''
|align="center"|8:30 — 11:30
|style="width: 180px;" align="center"|
|align="center"|量子信息论与容错量子计算简介
[http://sdcs.sysu.edu.cn/content/2541 李绿周] <br>
|align="center"|[http://penghuiyao.info 姚鹏晖](南京大学)
中山大学
|
:<font size=3>'''Title''': 量子生成对抗网络</font>
:'''Abstract''':量子机器学习近年来得到了较大关注。我们考虑如何基于量子计算技术提升生成对抗网络(GAN)的性能。具体来说,我们提出一个量子生成对抗网络模型(QGAN),该模型是一种经典-量子混合架构,其中以参数量子电路作为生成器,以经典神经网络作为区分器。所提出的QGAN具有以下特征或潜在优势:1.具有内在的生成离散数据的能力,而经典GAN由于梯度消失问题并不擅长生成离散数据。2.避免了目前大多数量子机器学习算法所面临的输入/输出瓶颈问题(即要么需要花费大量时间把经典数据编码为量子态,要么输出的只是问题解的量子态编码而不是经典可读取的形式)。3.可以把蕴含在训练集中的概率分布显示地学习出来,进而可以作进一步的应用。


|-
|-
|style="background: silver;" align="center" colspan="3" |'''茶歇'''
| align="center" colspan="3" |午休
|-
|-
|align="center"|10:15 '''am''' -- 11:05 '''am'''
 
|align="center"|[http://homepage.hit.edu.cn/keli 李科] <br>
哈尔滨工业大学
|
:<font size=3>'''Title''': Quantum de Finetti Theorem under One-way Adaptive Measurements</font>
:'''Abstract''':I will talk about a version of the quantum de Finetti theorem: permutation-invariant quantum states are well approximated as a probabilistic mixture of multi-fold product states. The approximation is measured by distinguishability under one-way adaptive measurements. I will also talk about its applications: (i) a quasipolynomial-time algorithm which detects multipartite entanglement with amount larger than an arbitrarily small constant (measured with a variant of the relative entropy of entanglement), and (ii) a proof that in quantum Merlin-Arthur proof systems, polynomially many provers are not more powerful than a single prover when the verifier is restricted to one-way adaptive measurements.


|-
|-
|align="center"|11:10 '''am''' -- 12:00 '''pm'''
|align="center"|14:00 — 16:00
|align="center"|[http://iiis.tsinghua.edu.cn/zh/weizh/ 魏朝晖] <br>
|align="center"|量子信息论与容错量子计算简介
清华大学
|align="center"|[https://iiis.tsinghua.edu.cn/zh/weizh/ 魏朝晖](清华大学)
|
:<font size=3>'''Title''': The Experimental Detection and Quantification of Entanglement</font>
:'''Abstract''':We define a property called nondegeneracy for Bell inequalities, which describes the situation that in a Bell setting, if a Bell inequality and involved local measurements are chosen and fixed, any quantum state with a given dimension and its orthogonal quantum state cannot violate the inequality remarkably at the same time. We prove that for an arbitrary quantum dimension, based on the measurement statistics only, we can give an analytic lower bound for the entanglement of formation of the unknown bipartite quantum state by choosing a proper nondegenerate Bell inequality, making the whole process semi-device-independent. We provide specific examples to demonstrate the existence of nondegeneracy and applications of our approach.


|-
|-
|style="background: silver;" align="center" colspan="3" |'''午餐'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月11日'''
 
|-
|-
|align="center"|2:00 '''pm''' -- 2:50 '''pm'''
|align="center"|8:30 — 11:30
|align="center"|[http://gscaep.ac.cn/index.php/divisions/view?id=6 李颖] <br>
|align="center"|Consensus: Reaching Agreement in Faulty Environment
中国工程物理研究院
|align="center"|[https://chaodong.me 郑朝栋](南京大学)
|
:<font size=3>'''Title''':Error-resilient Quantum Computation on Near-future Quantum Computers </font>
:'''Abstract''':Computation is meaningful only if it produces correct outcomes. On a scalable quantum computer with millions of qubits, by protecting the quantum information using error correction codes, we can realise quantum computation with reliable outcomes. In this talk, I will present two alternative approaches that can reduce computation errors without encoding; therefore, they are practical for near-future quantum computers with a limited number of qubits.


|-
|-
|align="center"|2:55 '''pm''' -- 3:45 '''pm'''
|align="center" colspan="3" |午休
|align="center"|[https://phy.sustc.edu.cn/index.php?s=/Show/index/cid/45/id/93.html 翁文康]  <br>
|-
南方科技大学
华为量子计算软件与算法首席科学家
|
:<font size=3>'''Title''': 专用量子计算机的应用算法 </font>
 
:'''Abstract''':在不久的将来,我们可以预期学术界和工业界在量子计算机的研发上有持续的突破。比如对于 50 个量子比特以上的量子芯片,能够达到非常高精度的调控技术。很有可能对于一些特定的计算任务,这些量子芯片能够执行到一个程度,是经典计算机无法有效模拟的。可是,这些芯片的量子比特个数还是远远不足以实现教科书里面的量子算法。当前的一个重大的问题就是,如何开发针对近期量子芯片的应用,去解决一些实际的科学或者工程问题?此外,对于一般用户,我们预期这些算力强大的专用量子机能够通过互联网,作为一种云服务去访问。这种形式的量子计算云服务也引发出不少学术问题,比如说,如何验证互联网背后的服务器是否带有真正的量子计算机而不是一个经典模拟器?
 
:在这次报告中,我将汇报最近的几个相关的科研成果和分享我对这些问题的看法。


|-
|-
|style="background: silver;" align="center" colspan="3" |'''茶歇'''
|align="center"|14:00 — 16:00
|align="center"|Consensus: Reaching Agreement in Faulty Environment
|align="center"|[https://disco.ethz.ch/members/yuwang 王彧弋](ETH)


|-
|-
|align="center"|4:10 '''pm''' -- 5:00 '''pm'''
|align="center"|16:00 — 16:10
 
|align="center"|闭幕
|align="center" colspan="2"|Panel Discussion
|
:
|}
|}


= 公告 =
= 公告 =
= 课件 =
参见南大云盘 [https://box.nju.edu.cn/d/d9d37df3e9ba4ec3a194/]


= 作业 =
= 作业 =
参见南大云盘 [https://box.nju.edu.cn/d/94fe0624c4684adfbd6d/]
7月12日23:59之前交至 ccf_tcs@163.com(邮件标题写上姓名)

Latest revision as of 08:01, 8 July 2021

计算理论之美
负责人 姚鹏晖 (pyao@nju.edu.cn)
时间 2021.7.8 — 2021.7.11
地点 南京大学仙林校区计算机系楼111报告厅
助教 钦明珑 (mf1833054@smail.nju.edu.cn)
v · d · e

由中国计算机学会(CCF)支持的首届“计算理论之美”暑期讲习班将由南京大学承办,于2021年7月8日至7月11日在江苏省南京市南京大学仙林校区开班。本次讲习班将选取理论计算机领域备受关注的四个话题,面向高年级本科生与研究生,安排四天的高级课程。内容深入浅出,由国内一线的优秀青年学者讲授,使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法,为有志于从事理论计算机科学研究的学者打下一定的基础,也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。

课程安排

时间 讲题 发言人
7月8日
8:20 — 8:30 开幕致辞
8:30 — 11:30 参数算法 陈翌佳(上海交通大学)
林冰凯(南京大学)
午休
14:00 — 16:00 参数算法 林冰凯(南京大学)
7月9日
8:30 — 11:30 Lovász Local Lemma 尹一通(南京大学)
午休
14:00 — 16:00 Lovász Local Lemma 何昆(中科院计算所)
16:15 — 17:00 学术报告:Perfect Sampling for (atomic) Lovász Local Lemma 吴克文(UC Berkeley)
7月10日
8:30 — 11:30 量子信息论与容错量子计算简介 姚鹏晖(南京大学)
午休
14:00 — 16:00 量子信息论与容错量子计算简介 魏朝晖(清华大学)
7月11日
8:30 — 11:30 Consensus: Reaching Agreement in Faulty Environment 郑朝栋(南京大学)
午休
14:00 — 16:00 Consensus: Reaching Agreement in Faulty Environment 王彧弋(ETH)
16:00 — 16:10 闭幕

公告

课件

参见南大云盘 [1]

作业

参见南大云盘 [2]

7月12日23:59之前交至 ccf_tcs@163.com(邮件标题写上姓名)