Collaborative Research: Quantum Monte Carlo Algorithms and quantum circuit complexity

合作研究：量子蒙特卡罗算法和量子电路复杂性

• 批准号: 0218443
• 负责人: Alexander Russell
• 金额: $ 15万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0218443&HistoricalAwards=false
• 关键词: Collaborative; Research; Quantum; Monte; Carlo

EIA-0218443Alexander C. RussellUniversity of ConnecticutCollaborative Research: Quantum Mote Carlo Algorithms and ComplexityThis collaborative project with the University of New Mexico is exploring both new quantum algorithmic techniques and tools for proving impossibility results for quantum computation. Specifically, the focus is on quantum Monte Carlo algorithms, which try to solve problems by doing a random walk in the space of possible solutions. In addition, fundamental limits on the power of quantum computation, developing impossibility results for quantum circuits is being explored and proving that simple generalizations of Shor's factoring algorithm will not work for the Graph Isomorphism problem, which along with Factoring is a likely candidate for a quantum algorithm.Specifically, quantum walks (unitary analogues of stochastic processes) on various combinatorial structures by employing both Fourier analysis for groups and new tools suited for less symmetric Spaces are being studied. Cases where quantum walks explore the space more quickly than their classical counterparts, and other cases where they become localized and mix more slowly than a classical walk are being explored. In addition Fourier analysis to develop lower bounds for shallow quantum circuits and information-theoretic bounds on the process of sampling from the quantum Fourier transform are being studied. In particular, the quantum Fourier transform over non-Abelian groups, and hidden subgroup and hidden subspace problems for such groups is being investigated.

EIA-0218443Alexander C.罗素康涅狄格大学合作研究：量子蒙特卡罗算法和复杂性这个与新墨西哥州大学的合作项目正在探索新的量子算法技术和工具，以证明量子计算的不可能性结果。具体来说，重点是量子蒙特卡罗算法，它试图通过在可能的解决方案空间中进行随机游走来解决问题。 此外，量子计算能力的基本限制，量子电路的不可能性结果正在探索中，并证明Shor的因子分解算法的简单推广将不适用于图同构问题，图同构问题与因子分解沿着可能是量子算法的候选者。正在研究通过采用群的傅立叶分析和适合于较不对称空间的新工具在各种组合结构上的量子行走（随机过程的酉模拟）。 量子漫步比经典漫步更快地探索空间的情况，以及它们变得局部化并且比经典漫步更慢地混合的其他情况正在探索中。 此外，正在研究傅立叶分析，以开发浅量子电路的下限和量子傅立叶变换采样过程的信息理论界限。特别是，正在研究非阿贝尔群上的量子傅里叶变换以及此类群的隐藏子群和隐藏子空间问题。