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

新的问题通常通过（隐含地）将它们转化为人们已经知道如何解决的熟悉问题来解决。数学家和计算机科学家将这种方法形式化为约简。该项目将重新审查削减问题，即，转换程序，通过为它们配备新兴的量子计算技术。在开发了基本工具包之后，量子约简将在两个主要方向上使用：将密码学建立在更好理解的NP难问题等基础上，并设计新的算法。这些影响包括加强安全通信和计算的基础，提高成功的量子算法框架的能力，以产生新的算法技术，以及对量子和经典计算的基本能力的深入了解和更好的了解。这项研究将与教育和外联方面的协调努力交织在一起。新的课程和战略将被运用，量子研讨会和编程竞赛等活动将被组织。所有这些都将有助于吸引更多的学生参与量子信息科学，并培养量子和STEM领域的多元化劳动力。该项目将为不同层次的学生提供咨询，并与工业和研究实验室建立联系，以促进研究传播和学生的职业成功。该项目的基本目标是了解量子计算的优势和局限性，并通过一种新的途径，即简化，将一个问题有效地与另一个问题联系起来。系统地研究量子约化下的算法设计、密码学和复杂性理论。主要目标是：1）基于经典对应物（例如，Karp和Turing约简），并找到它们的一般性质; 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.