IJTCS 2021 | 分论坛日程：量子计算和算法与复杂性

编者按

第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。

本期带来“量子计算”和“算法与复杂性”分论坛精彩介绍。

“量子计算”介绍

量子计算是一门新兴的交叉学科，其利用量子状态的相干、纠缠等量子力学基本原理，展现出了超越经典计算的能力，在实现某些特定计算任务时甚至比现有经典算法有指数量级的加速。

本次会议聚焦近期国内科研工作者在量子领域的前沿研究成果，涉及从理论结果到实验实现的多个方面，为大家提供相关交流合作的平台，并希望以此吸引更多年轻人或其他领域的专家学者关注量子计算领域的发展，共同推动量子计算方向的交叉合作。

“量子计算”分论坛主席

 

Xiaoming Sun

Chinese Academy of Sciences

 

Jialin Zhang

Chinese Academy of Sciences

“量子计算”分论坛议程

时间：2021年8月17日

时间	讲者	报告题目
13:30- 13:55	孙麓岩	基于玻色模式的量子纠错与容错
14:00- 14:25	邓东灵	Quantum Artificial Intelligence —The Recent Advances
15:00- 15:25	袁骁	Perturbative quantum simulation
15:30- 15:55	李彤阳	Quantum Algorithms for Semidefinite Programs with Applications to Machine Learning

“量子计算”分论坛报告简介

 

基于玻色模式的量子纠错与容错

孙麓岩，清华大学

Abstract

由于量子系统不可避免地与非受控环境耦合，可容错量子计算不仅要求对存储量子信息的逻辑比特进行量子纠错保护，而且还需要对逻辑比特操控的动力学过程进行保护，从而得到可靠的量子逻辑门。近来，利用微波谐振腔中光子态进行玻色量子编码的研究方案引起了人们的广泛关注。该量子纠错方案利用了谐振子无限维希尔伯特空间进行信息冗余编码，同时只需监测一种错误症状，因此对硬件要求大大降低。在本报告中，我将展示我们在电路量子电动力学体系中实现了二项式玻色量子纠错码，对单个逻辑比特的完全控制，以及双逻辑比特之间的受控相位门操作。我还会报告我们最近实现的单个逻辑比特上的错误透明相位门：量子门操作过程中随机发生的错误可以在其完成之后通过自主量子纠错来纠正，而不会带来额外的退相干。我们的实验证明了错误透明的逻辑比特量子操作的可行性，为将来的容错量子计算提供了一种新思路。

Biography

孙麓岩，清华大学长聘副教授。2001年本科毕业于浙江大学物理系，2008年在美国马里兰大学（College Park）获得博士学位。之后，作为博士后来到耶鲁大学，开始基于超导电路的量子计算实验研究。2013年9月加入清华大学，组建超导量子计算实验室，继续从事超导量子计算的实验研究。研究兴趣主要包括量子反馈、量子纠错、量子控制和量子精密测量等。目前承担科技部国家重点研发计划课题和自然科学基金委项目，包括国家杰出青年科学基金项目。

 

Quantum Artificial Intelligence — The Recent Advances

Dongling Deng, Tsinghua University

Abstract

Quantum artificial intelligence (Quantum AI) is an emergent interdisciplinary field that explores the interplay between artificial intelligence and quantum physics. On the one hand, judiciously designed quantum algorithms may exhibit exponential advantages in solving certain AI problems; on the other hand, ideas and techniques from AI can also be exploited to tackle challenging problems in the quantum domain. In this talk, I will first make a brief introduction to this field and review some recent progresses. I will talk about several concrete examples to illustrate how AI and quantum physics can promote studies in both fields.

Biography

Dongling Deng is an assistant professor at the Institute for Interdisciplinary Information Sciences, Tsinghua University. He graduated from Nankai University with two Bachelor degrees, one in physics and the other in mathematics. He then studied at the Chern Institute of Mathematics and got a master degree in theoretical physics. After that, he moved to the University of Michigan and obtained his Ph.D. in physics, with thesis awarded "the Kent M. Terwilliger Memorial Thesis Prize". He did his postdoctoral work as a JQI (Joint Quantum Institute) postdoctoral fellow at the University of Maryland. Prof. Deng's current research interest mainly concerns quantum artificial intelligence.

 

Perturbative quantum simulation

Xiao Yuan, Peking University

Abstract

