IJTCS | 分论坛日程：量子计算

编者按

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

本次大会的主题为“理论计算机科学领域的最新进展与焦点问题”。大会共设7个分论坛，分别对算法博弈论、区块链技术、多智能体强化学习、机器学习理论、量子计算、机器学习与形式化方法和算法与复杂性等领域进行深入探讨。同时，大会特别开设了青年博士论坛、女性学者论坛与本科生科研论坛，荟集海内外知名专家学者，聚焦理论计算机前沿问题。有关信息将持续更新，敬请关注！

本期带来“量子计算”分论坛精彩介绍。

“量子计算”介绍

量子计算是一门新兴的交叉学科，利用量子状态的相干、纠缠等量子力学基本原理，量子计算展现出了超越经典计算的能力，在实现某些特定计算任务时甚至比现有经典算法有指数量级的加速。本次会议聚焦近期国内外华人科研工作者在量子领域的前沿研究成果，为大家提供相关交流合作的平台，并希望以此吸引更多年轻人或其他领域的专家学者关注量子计算领域的发展，共同推动量子计算方向的交叉合作。

“量子计算”分论坛主席

孙晓明

中国科学院计算技术研究所

张家琳

中国科学院计算技术研究所

“量子计算”分论坛议程

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

李彤阳

Quantum Algorithms for Convex and Nonconvex Optimization

Abstract

The theories of optimization answer foundational questions in machine learning and lead to new algorithms for practical applications. In this talk, I will introduce two quantum algorithms that we recently developed for convex optimization (arXiv:1809.01731) and nonconvex optimization (arXiv:2007.10253), respectively. Both achieve polynomial quantum speedup compared to the best-known classical algorithms.

季铮锋

Spooky Complexity at a Distance

Abstract

In this talk, I will discuss the recent result on the characterization of the power of quantum multi-prover interactive proof systems, MIP*=RE (arXiv:2001.04383). After a brief setup of the problem, we will highlight its rich connections and implications to problems in computer science, quantum physics, and mathematics, including the Tsirelson's problem and Connes' embedding problem. In the second half of the talk, we will outline the overall proof strategy and introduce several key techniques employed in the proof.

姚鹏晖

Nonlocal Games With Noisy Maximally Entangled States are Decidable

Abstract

In this talk, we consider a special class of nonlocal games, where the players share infinitely many copies of a given state.  We prove an upper bound on the copies of the given states for the players to approximate the values of the games to an arbitrarily small precision if the shared states are noisy maximally entangled states. Combining with the recent breakthrough work MIP*=RE by Ji, Natarajan, Vidick, Wright and Yuen, our result implies that nonlocal games are not robust against the noise from the preshared states. Our work develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality for random operators. These novel tools are interesting on their own right and may have other applications in quantum information theory and quantum complexity theory.

宋  方

Unpredictable Functions and Quantum-secure Authentication

Abstract

A black-box random function f is intuitively difficult to predict. Namely, after making a number of queries to f, it remains hard to compute the function value at an "unqueried" input with probability significantly better than random guessing. However, if we grant the algorithm quantum superposition queries to the function, it becomes unclear how to characterize "unqueried" inputs and hence how to formalize unpredictable functions in the quantum setting. 

In this talk, I will review some prior efforts, and introduce a new notion termed "blind-unforgeable" which offers a more accurate definition for quantum unpredictability. I will then give various constructions realizing the new notion, and show applications in designing quantum-secure message authentication and digital signatures.

马雄峰

Utility Optimization in a Quantum Key Distribution Network

Abstract

Recently, a few field tests of quantum key distribution networks throughout the world have been presented throughout the world. By proposing a framework of a quantum network, we design a communication scheme with the highest security level that trusts a minimum number of intermediate nodes. Moreover, when the quantum key is a limited resource, we design key management and data scheduling schemes to optimize the utility of the data transmission. Our results can be directly applied to the current metropolitan and free-space quantum network implementations.

袁  骁

Error Mitigated Quantum Simulation with Near-term Quantum Hardware

Abstract

Variational algorithms may enable classically intractable simulations on near-term quantum computers. However, their potential is limited by hardware errors. It is therefore crucial to develop efficient ways to mitigate these errors. In this talk, we introduce the recently proposed variational algorithms for solving static and dynamic many-body physics problems as well as the error mitigation methods for suppressing errors during the simulation. We show how to suppress both device errors due to implementation imperfection and algorithmic errors due to algorithm approximation. Theses error mitigation methods can be implemented on current quantum hardware.

关于IJTCS

简介 → 国际理论计算机联合大会重磅登场

推荐 → 大会特邀报告（一）

推荐 → 大会特邀报告（二）

日程 → 分论坛：算法博弈论

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

日程 → 分论坛：机器学习理论

IJTCS注册信息

本次大会已经正式面向公众开放注册！每位参与者可以选择免费注册以观看线上报告，或是支付一定费用以进一步和讲者就报告内容进行交流，深度参与大会的更多环节。

• 观看线上报告：免费

• 完全注册：
  

• （普通）$100 /￥700
  （学生）$50 /￥350*
  作为参会人参加全部会议，直接在线提问讨论并参与特设互动环节

注册截止：2020年8月15日23:59

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

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

大会主席

John Hopcroft

中国科学院外籍院士、北京大学访问讲席教授

林惠民

中国科学院院士、中国科学院软件研究所专家

大会联合主席

邓小铁

北京大学教授

顾问委员会主席

高  文

中国工程院院士、北京大学教授

梅  宏

中国科学院院士、CCF理事长

张平文

中国科学院院士、CSIAM理事长、北京大学教授

组织单位

欢迎注册

大会网站：

https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html

注册链接：

https://econcs.pku.edu.cn/ijtcs2020/Registration.htm

联系人

大会赞助、合作等信息，请联系：[e-mail]

—   版权声明  —

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

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