New Developments in Computer Algebra using Techniques from Quantum Computing

使用量子计算技术的计算机代数的新发展

• 批准号: 22800006
• 负责人: LE GALL Francois
• 金额: $ 1.96万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22800006/
• 关键词: アルゴリズム; 計算機代数; 量子計算

We developed new approaches based on techniques from quantum computing to efficiently handle computational problems with an algebraic structure. Among our main results, we constructed new algorithms for distinguishing, in the framework of property testing, classes of groups, and new quantum algorithms for computing efficiently the product of two Boolean matrices. As applications of these novel approaches, we succeeded in proving the hardness of decoding problems arising in quantum communication, and in constructing new protocols for several tasks such as privacy-preserving communication.

我们开发了基于量子计算技术的新方法，以有效地处理具有代数结构的计算问题。在我们的主要成果中，我们构建了用于在属性测试框架中区分群类的新算法，以及用于有效计算两个布尔矩阵乘积的新量子算法。作为这些新颖方法的应用，我们成功证明了量子通信中出现的解码问题的难度，并为隐私保护通信等多项任务构建了新协议。

项目成果

On the distance between non-isomorphic groups

关于非同构群之间的距离

• DOI: 10.1016/j.ejc.2011.10.009
• 发表时间: 2011
• 期刊: European Journal of Combinatorics
• 影响因子: 1
• 作者: G. Ivanyos;F. Le Gall;Y. Yoshida
• 通讯作者: Y. Yoshida

The One-Way Communication Complexity of Subgroup Membership

子组成员资格的单向通信复杂性

• DOI: 10.4086/cjtcs.2011.006
• 发表时间: 2011
• 期刊: Chicago Journal of Theoretical Computer Science
• 作者: S. Aaronson;F. Le Gall;A. Russell;S. Tani
• 通讯作者: S. Tani

量子中継器ネットワークのための量子ネットワークコーディング

量子中继器网络的量子网络编码

• 发表时间: 2012
• 作者: Kento Emoto;Sebastian Ficsher;Zhenjiang Hu;佐藤貴彦,ルガルフランソワ
• 通讯作者: 佐藤貴彦,ルガルフランソワ

An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem

群同构问题某些实例的高效量子算法

• 发表时间: 2010
• 作者: Okuno H.;et al.;F. Le Gall
• 通讯作者: F. Le Gall

量子ネットワーク符号

量子网络代码

• 发表时间: 2010
• 作者: Awaki H.;et al.;西村治道
• 通讯作者: 西村治道