QnTM: Collaborative Research: The Quantum Complexity of Algebraic Problems

点击翻译按钮获取中文摘要

Quantum computing offers powerful new ways to solve cryptographic problems far more efficiently than classical computers can. This project focuses on the development of new quantum algorithms for problems such as Graph Isomorphism, for which there is no known efficient algorithm on classical computers. We focus on the Hidden Subgroup Problem (HSP) and its relatives. The HSP framework made its first appearance in the seminal work of Simon and Shor, where it led to efficient quantum algorithms for several basic problems in computational number theory, including integer factoring and computing discrete logarithms. In particular, Shor's algorithm for the HSP on the cyclic group makes it possible to break the RSA public-key cryptosystem.The hidden subgroup problems appearing in Simon's and Shor's algorithms take place over commutative groups, a case of the HSP that is now well-understood. The noncommutative hidden subgroup problem is intimately linked to several problems of major interest, including Graph Isomorphism, hidden shift problems, and cryptographically important cases of the Shortest Lattice Vector problem. Despite these incentives, however, the noncommutative HSP has largely resisted the quantum computing community's advances thus far. Efficient algorithms are only known for a few families of groups, and even the information--theoretic aspects of the problem are poorly understood. This project will seek both efficient quantum algorithms and query-complexity lower bounds for the symmetric group---the case of the HSP relevant to Graph Isomorphism---and other groups of algorithmic interest. Our approach applies the rich mathematical tools of representation theory, adapted bases, and entangled measurements over multiple coset states.