Approximations based on perturbation theory are the basis for most of the quantitative predictions of quantum mechanics, whether in quantum field theory, many-body physics, chemistry or other domains. Quantum computing provides an alternative to the perturbation paradigm, but the tens of noisy qubits currently available in state-of-the-art quantum processors are of limited practical utility. In this talk, we introduce perturbative quantum simulation, which combines the complementary strengths of the two approaches, enabling the solution of large practical quantum problems using noisy intermediate-scale quantum hardware. The use of a quantum processor eliminates the need to identify a solvable unperturbed Hamiltonian, while the introduction of perturbative coupling permits the quantum processor to simulate systems larger than the available number of physical qubits. After introducing the general perturbative simulation framework, we present an explicit example algorithm that mimics the Dyson series expansion. We then numerically benchmark the method for interacting bosons, fermions, and quantum spins in different topologies, and study different physical phenomena on systems of up to  qubits, such as information propagation, charge-spin separation and magnetism. In addition, we use 5 physical qubits on the IBMQ cloud to experimentally simulate the -qubit Ising model using our algorithm. The result verifies the noise robustness of our method and illustrates its potential for benchmarking large quantum processors with smaller ones.

Biography

Dr. Xiao Yuan received his Bachelor in theoretical physics from Peking University in 2012 and got his PhD in physics from Tsinghua University in 2016. Then he worked as a postdoc at University of Science and Technology China in 2017, at Oxford University from 2017 to 2019, and at Stanford University from 2019 to 2020. He is now an assistant professor at Center on Frontiers of Computing Studies, Peking University. Dr. Xiao Yuan's current research interests focus on near-term and universal quantum computing, and their applications.

 

Quantum Algorithms for Semidefinite Programs with Applications to Machine Learning

Tongyang Li, Peking University

Abstract

Semidefinite programming has been a central topic in the study of mathematical optimization, theoretical computer science, and operations research in the last decades. In this talk, we introduce a quantum algorithms for solving SDPs with polynomial speedup compared to the best known classical algorithms. We also introduce how the quantum algorithm can be applied to training linear and kernel-based classifiers, as well as solving general matrix games. The talk is based on three papers: https://arxiv.org/abs/1710.02581, https://arxiv.org/abs/1904.02276, and https://arxiv.org/abs/2012.06519.

Biography

Tongyang Li is currently an assistant professor at Center on Frontiers of Computing Studies, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathematical Sciences, Tsinghua University, both in 2015. Tongyang was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship.

“算法与复杂性”介绍

算法与复杂性是理论计算机领域的基石，主要分为两个主要研究领域，其一是复杂性研究，针对的是研究各个复杂度类之间的关系，其终极目标是证明P是否等于NP。另一个是针对各种计算模型的算法设计及针对算法复杂性的分析，包括自动机理论，近似算法，在线算法，随机算法，图算法，流算法，分布式算法等等。在实际应用中产生的大多数问题都可以通过建模转变为一个理论问题进行算法和复杂性的研究，而得到的有理论保障的结果对实际问题有很大的指导意义。

在国内该领域的发展正在加速，越来越多的学者在该领域从事前沿的工作，并且时有突破性的结果出现。FAW（Frontiers of Algorithmics Workshop）为立足国内的专注于算法与复杂性的国际会议。本次会议旨在初步建立算法与复杂性分论坛与FAW的联系，共同促进算法领域的交流合作。

“算法与复杂性”分论坛主席

 

Minming Li 

City University of Hong Kong

 

Guochuan Zhang

Zhejiang University

“算法与复杂性”分论坛议程

时间：2021年8月18日

时间	讲者	报告题目
19:00- 19:55	尹一通	Fast sampling constraint  satisfaction solutions via  the Lovász local lemma
20:00- 20:55	栗师	Tight Online Algorithms for Unrelated Machine  Load Balancing with  Predictions
21:00- 21:25	会议接收论文
21:30- 21:55	会议接收论文
22:00- 22:25	会议接收论文
22:30- 23:00	会议接收论文

“算法与复杂性”分论坛报告简介

 

Fast sampling constraint satisfaction solutions via the Lovász local lemma

Yitong Yin, Nanjing University

Abstract

This talk will cover some recent advances in sampling solutions of constraint satisfaction problems (CSPs) through the Lovász local lemma. We will talk about Markov chain based algorithms for sampling almost uniform CSP solutions, inspired by an LP based approach for approximately counting the number of CSP solutions due to Ankur Moitra. Assuming "local lemma"-like conditions, these Markov chain based sampling algorithms are accurate and can run in a nearly linear time in the number of variables for a broad class of CSPs.

