I am a PhD student in the theoretical computer science group at Columbia University, advised by Henry Yuen. I am broadly interested in quantum computation and computational complexity theory. I've been particularly interested in quantum circuit complexity.
Previously, I completed my MMath at the Institute for Quantum Computing at the University of Waterloo, where I was advised by David Gosset. I received my BS in Electrical Engineering and Computer Science from UC Berkeley.
My research is supported by the Google PhD fellowship.
Identity check problem for shallow quantum circuits
with Sergey Bravyi, and Minh Tran
TQC 2024
[arxiv]
On the Pauli Spectrum of QAC0
with Shivam Nadimpalli, Francisca Vasconcelos, and Henry Yuen
QIP 2024, STOC 2024
my slides (with animations)
[arxiv]
Unconditional Quantum Advantage for Sampling with Shallow Quantum Circuits
with Adam Bene Watts
TQC 2023 invited talk (see Adam's talk here)
my slides (with animations)
[arxiv]
Quantum optimization heuristics with an application to knapsack problems
with Wim van Dam, Karim Eldefrawy, and Nicholas Genise
IEEE Quantum Week 2021
[arxiv], [proceedings version]
On the Power and Limitations of Shallow Quantum Circuits
Department of Combinatorics and Optimization, University of Waterloo
Supervisor: David Gosset
[UWSpace]
In Fall 2023 I was a TA and guest lecturer for:
Introduction to Quantum Computing (COMS 4281)
Email: natalie at cs.columbia.edu