Collaborative Research: FET: Small: Minimum Quantum Circuit Size Problems, Variants, and Applications

合作研究：FET：小型：最小量子电路尺寸问题、变体和应用

• 批准号: 2243659
• 负责人: Nai-Hui Chia
• 金额: $ 30万
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2243659&HistoricalAwards=false
• 关键词: Collaborative; Research; FET; Small; Minimum

A central pursuit in modern computing is to find a method as efficient as possible to solve a computational problem. Abstractly, given the truth table of a function, can one decide the minimum size of a boolean circuit that correctly computes the function? The investigation into it, termed the minimum circuit size problem (MCSP), has accompanied the development of theoretical computer science since the beginning. It manifests diverse and sometimes mysterious properties that prove to be fruitful in investigating the foundations of computing. For instance, efficient algorithms for MCSP imply efficient learning algorithms for important tasks as well as breaking public-key cryptography; and on the other hand, MCSP is useful to demonstrate no-go results such as lower bounds on the computational resources necessary to solve a problem. The goal of this project is to advance quantum information processing through the lens of MCSP. The tools and objects studied in this project can have significant applications in quantum information processing and quantum physics. For instance, we might be able to build novel quantum cryptographic protocols, prove quantum resources lower bounds for basic problems, and show the hardness of estimating the wormhole volume by studying quantum versions of MCSP. Furthermore, this project could stimulate further collaboration between computer scientists and physicists. The research component will be supplemented by a concerted education and outreach plan. This will include developing courses in quantum computing and upgrading the theory curriculum in computer science, establishing groups in quantum computing at participating universities, disseminating the findings to a broad audience, and engaging local communities via successful programs (e.g., Saturday Academy that provides internships to Portland high school students), and hosting quantum coding contests across the two universities. They form a vital part of this project to promote greater interest and proficiency in quantum computing. This project aims to investigate the minimum quantum circuit size for computing various objects along three thrusts. 1) A framework for studying minimum quantum circuit size problems on classical and quantum objects, including functions, quantum states, and unitary operators. New tools will be developed to establish their hardness and connections to fundamental problems in quantum information processing. A new landscape of quantum complexity theory will be identified. 2) Under the framework developed in thrust 1, the problems of deciding the minimum size circuit for simulating a quantum system andfor preparing ground states will be further explored. These two problems represent some of the most viable applications of quantum computers, and the new findings here will depict the algorithmic limits of these applications as well as connect them to other basic primitives in quantum computing. 3) More input models will be explored, including succinct classical descriptions and purely quantum inputs (e.g., a quantum state in a register), and the formal treatment will be accompanied by novel applications, including new protocols for classically verifying quantum resources as well as novel quantum pseudorandom primitives. The proposed work in all these thrusts will expand the scope of quantum information processing and the minimum circuit size problem. Moreover, it will provide new approaches to studying basic quantum primitives and bridging computer science and quantum physics.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.

现代计算中的一个中心追求是找到一种解决计算问题的效率。抽象地，鉴于函数的真实表，可以决定正确计算函数的布尔电路的最小尺寸吗？从一开始，对IT的调查（称为最小电路大小问题（MCSP））伴随着理论计算机科学的发展。它表现出多种多样的，有时甚至是神秘的特性，这些特性在研究计算基础时被证明是富有成效的。例如，MCSP的有效算法暗示着重要任务的有效学习算法以及破坏公共密码术；另一方面，MCSP对于证明无需结果很有用，例如解决问题所需的计算资源上的下限。该项目的目的是通过MCSP的镜头推进量子信息处理。该项目中研究的工具和对象可以在量子信息处理和量子物理学中具有重要的应用。例如，我们也许能够构建新颖的量子加密协议，证明量子资源的基本问题降低界限，并通过研究MCSP的量子版本来估算虫洞体积的硬度。此外，该项目可以刺激计算机科学家与物理学家之间的进一步合作。研究组成部分将由一致的教育和外展计划补充。这将包括开发量子计算的课程并升级计算机科学中的理论课程，在参与大学的量子计算中建立小组，将发现传播给广泛的受众，并通过成功的课程（例如，通过成功的周六学院为当地社区提供实习，向波特兰较高的学生提供实习），并举办量子编码竞赛跨两所大学。它们构成了该项目的重要组成部分，以提高量子计算的更大兴趣和熟练程度。该项目旨在研究沿三个推力计算各种对象的最小量子电路大小。 1）研究经典和量子对象（包括功能，量子状态和统一操作员）上最小量子电路大小问题的框架。将开发新工具，以建立与量子信息处理中基本问题的硬度和联系。将确定量子复杂性理论的新景观。 2）在推力1中开发的框架下，将进一步探讨确定模拟量子系统和准备基础状态的最小尺寸电路的问题。这两个问题代表了量子计算机的一些最可行的应用，此处的新发现将描述这些应用程序的算法限制，并将它们连接到量子计算中的其他基本基础。 3）将探索更多的输入模型，包括简洁的经典描述和纯粹的量子输入（例如，寄存器中的量子状态），正式处理将伴随新的新应用，包括用于经典验证量子资源的新协议以及新颖的量子量子pseudorandom原始原则。所有这些推力中提出的工作将扩大量子信息处理的范围和最小电路尺寸问题。此外，它将提供新的方法来研究基本的量子原始基原始素和桥接计算机科学和量子物理学。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛的影响评估的评估来进行评估的。