This publication in Theory of Computing is a great cap on my grad school career. My dissertation was all about *theory*, and Theory of Computing is a top-tier respected journal. So, I get one last stamp/sticker/win on my theory work as I start my industry career.

It turns out I was able to fix Scott's bug using another of Scott's results, plus a couple new lemmas.

(Specifically, I showed YQP* is contained in APP and thus is PP-low).

(Scott has joked YQP stands for "Yoda Quantum Polynomial Time"... now some friends joke it stands for "Yirka Quantum Polynomial Time".)

This project has a great story. My adviser, Scott Aaronson, asked me around 2021 if I could fix an error in one of his old papers. I had no idea how, but one day I was reading about a weird complexity class, YQP, in another one of Scott's papers.

Just $995 each!

I had no idea there was competition for the name 😅.
I'm working with Blanqet, the 'q' is apparently very important.

Just to name a few team members: Bill Fefferman, Sean Hallgren, Liang Jiang, Yevgeniy Dodis, and my PhD advisor Scott Aaronson.
Blanqet is based in Chicago, and I'll be working out of Austin.
Hoping to share more details in the future!

Bill is now on my PhD dissertation committee.
I think this is the first time I've disproved someone's published conjecture, so I'm happy Bill just seems happy about it 😄

I revisited the idea over the years, and could never prove the impossibility. Well, in summer 2024, I realized why: the conjecture is false!
This new paper presents an algorithm with the full Grover-style speedup.

Before I started my PhD at UT, I attended AQIS 2018 in Japan. I spoke with Bill Fefferman in Kyoto, and he suggested a conjecture of his for me to work on: that no Grover-style quantum speedup was possible using an in-place query model.

We develop a new quantum search algorithm that achieves the same quantum advantage as Grover's algorithm but in a novel input model that prevents the quantum reflections at the core of Grover's algorithm.

I'm really happy with this project, because it has a great story. 🔖

Unlike in the photo, I'm happy to be on good terms with my committee and expect it to be a nice capstone to my grad school experience.
But, still a little nervous 😅

#PhD #QuantumComputing

As I write my dissertation, I notice and remember things about my past work that could be improved. This one has been in my notebook for years, so it's a good time to share.
I hope somebody solves this problem and responds to my conjecture!