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

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
imported>TCSseminar
imported>TCSseminar
 
(63 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="74%" 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="#99CCFF" style="width: 240px;" align="center"|时间
|bgcolor="#4D72BE" align="center" style="width: 21%"|<font size=3, color=white>'''时间'''</font>
 
|bgcolor="#4D72BE" align="center" |<font size=3, color=white>'''讲题'''</font>
|bgcolor="#99CCFF" style="width: 430px;" align="center"|讲题
|bgcolor="#4D72BE" align="center" style="width: 20%"|<font size=3, color=white>'''发言人'''</font>
|bgcolor="#99CCFF" align="center"|发言人


|-
|-
|bgcolor="#A7C1F2" align="center" colspan="3" |'''7月8日'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月8日'''
|-
|-
|align="center"|8:20 '''am''' -- 8:30 '''am'''
|align="center"|8:20 — 8:30  


|align="center"|<font size=4>'''开幕致辞'''</font>
|align="center"|开幕致辞
|
|


|-
|-
|style="background: silver;" align="center" colspan="3" |'''茶歇'''
|align="center"|8:30 — 11:30
|align="center"|参数算法
|align="center"|{{Nowrap|[https://basics.sjtu.edu.cn/~chen/ 陈翌佳]（上海交通大学）}}<br>[https://sites.google.com/site/bingkai314159/ 林冰凯]（南京大学）
 
|-
| align="center" colspan="3" |午休
|-
|-
|align="center"|10:15 '''am''' -- 11:05 '''am'''
|align="center"|[http://ioe.sxu.edu.cn/kyry/b1514d870eb64cf6b925e9facee08f26.htm 苏晓龙] <br>
山西大学
|
:<font size=3>


|-
|-
|style="background: silver;" align="center" colspan="3" |'''午餐'''
|align="center"|14:00 — 16:00
|align="center"|参数算法
|align="center"|[https://sites.google.com/site/bingkai314159/ 林冰凯]（南京大学）
 
|-
|-
|align="center"|2:00 '''pm''' -- 2:50 '''pm'''
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月9日'''
|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"|8:30 — 11:30
|align="center"|[http://quantum.ustc.edu.cn/web/index.php/node/638 戴汉宁] <br>
|align="center"|Lovász Local Lemma
中国科学与技术大学
|align="center"|[http://tcs.nju.edu.cn/yinyt/ 尹一通]（南京大学）
|
:<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" |'''茶歇'''
| align="center" colspan="3" |午休
|-
|-
|align="center"|4:10 '''pm''' -- 5:00 '''pm'''


|align="center"|[https://www.sustech.edu.cn/zh/ludawei.html 鲁大为] <br>
|-
南方科技大学
|align="center"|14:00 — 16:00
|
|align="center"|Lovász Local Lemma
:<font size=3>'''Title''': Experimental Implementation of Efficient Quantum Pseudorandomness on a 12-spin System</font>
|align="center"|[https://theory.ict.ac.cn/en/members/hekun/ 何昆]（中科院计算所）


:'''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"|16:15 — 17:00
|align="center"|学术报告：Perfect Sampling for (atomic) Lovász Local Lemma
|align="center"|[https://shlw.github.io/ 吴克文]（UC Berkeley）


:
|-
|}
|bgcolor="#DAE1F0" align="center" colspan="3" |'''7月10日'''


:{|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日'''
|-
|-
|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（邮件标题写上姓名）

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=计算理论之美_(Summer_2021)&oldid=9492"