QnTM: Collaborative Research: Quantum Algorithms

QnTM：协作研究：量子算法

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

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.

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