NO.198 New Directions in Provable Quantum Advantages

Shonan Village Center

December 11 - 15, 2023 (Check-in: December 10, 2023 )


  • François Le Gall
    • Nagoya University, Japan
  • Fang Song
    • Portland State University, USA
  • Penghui Yao
    • Nanjing University, China


Quantum computing is emerging as a new science and technology that promises to achieve a significant scientific breakthrough. Despite several wellknown quantum algorithms and protocols discovered in the past century, numerous exciting results have been found in the past decade, which have witnessed the advantages of quantum computation in various aspects.

The meeting is envisaged to concentrate on new settings and models where the capacity of quantum information processing provides provable advantages over classical means. The meeting will invite leading researchers whose contributions are likely to be essential to this field. We anticipate that the meeting will foster discussions in-depth and stimulate brainstorming between researchers working on different topics. The meeting will hopefully strengthen the collaborations among various research communities, especially between Asian and non-Asian researchers.

The meeting will focus on the following three topics.

1. Quantum distributed computing

Quantum computing in the distributed setting has recently been the subject of intensive investigations. In particular, in the past few years, Le Gall and Magniez (PODC 2018), Le Gall, Rosmanis and Nishimura (STACS 2019), and Izumi and Le Gall (PODC 2019) have shown the superiority of quantum distributed algorithms over classical distributed algorithms in several major settings. The objective of this seminar will be to both give an overview of this field and further investigate the computational power of quantum distributed algorithms. A first target will be finding more examples in which quantum distributed algorithms can outperform classical distributed algorithms and especially developing new ones. A second goal will be investigating the limitations of quantum distributed computing by clarifying the relations with the more developed area of two-party
quantum communication complexity. For this purpose, the seminar will invite participants with different backgrounds, in particular some experts of classical distributed algorithms interested in quantum computation and experts in quantum communication complexity interested in distributed computing.

2. Quantum games and quantum proof systems

Games and proof systems are fundamental models in computational complexity. Quantum computation and quantum information processing provide fascinating twists with these models. In quantum complexity theory, one may consider the quantum analogs of the classical models, where the players exchange quantum messages. It has received great attention to investigate the quantum analogs of classical proof systems, including QMA (quantum analog of NP), QIP (quantum analog of IP), QMIP (quantum analog of MIP), etc. While the models inherit some similarities to their classical counterparts, they can also possess unique quantum features and lead to very different pictures of quantum complexity theory. In the classical setting, multiprover interactive proof systems are as powerful as NEXP. By a recent breakthrough result MIP*=RE, if the provers are allowed to
access quantum resources, then the systems are undecidable. Numerous novel ideas have been introduced in this line of research, which haven’t been fully explored. For this sub-topic, the seminar will invite experts in this area to share the progress and understanding on quantum interactive proof systems.

3. Quantum cryptography

Quantum information processing is transforming the landscape of cryptography. A grave concern is the break of widely deployed cryptosystems due to exponential quantum speedup over best known classical algorithms for problems such as factorization. There has been extensive effort to construct new cryptosystems in the hope of resisting attacks enabled by quantum computing, usually referred to as post-quantum cryptography, which leads to the ongoing influential standardization project at the US National Institute of Standards and Technology (NIST). This line of work has been a central target of cryptanalysis, and it is both theoretically and practically critical to investigate the possibility of faster quantum algorithms for a host of hard problems. On the other hand, when honest users are also granted the capability of quantum information processing, quantum cryptography, i.e., cryptographic constructions employing quantum information, has shown superiority over classical cryptography, turning impossibility into possibility. Notable examples include unconditional quantum key distribution (QKD) and composable secure computation from a trusted setup. In recent years, there has been remarkable progress on copy protection, including quantum money and software release against pirates. Thanks to the no-cloning feature of quantum information, candidates have been constructed for these tasks, which are otherwise impossible to realize classically since classical information can be replicated freely. This sub-topic aims to advance new findings on both quantum algorithmic advantages on post-quantum cryptography and quantum cryptographic advantages in realizing copy protection and other primitives.