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

新问题通常是通过（隐式地）将其转换为人们已经知道如何解决的熟悉问题来解决的。数学家和计算机科学家将这种方法形式化为归约。该项目将通过为它们配备新兴的量子计算技术来重新审视简化（即转换程序）。开发出基本工具包后，量子约简将应用于两个主要方向：将密码学基于更好理解的NP难题等，以及设计新算法。其影响包括加强安全通信和计算的基础，增强成功的量子算法框架产生新算法技术的能力，以及对量子和经典计算的基本能力形成深入的见解和更清晰的认识。该研究将与教育和推广方面的共同努力交织在一起。将实施新的课程和策略，并组织量子研讨会和编程竞赛等活动。所有这些都将服务于吸引更多量子信息科学学生并培训量子和 STEM 领域多元化劳动力的目标。将为各个级别的广大学生提供建议，同时与行业和研究实验室建立联系，以促进研究传播和学生的职业成功。该项目的基本追求是了解量子计算的优势和局限性，并通过一种新颖的途径、简化（即有效地将一个问题与另一个问题联系起来的程序）使其易于使用。对量子约简下的算法设计、密码学和复杂性理论进行系统研究。主要目标是：1）根据经典对应物（例如卡普和图灵还原）确定量子还原的正式定义，并找到它们的一般性质； 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.