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

新的问题通常通过(隐含地)将它们转化为人们已经知道如何解决的熟悉的问题来解决。数学家和计算机科学家将这种方法形式化为约化。该项目将重新审视削减，即转换程序，为他们配备新兴的量子计算技术。在开发了基本的工具包之后，量子约简将在两个主要方向上使用：基于更好地理解的NP-Hard问题的密码学等，以及设计新的算法。这些影响包括加强安全通信和计算的基础，增强成功的量子算法框架产生新算法技术的能力，以及发展对量子和经典计算基本能力的洞察和更精细的描述。这项研究将与教育和外联方面的协调努力交织在一起。将练习新的课程和策略，并组织量子研讨会和编程竞赛等活动。所有这些都将服务于邀请更多量子信息科学学生和培训量子和STEM方面的多样化劳动力的目标。将向不同层次的广泛学生群体提供建议，这将与与工业和研究实验室建立联系相结合，以促进研究传播和学生的职业成功。该项目接近基本追求，即了解量子计算的优势和限制，并通过一种新的途径-简化-这是有效地将一个问题与另一个问题联系起来的程序。对量子约简下的算法设计、密码学和复杂性理论进行了系统的研究。主要目标是：1)基于经典约化(如Karp约化和图灵约化)确定量子约简的形式化定义，并找到它们的一般性质；2)重温量子约简下的平均情况硬度，重点探讨密码学基于最坏情况硬度的密码学基础以及密码基元之间的可约性；以及3)使用量子约简来设计新的算法和建立(最坏情况)硬度结果，并更好地描绘量子计算和经典计算的能力。在教育、指导和推广方面的协同努力将被整合到研究计划中，该计划可以培训新一代量子计算劳动力，并进一步扩大不同学生群体对计算的参与，更广泛地说，STEM。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.