Gregory Rosenthal

I'm a postdoc with Tom Gur and Animesh Datta at University of Cambridge and University of Warwick. Previously I was a computer science PhD student at University of Toronto with Henry Yuen and Benjamin Rossman, and before that I was a math major and computer science minor at Cornell University. My research is in quantum complexity theory, especially the complexity of "inherently quantum" problems with quantum input and/or output.

Email:
PhD thesis: Quantum State and Unitary Complexity
CV
Research Statement
Teaching Statement

photo of me

Research Papers

Quantum Channel Testing in Average-Case Distance
Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, and Tom Gur

Efficient Quantum State Synthesis with One Query
Gregory Rosenthal
SODA 2024 (slides)
QIP 2024

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Gregory Rosenthal
TQC 2022 (slides) - workshop track
In submission at Quantum

Interactive Proofs for Synthesizing Quantum States and Unitaries
Gregory Rosenthal and Henry Yuen
ITCS 2022 (video, slides)
QIP 2022

Bounds on the QAC0 Complexity of Approximating Parity
Gregory Rosenthal
ITCS 2021 (Best Student Paper Award) (video, slides)
TQC 2021 - workshop track

Beating Treewidth for Average-Case Subgraph Isomorphism
Gregory Rosenthal
IPEC 2019 (Best Student Paper Award) (slides)
Algorithmica Special Issue for IPEC 2019

Other Writings