| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | March 17, 2020 |
| Latest Amendment Date: | March 17, 2020 |
| Award Number: | 1942706 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Bogdan Mihaila
bmihaila@nsf.gov (703)292-8235 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | April 1, 2020 |
| End Date: | December 31, 2020 (Estimated) |
| Total Intended Award Amount: | $536,497.00 |
| Total Awarded Amount to Date: | $83,289.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3124 TAMU COLLEGE STATION TX US 77843-3124 (979)862-6777 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
HRBB 427 College Station TX US 77845-4645 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | FET-Fndtns of Emerging Tech |
| Primary Program Source: |
01002122DB NSF RESEARCH & RELATED ACTIVIT 01002223DB NSF RESEARCH & RELATED ACTIVIT 01002324DB NSF RESEARCH & RELATED ACTIVIT 01002425DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
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.
Please report errors in award information by writing to: awardsearch@nsf.gov.
