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

解决新问题的方法通常是（含蓄地）将其转化为人们已经知道如何解决的熟悉问题。数学家和计算机科学家将这种方法形式化为约简。该项目将重新审视减少，即转换过程，通过配备新兴的量子计算技术。在开发基本工具包之后，量子约简将在两个主要方向上使用：基于更好理解的np困难问题等的密码学，以及设计新的算法。其影响包括加强安全通信和计算的基础，提高成功的量子算法框架产生新算法技术的能力，以及发展对量子和经典计算基本能力的见解和更精细的描述。这项研究将与教育和推广方面的协调努力交织在一起。新的课程和策略将被实践，并将组织量子研讨会和编程竞赛等活动。所有这些都将有助于邀请更多的学生学习量子信息科学，并培养量子和STEM领域的多元化劳动力。我们会为不同层次的学生提供意见，并与业界和研究实验室建立联系，以促进研究成果的传播和学生的职业成功。这个项目接近于理解量子计算的优势和局限性的基本追求，并通过一种新的途径使其易于访问，即简化，这是一种有效地将一个问题与另一个问题联系起来的程序。系统研究量子约简下的算法设计、密码学和复杂性理论。主要目标是：1)确定基于经典对立物（例如，卡普和图灵约简）的量子约简的正式定义，并找到它们的一般性质；2)回顾了量子约简下的平均情况硬度，重点研究了基于最坏情况硬度的密码算法，以及密码基元之间的可约性；3)使用量子约简来设计新的算法并建立（最坏情况下）硬度结果，并描绘出量子和经典计算能力的更精细的图景。在教育、指导和推广方面的共同努力将被纳入研究计划，这可以培养新一代量子计算劳动力，并进一步扩大不同学生群体对计算的参与，更广泛地说，是STEM。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.