QnTM: Collaborative Research: Quantum Algorithms

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

1. Intellectual ImpactResearch is proposed on two Areas of Interest in NSF Solicitation 05-501: Development of a broadand general collection of quantum algorithms; Quantum simulation of quantum systems. Specifictopics: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 graphautomorphism problem may be formulated as a hidden subgroup problem over the symmetricgroup S n . The abelian case can be effectively computed with a quantum computer by repetitionof coset state preparation and Fourier sampling. The natural generalization of this method tononabelian groups is commonly referred to as the standard method for the nonabelian HSP. Theperformance of this algorithm depends upon properties of the irreducible complex representationsof the group. However in most cases they do not yet yield useful algorithms. Research is proposedon improving these methods as well as determining in which cases they are bound for failure andother 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 thecomputation registers. These issues are particularly pressing in the context of liquid-state NMRquantum computing as well as ion trap quantum computing, and we have studied them (especiallyin the NMR context) in the past, obtaining results that are nearly best-possible for closed-systemcooling. These results reveal, however, that closed-system cooling cannot be powerful enough toturn warm systems into large-scale quantum computers. We are therefore turning to the studyof open-system algorithmic cooling. This requires new algorithmic techniques. Also, since opensystems are more sensitive to decoherence than closed systems, more careful modeling of theseeffects 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 exposureof data to decoherence. We plan to explore these ideas further to a) improve the overhead in thenumber of ancillas discarded and therefore the total number of qubits required b) improve thethreshold and decrease computational overhead for more realistic error-models2. Broader ImpactSocietal impact: Even if quantum computers are a distant reality, encryption of data today so thatit cannot be decrypted at a future time, depends upon the development of cryptosystems resilientto attacks by quantum computers. This in turn demands an understanding of what problems areand 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 teachingquantum computation, which is also part of our efforts). We propose to create course material tomake this happen.