Collaborative Research: Quantum Monte Carlo Algorithms and Quantum Circuit Complexity

EIA-0218563 Christopher D.Moore新墨西哥大学合作研究：量子Mote Carlo算法和复杂性这个与康涅狄格大学合作的项目正在探索新的量子算法技术和工具，用于证明量子计算的不可能结果。具体地说，重点是量子蒙特卡罗算法，它试图通过在可能解的空间中进行随机游走来解决问题。此外，对量子计算能力的基本限制进行了探索，开发了量子电路的不可能性结果，并证明了Shor分解算法的简单推广不适用于图同构问题，该问题与分解一起很可能是量子算法的候选。具体地说，通过使用群的傅立叶分析和适用于较不对称空间的新工具，研究了各种组合结构上的量子游动(随机过程的酉类模拟)。人们正在探索量子行走比经典行走更快探索空间的情况，以及量子行走变得局部化和混合比经典行走更慢的其他情况。此外，正在研究傅里叶分析，以开发浅量子电路的下界，以及从量子傅里叶变换中采样过程的信息论界限。特别是，非阿贝尔群上的量子傅立叶变换，以及这类群的隐藏子群和隐藏子空间问题正在被研究。这与图同构密切相关，并探索了易于处理的特殊情况，同时说明了Shor-type算法通常很难实现。

EIA-0218563Christopher D. MooreUniversity of New MexicoCollaborative Research: Quantum Mote Carlo Algorithms and ComplexityThis collaborative project with the University of Connecticut 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 is 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. This is closely related to Graph Isomorphism, and explore tractable special cases while showing it is hard for a Shor-type algorithm in general.