Embedded Files
I am a fourth-year 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.
Magic and communication complexity
Uma Girish, Natalie Parham, Alex May, and Henry Yuen
in submission
[arxiv]
Random Unitaries in Constant (Quantum) Time
Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen
QIP 2026, ITCS 2026
[arxiv]
Quantum circuit lower bounds in the magic hierarchy
Natalie Parham
QIP 2026
[arxiv]
Identity check problem for shallow quantum circuits
Sergey Bravyi, Natalie Parham, and Minh Tran
TQC 2024, ITCS 2026
[arxiv]
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen
QIP 2024, STOC 2024
my slides (with animations)
[arxiv]
Unconditional Quantum Advantage for Sampling with Shallow Quantum Circuits
Adam Bene Watts and Natalie Parham
TQC 2023 invited talk, ITCS 2026
my slides (with animations), Adam's talk video
[arxiv]
Quantum optimization heuristics with an application to knapsack problems
Wim van Dam, Karim Eldefrawy, Nicholas Genise, and Natalie Parham
IEEE Quantum Week 2021
[arxiv], [proceedings version]
Master's Thesis:
Master's Thesis:
On the Power and Limitations of Shallow Quantum Circuits
Department of Combinatorics and Optimization, University of Waterloo
Supervisor: David Gosset
[UWSpace]
Teaching
Teaching
I am a Fall 2025 guest lecturer for Introduction to Quantum Computing (COMS 4281)
In Fall 2023 I was a TA and guest lecturer for Introduction to Quantum Computing (COMS 4281)
Contact
Contact
Email: natalie at cs.columbia.edu
Page updated
Google Sites
Report abuse