QnTM: Collaborative Research: Quantum Algorithms

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

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.