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

点击翻译按钮获取中文摘要

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.