通訊、密碼及量子信息之複雜性問題研究

《通訊、密碼及量子信息之複雜性問題研究》是依託清華大學，由姚期智擔任項目負責人的重點項目。

基本介紹

• 中文名：通訊、密碼及量子信息之複雜性問題研究
• 依託單位：清華大學
• 項目負責人：姚期智
• 項目類別：重點項目

項目摘要

在過去的30年裡，計算複雜性已經成為信息科學最為主要的研究領域之一。計算複雜性的研究不僅僅局限於具體問題的最佳化算法設計，更為重要的是，這種研究旨在搭建理論框架，促使新型套用成為可能。在本項目中，我們準備從三個層次探索複雜性問題。首先，本項目著眼於研究量子計算複雜性，目的在於理解這項新型技術的功耗與限制。我們尤其希望研究量子多證明者驗證系統下能夠實現的計算可靠性問題。其次，本項目準備研究密碼學中的複雜性問題，尤其希望研究最近提出的非交換群中圖形基礎下安全多方計算效率問題，並研究網際網路環境下基於複雜性的密碼學理論。第三，本項目意在研究通信複雜性中的下限問題。例如，我們希望檢測通信複雜性同類功能下的某些對稱屬性。這些題材的研究需要各種不同的數學技術，我們預期將會運用並發展離散數學，拓撲學、幾何、代數等方面的數學工具。

結題摘要

計算複雜性是信息科學重要研究領域之一，其研究不僅限於具體問題的最佳化算法設計，更重要的是搭建理論框架，促使新型套用成為可能。網際網路的普及以及量子信息的前景，均為此類新型套用提供了絕佳表現機會。本項目從三個層面探索複雜性問題。第一在基礎層面上，研究計算及通信複雜中的上限及下限問題，對此領域中核心觀念，如設計偽隨機生成器進行探索。第二在套用層面上，研究密碼學中的複雜性問題，對已有密碼技術進行安全分析，並對如何最佳化設計進行探索。第三在前瞻性層面上，研究量子信息及複雜性，深入了解這項新型信息技術的基礎及套用。以清華大學交叉信息研究院為基地，本項目進展順利。在以上三個不同方向研究計算複雜性，取得了良好的研究及人才培養成果。這些方向彼此密切關聯，他們的研究相輔相成。例如，密碼學及量子通信學是建築在計算複雜性的數學基礎上，偽隨機數生成在密碼學及計算複雜性兩個領域中都是中心問題，量子博弈論是量子信息和密碼學的交叉領域等等。在量子博弈上，成果同時包括了理論推導及物理實驗論證，這是本項目的另一成功特色。在四年里，本項目完成200餘篇國際會議/期刊論文，包括12篇在理論計算機頂級會議STOC，FOCS，SODA，CCC上發表，以及10篇在密碼學頂級會議CRYTO，Eurocrypt上發表。培養了11位博士生畢業。