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招标的两个感兴趣领域的智力Impactresearch 05-501：开发广阔的量子算法集合；量子系统的量子模拟。特殊性问题：隐藏的亚组问题：非阿布莱人隐藏子组问题（HSP）的状态是量子算法中最基本的开放问题之一。特别是，在对称group s上，可以将石墨形态问题作为隐藏的亚组问题提出。可以通过coset状态准备和傅立叶采样来有效地使用量子计算机来有效计算Abelian情况。这种方法的自然概括托管群通常被称为非亚伯HSP的标准方法。该算法的性能取决于该组不可还原复杂表示的特性。但是，在大多数情况下，它们尚未产生有用的算法。提出了研究，以改进这些方法，并确定在哪些情况下绑定到失败的方法，并且需要进行其他方法。算法冷却：算法冷却是量子算法的不可避免的组件：例如，我们甚至可以将故障计算视为移动的热量（随机错误（随机错误），将其视为移动的（随机错误）。这些问题在液态NMRQUANTUM计算以及离子陷阱量子计算的背景下尤其如此，并且过去我们已经研究了它们（尤其是在NMR环境中），从而获得了几乎最适合封闭系统的结果。但是，这些结果表明，封闭系统冷却不能足够强大，足以在大型量子计算机中进行暖量系统。因此，我们正在研究开放系统算法冷却的研究。这需要新的算法技术。同样，由于开放系统比封闭的系统更敏感，因此需要更仔细的模型。耐耐耐受性的量子组合：逆转性是实验量子计算机实现实验的主要障碍。在过去的一年中，在有装饰性的存在下进行易耐故障量子计算的能力有两个显着的突破。在这两种情况下，主要思想是使用唯一的量子特征将数据暴露限制为逆转。我们计划进一步探索这些想法，以a）提高丢弃的ancillas的高架开销，因此需要的量子总数b）改善thesthreshold并减少计算开销，以实现更现实的错误模型2。更广泛的影响力影响：即使量子计算机是遥远的现实，当今的数据加密也无法在将来的时间解密，也取决于密码系统的发展，量子计算机有弹性的攻击。反过来，这需要了解量子计算机上的问题是无法处理的。我们建议创建课程材料，这发生了。