Biography

Yitong Yin is a Professor in Computer Science in the Department of Computer Science and Technology at Nanjing University. He received his PhD in Computer Science from Yale University in 2009, and has been in the faculty of Nanjing University since then. His research interest is theoretical computing science, with focuses on randomized algorithms and data structure complexity.

 

Tight Online Algorithms for Unrelated Machine Load Balancing with Predictions

Shi Li, University at Buffalo

Abstract

The success of modern machine learning techniques has led to a surge of interest in using machine learned predictions to design better online algorithms for combinatorial optimization problems. This is called learning augmented online algorithms. One seeks to design a prediction about the online instance and an online algorithm which is given the prediction upfront. They should satisfy: a) usefulness, which means the prediction allows the online algorithm to achieve a better competitive ratio, b) robustness, which means the performance of the algorithm deteriorates smoothly as the noise of prediction increases, and c) learnability, which means the predicted information can be learned efficiently from past instances.

In this talk, I will present our results for the online load balancing problem in this model.  That is, we allow some prediction about the instance to be given to the online algorithm. First, we design deterministic and randomized online rounding algorithms for the problem in the unrelated machine setting, with O(\log m/\log \log m)- and O(\log \log m / \log \log \log m)-competitive ratios. They respectively improve upon the previous ratios of O(\log m) and O(\log^3\log m) of Lattanzi et al., and match their lower bounds. Second, we extend their prediction scheme from the restricted assignment setting to the unrelated machine setting. Finally, we consider the learning model introduced by Lavastida et al., and show that under the model, the prediction can be learned efficiently with a few samples of instances.

The talk is based on my joint work with Jiayi Xian. 

Biography

Shi Li is an associate professor at the department of computer science and engineering at University at Buffalo. Before joining University at Buffalo in 2015, he was a research assistant professor at Toyota Technological Institute at Chicago. He received his Ph.D. in 2013 from the Department of Computer Science at Princeton University.  He received his Bachelor's degree in 2008 from the Department of Computer Science and Technology at Tsinghua University, where he was also a student of Andrew Chih-Chi Yao's special pilot class.  Professor Li's main research is the design of efficient algorithms for scheduling, clustering, facility location and network design problems under different models. 

关于IJTCS

回顾 → 对话邓小铁：在首届IJTCS中，我看到了中国计算理论的成长

日程 → 分论坛：区块链技术

日程 → 分论坛：多智能体强化学习

IJTCS注册信息

大会现已正式面向公众开放注册！

观看线上报告：免费

通过在线观看直播的方式参与大会，可通过直播平台提问。

线上会议注册：

（普通）$100 /￥700

（学生）$50 /￥350*

获得所有Zoom会议参会链接，作为参会人在线参加全部会议，直接在线提问讨论并参与特设互动环节。

线下会议注册：

（普通）$200 / ￥1400

（学生）$100 / ￥700*

作为参会人在线下（北京大学）参加会议，与知名学者们面对面交流；同时享受线上注册的所有权益。

*因防疫要求，仅开放10个校外线下参会名额。

点击 ↓↓↓二维码↓↓↓ 跳转注册页面

*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至[e-mail]，邮件主题格式为＂Student Registration+姓名+线上/线下"。

大会主席 

 

John Hopcroft

图灵奖获得者

中国科学院外籍院士

北京大学访问讲席教授

大会联合主席 

 

邓小铁

北京大学讲席教授

欧洲科学院外籍院士

ACM/IEEE Fellow

顾问委员会主席 

高  文

中国工程院院士

北京大学教授

梅  宏

中国科学院院士

CCF理事长

张平文

中国科学院院士

CSIAM理事长

北京大学教授

程序委员会主席 

孙晓明

中科院计算所

研究员

邓小铁

北京大学

讲席教授

李闽溟

香港城市大学

副教授

陆品燕

上海财经大学

教授

李  建

清华大学

副教授

组织单位 

合作媒体

大会赞助

联系人

大会赞助、合作等事宜

请联系

[e-mail]

010-62761029

大会网站

https://econcs.pku.edu.cn/ijtcs2021/index.htm

↑↑扫码直达大会官网↑↑

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转大会注册页面