FET: CAREER: Algorithms, cryptography and complexity meet quantum reductions

FET：职业：算法、密码学和复杂性满足量子缩减

基本信息

批准号：
2054758
负责人：
Fang Song
金额：
$ 53.65万
依托单位：
Portland State University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-03-01 至 2025-03-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2054758&HistoricalAwards=false
关键词：
FET CAREER Algorithms cryptography complexity

项目摘要

New problems are often solved by (implicitly) converting them into familiar problems that people already know how to solve. Mathematicians and computer scientists formalize this methodology as reductions. This project will revisit reductions, i.e., the converting procedures, by equipping them with the emerging technology of quantum computing. After developing the basic toolkit, quantum reductions will be employed in two major directions: basing cryptography on the better-understood NP-hard problems and the like, and designing new algorithms. The impacts include strengthening the foundation for secure communication and computation, boosting the power of successful quantum algorithmic framework to produce new algorithmic techniques, as well as developing insights and finer picture into the fundamental capabilities of quantum and classical computation. The research will be intertwined with a concerted effort in education and outreach. New courses and strategies will be exercised, and activities such as quantum workshops and programming contests will be organized. All will serve the goal of inviting more students in quantum information science and training a diverse workforce in quantum and STEM. Advising will be conducted towards a broad group of students at various levels, which will be combined with building connections with industry and research labs to enhance research dissemination and the career success of students.This project approaches the fundamental pursuit of understanding the strengths and limits of quantum computing and making it accessible via a novel route, reductions, which are procedures that effectively relate one problem to another. A systematic investigation will be conducted on algorithm design, cryptography and complexity theory under quantum reductions. The major objectives are: 1) pinning down formal definitions of quantum reductions based on the classical counterparts (e.g., Karp and Turing reductions), and finding their general properties; 2) revisiting average-case hardness under quantum reductions, focusing on the inquiry of basing cryptography on worst-case hardness, and the reducibility between cryptographic primitives; and 3) using quantum reductions to design new algorithms and establish (worst-case) hardness results, and depicting a finer picture of the capabilities of quantum and classical computation. A concerted effort in education, mentoring and outreach will be integrated into the research plan, which can train a new generation of workforce in quantum computation and further broaden the participation in computing, STEM more generally, from a diverse group of students.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.

通常（隐式地）将它们转换为人们已经知道如何解决的熟悉问题，通常可以解决新问题。数学家和计算机科学家将这种方法形式化为减少。该项目将通过为新兴的量子计算技术装备来重新审视降低，即转换过程。在开发了基本工具包之后，量子减少将在两个主要方向上使用：基于加密的NP问题等，并设计新算法。影响包括增强安全通信和计算的基础，增强成功的量子算法框架的力量，以生成新的算法技术，以及将洞察力和更精细的图片发展为量子和古典计算的基本功能。这项研究将与一致的教育和外展工作交织在一起。将采用新的课程和策略，并将组织量子研讨会和节目竞赛之类的活动。所有这些都将为邀请更多的学生参与量子信息科学，并培训量子和STEM的多样化劳动力。建议将向各个级别的一群学生进行，这将与与行业和研究实验室建立联系，以增强研究的传播和学生的职业成功。该项目采取了对理解量子计算的优势和限制的基本力量，并通过新颖的路线可以访问它，这些方法是有效地将一个问题与另一个问题相关联的过程。在量子降低下，将对算法设计，密码学和复杂性理论进行系统研究。主要目标是：1）基于经典对应物（例如，karp和图灵降低）的量子减少的形式定义，并找到它们的一般特性； 2）在量子减少下重新审视平均案例硬度，重点是基于加密术的询问，以及加密原始图之间的降低性； 3）使用量子减少来设计新算法并建立（最坏的）硬度结果，并描述了量子和经典计算能力的更精细图片。在研究计划中，将整合在教育，指导和宣传方面的一致努力，该计划可以培训新一代的劳动力量子计算，并进一步扩大对计算的参与，更普遍地源于一群学生。这一奖项反映了NSF的法定任务，并认为通过基金会的知识优点和广泛的crietia crietia crietia criperia criperia criperia criperia criperia criperia criperia criperia criperia cripitia cristia criperia均值得通过评估。