CAREER: New Frontiers of Quantum Pseudorandomness and Complexity

Quantum computing will enable new computational and cryptographic capabilities which can exponentially surpass today’s computers. At the same time, quantum computers will be incapable of solving certain problems efficiently. The goal of this project is to advance quantum security by constructing new forms of cryptography based on quantum mechanics, which show it is possible to hide information in the physical properties of quantum systems. This will demonstrate the limitations quantum computers will face in learning physical properties of quantum systems. It may also enable new ways of hiding information in a way which is secure even against an adversary with a quantum computer. This project includes an integrated education and outreach program to build a robust pipeline of talent to push the field of quantum computing forward. The goal of this project is to construct quantum variants of pseudorandomness which are quantum analogues of pseudorandom generators. Instead of generating numbers which are indistinguishable from random, the goal is to instead construct quantum states which hide some of their quantum mechanical properties, such as their entanglement. This project aims to construct four new forms of quantum pseudorandomness tailored to different applications. These constructions will be designed to 1) show that it is cryptographically hard to deduce the entanglement of quantum systems which arise as ground states of local Hamiltonians, 2) create new post-quantum cryptographic primitives from learning properties of quantum states, 3) create new ways of testing if quantum devices are functioning properly, and 4) tackle core questions in quantum complexity theory, such as the complexity of implementing unitary transformations of quantum systems. 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.