AF: Small: Quantum Algorithms and Complexity

这个项目研究量子计算机的能力。主要目标是确定哪些问题具有有效的量子算法，哪些问题在量子计算机的存在下仍然难以解决。这是计算机科学中的一个基本问题。其中一个目标是为量子计算机找到新的应用。第二个目标是了解哪些密码系统对量子计算机是安全的。这些系统必须基于量子计算机无法有效解决的问题。PI和他的研究生们正在考虑这类问题。该方案考虑了二面体隐子群问题的新方法。如果找到解决这个问题的量子算法，将会破坏一些量子安全密码系统的候选方案。如果发现更多的证据表明问题难以解决，那么就会增加对所提议系统安全性的信心。另一种潜在的加速类型是用于优化问题。该工作解决了是否存在近似绝热算法的某些设置，其中量子算法比最佳经典算法获得更好的近似解。最后一个问题是如何理解哈密顿复杂性。

This project studies the power of quantum computers. The main goal is to determine which problems have efficient quantum algorithms andwhich ones remain hard in the presence of quantum computers. This is a fundamental question in computer science. One objective is to find new applications for quantum computers. A second objective is to understand which cryptosystems are secure against quantum computers. These systems must be based on problems that cannot be solved efficiently by quantum computers. The PI and his graduate students are considering these types of problems.The project considers new approaches for the dihedral hidden subgroup problem. A quantum algorithm for this problem, if found, would break some candidates for quantum-secure cryptosystems. If more evidence is found that the problem is difficult to solve, then it increases the confidence in the security of the proposed systems. Another type of potential speedup is for optimization problems. The work addresses whether certain settings for the approximate adiabatic algorithm exist for which the quantum algorithm achieves a betterapproximate solution than the best classical algorithm. The last problem deals with understanding Hamiltonian complexity.