| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | September 10, 2020 |
| Latest Amendment Date: | October 14, 2020 |
| Award Number: | 2041841 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Elizabeth Behrman
ebehrman@nsf.gov (703)292-7049 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | March 1, 2020 |
| End Date: | September 30, 2023 (Estimated) |
| Total Intended Award Amount: | $202,058.00 |
| Total Awarded Amount to Date: | $202,058.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1600 SW 4TH AVE PORTLAND OR US 97201-5508 (503)725-9900 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
1600 SW 4th Avenue Portland OR US 97207-0751 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Quantum Computing |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Pseudo-randomness, an efficient approximation for true randomness, has become indispensable in algorithm design, coding theory, cryptography and complexity theory. This project aims to develop a comprehensive theory of computational pseudo-randomness in the setting of quantum information processing. These pseudo-random objects and tools can be useful in quantum algorithm design and quantum complexity theory. The computational approach of this project to some problems outside the conventional territory of computing could stimulate further collaboration between computer scientists, quantum information theorists and physicists. Course development, assisting the development of local ``Women in CS'' chapter and ``Women in Tech'' events, establishing interest groups in quantum computing at the university to attract underrepresented students, as well as outreach to high school students are an integral part of this award.
This specific focus is on computational pseudorandomness, which is indistinguishable from true randomness as far as efficient observers are concerned. There are three major objectives: 1) formalize and design pseudorandom quantum states and quantum operators, in analogy to two basic classical pseudorandom objects -- pseudorandom generators and pseudorandom functions; 2) investigate their applications in computer science, especially in quantum cryptography such as constructing quantum money, quantum authentication, and a novel primitive of tokenized cryptography. This requires developing appropriate quantum security models and designing new schemes; 3) develop other quantum pseudorandom objects and explore applications beyond computer science such as understanding black holes and thermalization in physics. The proposed pseudorandom objects and techniques to be developed can provide more efficient solutions to some proposed applications or even overcome some no-go results in the information-theoretical setting. This study complements the work on quantum state and unitary designs, which are statistical approximations to the quantum Haar randomness. Together, they can reveal more insights to the fundamental properties of quantum information. The computational lens of studying problems beyond computer science can be fruitful elsewhere.
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This project aimed to develop computational quantum pseudorandom objects and use them to investigate a variety of topics in quantum information science. This was inspired by the success of the classical counterparts, e.g., pseudorandom generators and pseudorandomfunctions, which have proven fruitful to information theory, algorithmdesign, cryptography, etc.
There were a number of significant outcomes produced during this project. A major achievement was introducing pseudorandom state generators (PRS), which efficiently generate quantum states that are computationally indistinguishable from those sampled from the Haar measure (analogous to a uniform random distribution). The work by the PI gave an construction of PRS based on the existence of one-way functions. Fundamental properties of a PRS were also shown, includingno-cloning of PRS by poly-time algorithms and that pseudorandom states are highly entangled. The no-cloning property was then employed to obtain a generic construction of quantum money. Moreover, the PI's work formulated quantum unitary operations (PRU) and proposed candidate constructions.
The quantum pseudorandomness results in this project had spurred a lot of interests and influenced multiple disciplines. The most notable was reshaping the landscape of quantum cryptography and offering an avenue for demonstrating quantum advantage via cryptography. Aside from a host of applications immediately enabled by pseudorandom states that are impossible classically such as copy-protection, it became an emerging pursuit to revisit the weakest assumption needed forcryptography. This is due to the evidence shown by Kretschmer that in a relativized world, PRS is weaker than one-way functions, which are viewed a minimal assumption for classical cryptography. It was found that many primitives can in fact be realized from PRS, such as multiparty computation and trapdoor functions, and one-way functions were either necessary or even insufficient before these new developments.
In addition to cryptography, the outcomes in this project also inspired new approaches to black hole and quantum gravity using pseudorandom states. The entanglement property of PRS shown by the PI's work was further developed into a systematic study of pseudoentanglement with applications in gravity. In fact, realizing a provable-secure pseudorandom unitary operator, a primitive introduced in this project, is currently viewed as a fundamental open question in the community, since PRU might be more useful in both cryptography and quantum gravity. Close to the end of this project, the PI's work made a promising step by realizing a necessary property of PRU, which was lacking in PRS.
The research outcomes were also supplemented by extensive efforts by the PI on disseminating the findings to a broad audience, involving students at various levels in the research process, and updating courses such as Theory of Computation and Quantum Computing that both integrated the developments of this project and made adaptations to better prepare students for pursusing these topics.
Last Modified: 03/04/2024
Modified by: Fang Song
Please report errors in award information by writing to: awardsearch@nsf.gov.
