QnTM: Collaborative Research: Quantum Algorithms

QnTM：协作研究：量子算法

• 批准号: 0524837
• 负责人: Umesh Vazirani
• 金额: $ 15万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0524837&HistoricalAwards=false
• 关键词: QnTM; Collaborative; Research; Quantum; Algorithms

1. Intellectual Impact Research is proposed on two Areas of Interest in NSF Solicitation 05-501: Development of a broad and general collection of quantum algorithms; Quantum simulation of quantum systems. Specific topics: Hidden subgroup problems: The status of the non-abelian hidden subgroup problem (HSP) is one of the most fundamental open problems in quantum algorithms. In particular, the graph automorphism problem may be formulated as a hidden subgroup problem over the symmetric group S n . The abelian case can be effectively computed with a quantum computer by repetition of coset state preparation and Fourier sampling. The natural generalization of this method to nonabelian groups is commonly referred to as the standard method for the nonabelian HSP. The performance of this algorithm depends upon properties of the irreducible complex representations of the group. However in most cases they do not yet yield useful algorithms. Research is proposed on improving these methods as well as determining in which cases they are bound for failure and other methods are necessitated. Algorithmic cooling: Algorithmic cooling is an inescapable component of quantum algorithms: for example, we can even view fault-tolerant computing as moving heat (random errors) out of the computation registers. These issues are particularly pressing in the context of liquid-state NMR quantum computing as well as ion trap quantum computing, and we have studied them (especially in the NMR context) in the past, obtaining results that are nearly best-possible for closed-system cooling. These results reveal, however, that closed-system cooling cannot be powerful enough to turn warm systems into large-scale quantum computers. We are therefore turning to the study of open-system algorithmic cooling. This requires new algorithmic techniques. Also, since open systems are more sensitive to decoherence than closed systems, more careful modeling of these effects will be required. Fault-tolerant Quantum Comptutation: Decoherence is the major obstacle to the experimen- tal realization of quantum computers. Over the last year there have been two significant break- throughs in the ability to carry out fault-tolerant quantum computation in the presence of deco- herence. The main idea in both cases is the use of uniquely quantum features to limit the exposure of data to decoherence. We plan to explore these ideas further to a) improve the overhead in the number of ancillas discarded and therefore the total number of qubits required b) improve the threshold and decrease computational overhead for more realistic error-models 2. Broader Impact Societal impact: Even if quantum computers are a distant reality, encryption of data today so that it cannot be decrypted at a future time, depends upon the development of cryptosystems resilient to attacks by quantum computers. This in turn demands an understanding of what problems are and are not tractable on quantum computers, a core topic of the proposed research. Educational impact: Ideas from quantum computation and quantum information can poten- tially have a major impact on how basic quantum mechanics is taught (quite apart from teaching quantum computation, which is also part of our efforts). We propose to create course material to make this happen.

1. NSF征集05-501中提出了两个感兴趣领域的智力影响研究：开发广泛而通用的量子算法集合;量子系统的量子模拟。具体专题：隐藏的子群问题：非交换隐子群问题是量子算法中最基本的公开问题之一。特别地，图自同构问题可以被公式化为对称群Sn上的隐子群问题。通过重复陪集态制备和傅立叶采样，可以用量子计算机有效地计算阿贝尔情形。这种方法自然推广到非阿贝尔群通常被称为非阿贝尔HSP的标准方法。该算法的性能取决于群的不可约复表示的性质。然而，在大多数情况下，他们还没有产生有用的算法。研究提出了改进这些方法，以及确定在哪些情况下，他们注定失败和其他方法是必要的。制冷：量子冷却是量子算法的一个不可避免的组成部分：例如，我们甚至可以将容错计算视为将热量（随机错误）从计算寄存器中移出。这些问题在液态NMR量子计算和离子阱量子计算的背景下特别紧迫，我们过去已经研究过它们（特别是在NMR背景下），获得了几乎最适合封闭系统冷却的结果。然而，这些结果表明，封闭系统的冷却能力不足以将温暖的系统变成大规模的量子计算机。因此，我们转向开放系统算法冷却的研究。这需要新的算法技术。此外，由于开放系统比封闭系统对退相干更敏感，因此需要对这些效应进行更仔细的建模。容错量子计算：退相干是量子计算机实验实现的主要障碍。在过去的一年里，在存在退相干的情况下进行容错量子计算的能力有两个重大突破。这两种情况的主要思想都是使用独特的量子特征来限制数据对退相干的暴露。我们计划进一步探索这些想法，以a）改善丢弃的辅助器数量的开销，从而改善所需的量子位的总数B）改善阈值并降低计算开销，以获得更现实的错误模型2。社会影响：即使量子计算机是一个遥远的现实，今天的数据加密，使其无法在未来的时间被解密，取决于对量子计算机攻击有弹性的密码系统的发展。这反过来又要求理解什么问题在量子计算机上是可处理的，什么问题在量子计算机上是不可处理的，这是拟议研究的核心主题。教育影响：量子计算和量子信息的思想可能会对基础量子力学的教学方式产生重大影响（除了教授量子计算之外，这也是我们努力的一部分）。我们建议创建课程材料来实现这一点。