FET: Medium: Quantum Algorithms, Complexity, Testing and Benchmarking

这是量子计算的一个激动人心的时刻，计算思想准备在指导量子计算机实验实现的巨大投资以及密码学，复杂性理论，凝聚态物理和量子引力的基础问题方面发挥更大的作用。该项目包括探索这些问题的强大计划，包括近期量子计算机的测试和基准测试，密码学和量子交叉的基础问题，局部哈密顿和量子概率可检验证明（PCP）基态的复杂性，以及量子引力与量子复杂性和密码学思想之间的相互作用。所提出的研究将深化量子计算理论与实验和理论物理学之间的积极互动，以及与经典复杂性理论和密码学之间的互动。它将把计算透镜带到凝聚态物理和量子引力中一些最基本的问题上。这个项目呈现了两种不同的思路。第一部分探讨了关于近期量子计算机验证和基准测试的计算问题。这包括研究随机电路采样的复杂性（和算法），这是b谷歌“量子霸权”实验的基础，并为下一代量子处理器制定理论上合理但可实现的目标。它还包括为量子计算机的基准测试开发一些基本的原语。第二条线索更加基础，并探讨了一些主题，包括：i)量子哈密顿复杂性的基本问题，包括量子PCP猜想以及某些二维哈密顿量的基态是否具有简洁的经典表示作为投影纠缠对态（PEPS）。ii)在量子计算的背景下重新审视密码学的基本原语。iii)量子引力与复杂性理论和密码学之间的深层关系，包括量子引力中的量子扩展丘奇-图灵命题是否为假，如何形式化量子引力中有效计算的一般概念，以及密码学与贝肯斯坦-霍金辐射本质之间的联系。首席研究员将更新并继续教授名为“量子力学和量子计算”的大规模开放在线课程（MOOC）课程，该课程已经覆盖了全球数万名学生，并参与名为Qubit x Qubit的非营利组织的顾问委员会，该组织成功地覆盖了数百个国家的低收入、代表性不足的少数民族和女学生。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This is an exciting time in quantum computation, with computational ideas poised to play an even larger role in guiding the enormous investment in experimental realization of quantum computers, as well as in foundational questions in cryptography, complexity theory, condensed matter physics and quantum gravity. This project includes robust plans for exploring these issues, including the testing and benchmarking of near-term quantum computers, foundational questions at the intersection of cryptography and quantum, the complexity of ground states of local Hamiltonians and quantum probabilistically checkable proof (PCP), and the interplay between quantum gravity and ideas from quantum complexity and cryptography. The presented research will deepen an already active interaction between the theory of quantum computing and experimental and theoretical physics, as well as with classical complexity theory and cryptography. It will bring the computational lens to bear on some of the most fundamental questions in condensed matter physics and quantum gravity.This project presents two different threads. The first explores computational questions about verification and benchmarking of near-term quantum computers. This includes studying the complexity of (and algorithms for) Random Circuit Sampling, which was the basis of Google’s “quantum supremacy” experiment, and formulating a theoretically sound but achievable goal for the next generation of quantum processors. And it includes developing some of the basic primitives for benchmarking quantum computers. The second thread is more foundational and explores a number of themes including: i) Fundamental questions in Quantum Hamiltonian Complexity, including the quantum PCP conjecture and whether ground states of certain 2D Hamiltonians have succinct classical representations as projected entangled-pair states (PEPS). ii) Re-examining the basic primitives of cryptography in the context of quantum computation. iii) The deep relationship between quantum gravity and complexity theory and cryptography, including questions about whether the quantum extended Church-Turing thesis is false in quantum gravity, how to formalize the general notion of efficient computation in quantum gravity, and connections between cryptography and the nature of Bekenstein-Hawking radiation. The Principal Investigator will update and continue teaching Massive Open Online Course (MOOC) class named "Quantum mechanics and quantum computation" that has already reached tens of thousands of students worldwide and participate in the advisory board of a non-profit called Qubit x Qubit, which is successful reaching low-income, underrepresented minority, and female students across hundreds of countries.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.