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

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

基本信息

  • 批准号:
    2224132
  • 负责人:
  • 金额:
    $ 30万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2022
  • 资助国家:
    美国
  • 起止时间:
    2022-10-01 至 2022-10-31
  • 项目状态:
    已结题

项目摘要

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.
现代计算的核心追求是找到一种尽可能有效的方法来解决计算问题。抽象地说,给定一个函数的真值表,人们能否决定正确计算该函数的布尔电路的最小尺寸?最小电路尺寸问题(MCSP)是伴随着理论计算机科学的发展而产生的。它表现出多种多样的,有时是神秘的属性,证明是富有成效的调查计算的基础。例如,MCSP的有效算法意味着重要任务的有效学习算法以及打破公钥密码学;另一方面,MCSP有助于证明不可行的结果,例如解决问题所需的计算资源的下限。该项目的目标是通过MCSP的透镜推进量子信息处理。该项目中研究的工具和对象可以在量子信息处理和量子物理学中有重要的应用。例如,我们可能能够建立新的量子密码协议,证明基本问题的量子资源下界,并通过研究MCSP的量子版本来显示估计虫洞体积的难度。此外,该项目还可以促进计算机科学家和物理学家之间的进一步合作。研究部分将辅之以协调一致的教育和外联计划。这将包括开发量子计算课程和升级计算机科学理论课程,在参与大学建立量子计算小组,向广大受众传播研究结果,并通过成功的计划(例如,周六学院为波特兰高中生提供实习机会),并在两所大学举办量子编码竞赛。它们构成了该项目的重要组成部分,以促进对量子计算的更大兴趣和熟练程度。本项目旨在研究计算沿着三个推力的各种物体的最小量子电路尺寸。1)一个研究经典和量子对象上的最小量子电路尺寸问题的框架,包括函数、量子态和幺正算子。将开发新的工具来建立它们的硬度和与量子信息处理中基本问题的联系。量子复杂性理论的一个新的景观将被确定。2)在第一部分的框架下,我们将进一步探讨模拟量子系统和制备基态所需的最小电路尺寸的确定问题。这两个问题代表了量子计算机的一些最可行的应用,这里的新发现将描述这些应用的算法限制,并将它们与量子计算中的其他基本原语联系起来。3)更多的输入模型将被探索,包括简洁的经典描述和纯粹的量子输入(例如,寄存器中的量子态),并且正式处理将伴随着新的应用,包括用于经典地验证量子资源的新协议以及新的量子伪随机原语。所有这些方面的工作都将扩大量子信息处理的范围和最小电路尺寸问题。此外,它将提供新的方法来研究基本的量子原语和桥梁计算机科学和量子物理学。这个奖项反映了NSF的法定使命,并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Nai-Hui Chia其他文献

Nai-Hui Chia的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Nai-Hui Chia', 18)}}的其他基金

CAREER: Complexity Theory of Quantum States: A Novel Approach for Characterizing Quantum Computer Science
职业:量子态复杂性理论:表征量子计算机科学的新方法
  • 批准号:
    2339116
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Continuing Grant
Collaborative Research: FET: Small: Minimum Quantum Circuit Size Problems, Variants, and Applications
合作研究:FET:小型:最小量子电路尺寸问题、变体和应用
  • 批准号:
    2243659
  • 财政年份:
    2022
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant

相似国自然基金

Research on Quantum Field Theory without a Lagrangian Description
  • 批准号:
    24ZR1403900
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
Cell Research
  • 批准号:
    31224802
  • 批准年份:
    2012
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research
  • 批准号:
    31024804
  • 批准年份:
    2010
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Cell Research (细胞研究)
  • 批准号:
    30824808
  • 批准年份:
    2008
  • 资助金额:
    24.0 万元
  • 项目类别:
    专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
  • 批准号:
    10774081
  • 批准年份:
    2007
  • 资助金额:
    45.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
  • 批准号:
    2403559
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329909
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
  • 批准号:
    2403560
  • 财政年份:
    2024
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Medium:Compact and Energy-Efficient Compute-in-Memory Accelerator for Deep Learning Leveraging Ferroelectric Vertical NAND Memory
合作研究:FET:中型:紧凑且节能的内存计算加速器,用于利用铁电垂直 NAND 内存进行深度学习
  • 批准号:
    2312886
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Medium:Compact and Energy-Efficient Compute-in-Memory Accelerator for Deep Learning Leveraging Ferroelectric Vertical NAND Memory
合作研究:FET:中型:紧凑且节能的内存计算加速器,用于利用铁电垂直 NAND 内存进行深度学习
  • 批准号:
    2312884
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Medium: Efficient Compilation for Dynamically Reconfigurable Atom Arrays
合作研究:FET:中:动态可重构原子阵列的高效编译
  • 批准号:
    2313084
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Theoretical Foundations of Quantum Pseudorandom Primitives
合作研究:FET:小型:量子伪随机原语的理论基础
  • 批准号:
    2329938
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Medium: Design and Implementation of Quantum Databases
合作研究:FET:媒介:量子数据库的设计和实现
  • 批准号:
    2312755
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: De Novo Protein Scaffold Filling by Combinatorial Algorithms and Deep Learning Models
合作研究:FET:小型:通过组合算法和深度学习模型从头填充蛋白质支架
  • 批准号:
    2307573
  • 财政年份:
    2023
  • 资助金额:
    $ 30万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了