The study of quantum computing has gained incredible momentum arising from the discovery, decades ago, of quantum algorithms with immense potential for real-world impact, such as the quantum factoring algorithm, and unstructured database search.  Further impactful real world quantum algorithms have, however, been very elusive, suggesting that each one has a macroscopic effect on the entire field.  Recently, though, there have been published indications that quantum algorithms may be able to solve certain new and special constraint satisfaction problems (CSPs) with the potential for an exponential quantum advantage.  Moreover, while these CSPs do not have a specific real world application as of yet, they seem much closer than prior paradigms designed for near-term quantum computing, such as random circuit sampling, VQE, etc.  We are interested in pursuing this new class of quantum algorithm, improving the known advances where possible, and investigating the potential applications in cryptography, optimization, and beyond.

Meanwhile, near-term quantum computers are advancing, but still unable to run instances of real-world-applicable quantum algorithms.  Furthermore, it is not yet possible to verify the quantum advantage of the existing near term devices.  Two different theoretical disciplines, one focusing on cryptographic proofs of quantumness, and another focused on understanding the classical complexity of simulating limited quantum circuits, both offer the opportunities for theorists to contribute an important (and verifiable) lens into the design and capabilities of near term quantum devices.

key words

Quantum Algorithms; Error Correcting Codes; Low Depth Quantum Circuits; Classical Simulation; Cryptography

Citizenship:  Open to U.S. citizens

Level:  Open to Postdoctoral applicants