Quantum Complexity Theory Student Project Showcase #5 (2025 Edition)!
Sorry for the long blog-hiatus! I was completely occupied for weeks, teaching an intensive course on theoretical computer science to 11-year-olds (!), at a math camp in St. Louis that was also attended by my 8-year-old son. Soon I’ll accompany my 12-year-old daughter to a science camp in Connecticut, where I’ll also give lectures.
There’s a great deal to say about these experiences, but for now: it’s been utterly transformative and life-affirming to spend my days in teaching precocious, enthusiastic, non-jaded children the material I love in the real world, rather than (let’s say) in scrolling through depressing world news and social media posts and emails from hateful trolls on my phone. It’s made me feel 25 years younger (well, at least until I need to walk up a flight of stairs). It’s made me want to go back to actual research and teaching, which besides family and friends have been the main sources of joy in my life.
So on that note, and without further ado: I hereby present the latest Quantum Complexity Theory Student Project Showcase! As the name suggests, this is where I share a selection of the best research projects, from the students who took my graduate class on Quantum Complexity Theory at UT Austin this past spring.
See here for the four previous iterations of the Showcase:
- 2011 edition (MIT)
- 2012 edition (MIT)
- 2014 edition (MIT)
- 2021 edition (MIT / UT Austin)
(As you can see, the timing hasn’t been 100% consistent.)
I expect that, as in past editions, many of this year’s projects will lead to published research papers, or at the very least, preprints on the arXiv.
And now, really without further ado, the projects!
(1) Quantum Hermite Transform and Gaussian Goldreich-Levin, by Vishnu Iyer and Siddhartha Jain.
Vishnu and Sid propose a new primitive for quantum algorithms—the Hermite transform, as opposed to the Fourier transform—and give at least one successful example of its use. They’d be eager to know if anyone can think of other applications!
(2) Quantum Statistical Witness Indistinguishability, by Shafik Nassar and Ronak Ramachandran.
In modern cryptography, even if it isn’t statistical zero-knowledge (SZK), a proof protocol might have the weaker property of being statistically witness-indistinguishable (SWI): that is, Arthur can’t tell which of two possible yes-witnesses Merlin holds. Here Shafik and Ronak initiate the study of quantum SWI, and prove the basic properties of this notion, such as the equivalence of honest and dishonest verifier. Hopefully this will serve as a springboard for someone to find an actual QSWI protocol for an interesting problem.
(3) A Zero-Knowledge Protocol for Keyed Unitary Families, by David Joy and Angela Zhang.
Continuing the theme of quantum zero-knowledge, David and Angela give a protocol by which Merlin can convince Arthur that he knows a unitary relating one pure state to another, without revealing the unitary. Again continuing a theme, applications of this protocol are sought!
(4) On Query Lower Bounds for Aaronson-Kuperberg Unitary Synthesis Circuits, by Arko Banerjee.
Back in 2006, when we formulated our so-called “Unitary Synthesis Conjecture,” Greg Kuperberg and I showed that if a quantum algorithm applies an n-qubit unitary U(f) after making a single query to a Boolean function f, then as we range over f’s, there can be at most 4n possible values of U(f). Here Arko improves our bound to 2n, which is tight. He also tries extremely hard to generalize our bound to the two-query case, not quite succeeding but proving partial results that hopefully will be helpful to others.
(5) Quantum Search with Non-Interacting Bosons and Fermions, by Aravind Karthigeyan.
This one really made me think. Aravind studies the problem of search for a single marked vertex, on the complete graph with N vertices, using either M bosons or M fermions that can hop between the vertices. With M bosons, he shows that the search succeeds in Θ(√(N/M)) time with high probability, which is just the usual runtime for Grover search with M parallel searchers. With fermions, by contrast, he shows that more time is needed. Why? Because of the Pauli Exclusion Principle! The fermions all “step on each others’ toes,” competing to be the one that jumps onto the marked vertex, which limits the advantage of having M fermions searching in parallel.
(6) Limits to Pseudodeterminism in Quantum Communication Protocols, by Jiawei Li.
Jiawei revisits the famous Hidden Matching Problem, which is known to have an exponential gap between its randomized one-way communication complexity of ~√n, and its quantum one-way communication complexity of ~log(n). He makes a new observation about this problem: namely, if you want the exponential quantum communication advantage, then you must content yourself with a protocol that can generate many different possible correct answers with appreciable probabilities (i.e., that generates large min-entropy). In other words, no good quantum protocol for the problem is pseudodeterministic. This complements, for example, my and Shih-Han Hung’s work, which showed the same statement for quantum supremacy experiments based on Random Circuit Sampling, or the long line of works that showed it for experiments that violate the Bell/CHSH inequality.
Congratulations to my students for their accomplishments, and thanks to them for giving me permission to include their work in this showcase!
Follow
Comment #1 August 1st, 2025 at 7:47 am
> …in the real world, rather than (let’s say) in scrolling through depressing world news and social media posts and emails from hateful trolls on my phone….
Have you considered making this a permanent change? Sounds like you maybe need it.
I haven’t read the news for years, have an old 3310 mobile that can’t do anything except phone calls, and wouldn’t dream of checking my email more than once a day, and as far as I can tell, I haven’t lost anything by this.
I did find out about the coronavirus a couple of weeks later than everyone else (My Mum rang up to ask what I thought about it!), but I still got all my panic buying done long before anyone else.
Leave all your electric foolishness at home one day and take a couple of complexity theory papers down the pub for a coffee. Take paper and some nice coloured pens. It’s lovely.
Comment #2 August 1st, 2025 at 9:19 am
Okay when I first read this post I didn’t interpret it properly, and thought that the quantum complexity projects were done by the 11 year-olds at math camp. I was gonna say, “Wow, those are some insanely impressive projects!”
In my defense I hadn’t finished my coffee yet.
Comment #3 August 1st, 2025 at 10:13 am
Yonah Borns-Weil #2: LOL. As it happens, the 11-year-olds also did research projects, which they presented in a nice poster session, and which were extremely impressive for 11-year-olds. But they were mostly about rediscovering known results in elementary number theory and finite geometry.
Comment #4 August 1st, 2025 at 12:23 pm
Do you happen to have any Austin area recommendations for precocious 6 year olds who like math?
Comment #5 August 1st, 2025 at 2:47 pm
I am among those (not just a few, I would guess) of your loyal readers who would love to see, and would no doubt profit from viewing, the efforts of your 11 year-old students.
Comment #6 August 1st, 2025 at 6:24 pm
Congratulations on your well-earned vacation from Internet asshollery.
Comment #7 August 1st, 2025 at 6:55 pm
Judging just by name, Quantum Hermite Transform sounds like something that ought to have applications in lattice-based crypto.
Comment #8 August 1st, 2025 at 8:07 pm
Rob P #4: Russian School of Math? Saturday Morning Math Circle? But not sure at what ages those start; it might be older.
Comment #9 August 1st, 2025 at 8:09 pm
Patrick M. Dennis #5: I wasn’t involved with their research projects — that would be between the camp, the students, and their parents.
On the other hand, I’m thinking of posting the notes from my lectures, if I can find someone to transcribe them for me in a reasonable way (possibly with AI assistance). Right now they’re ~70 handwritten pages with lots of margin notes.
Comment #10 August 2nd, 2025 at 9:25 am
The notion of “pseudodeterminism” is very interesting.
Are there papers that approach it as a continuous measure rather than a yes/no measure? For example, if a randomized algorithm has n bits of output but variant A has n/2 bits of entropy in the output whereas variant B has log_2(n) bits of entropy in the output then B is “exponentially more pseudodeterministic” than A?
Comment #11 August 2nd, 2025 at 10:33 am
Scott,
“Quantum Search with Non-Interacting Bosons and Fermions, by Aravind Karthigeyan. –
With fermions, by contrast, he shows that more time is needed.”
Does this have anything to do with Chiral nature of Fermions. Just reminds me of the discussions triggered by David Tong’s posts. Does calculation efficiency being different for Fermions even on a QC have any implications for the Church-Turing/Extended hypothesis ?
Thanks
Prasanna
Comment #12 August 2nd, 2025 at 10:44 am
Scott, I am happy to hear all this! I think you should seriously consider reducing the amount of time you interact online or spend reading all sorts of horrible news. It will do wonders for your mental health. Get back to research, spend time with your family, do hobbies, whatever. Even though we love seeing you blogging, interacting with all sorts of hateful trolls online or reading constantly depressing news helps no one. Take care of your self!
Comment #13 August 2nd, 2025 at 3:37 pm
Craig Gidney #10: Yes, absolutely. In my paper with Shih-Han Hung (for example), that’s exactly what we do: we lower-bound the amount of min-entropy that needs to be in the output (under hardness assumptions), rather than just saying it needs to be pseudodeterministic. Jiawei does that in his project as well.
Comment #14 August 2nd, 2025 at 3:39 pm
Prasanna #11: No, it has nothing whatsoever to do with the chiral nature of fermions, which only shows up in more sophisticated contexts. As I said, it’s all about the Pauli exclusion principle.
Comment #15 August 2nd, 2025 at 3:51 pm
Incidentally, I find it incredible that even in this post, which I opened by celebrating my brief liberation from the tyranny of people screaming on the Internet that’s gradually taken over my whole life, and continued with quantum computing projects … still multiple commenters tried to bait me into arguing with them about Israel and Gaza.
No. I’m not going to do it. I’m not even going to post those comments. Maybe we’ll circle back to it in a future post, but not now.
Comment #16 August 4th, 2025 at 12:15 am
Scott, have you considered using LLMs to filter the comments for you (if you haven’t already)?
It should be simple enough to hook up an LLM API and task it to block all the comments about say Gaza/politics in general/anything off-topic (prepend the blogpost in the context), with the option to review them yourself later, get a censored summary of the blocked comments, or don’t even bother.
For the sake of your sanity and happiness, do give it a try! I’m sure many readers would love to build it for you.
Comment #17 August 5th, 2025 at 6:44 pm
These projects all look very interesting!
Regarding the limits of pseudodeterminism in Hidden Matching, we derived basically the same result in this paper: https://arxiv.org/abs/2410.11827 (Theorem 10 – it’s stated for parallel-repeated Hidden Matching, because we need that in our application, but the proof works for a single instance as well). In our case this was an intermediate result and we ended up using it to prove that Hidden Matching requires uncloneable quantum states as advice.
Comment #18 August 9th, 2025 at 11:28 am
Hi Scott,
1. For the QSWI paper, since the major transformations (KW, MW, Watrous rewinding) appear to be agnostic to whether the witness is classical or quantum, do you think/conjecture that $$\mathrm{hvQMA\text{-}QSWI} = \mathrm{QMA\text{-}QSWI}$$ I understand the proof requires the ability to classically choose between two witnesses using a classical bit, but because of the no-cloning theorem and non-orthogonal quantum states it would be a lot more difficult, though.
2. For the boson paper, I am shocked that this hasn’t been done before by bored physicists. There seems to be a very explicit duality between a non-interacting boson system on a complete graph and a SU(2) system precessing in a magnetic field that was just discovered. I have spent way too much time checking if this result had existed before, and that alone is shocking. The speedup seems to be the least important thing in that paper.
Second, the analysis assumes perfect permutation symmetry and non-interacting bosons. The spin-J mapping really hinges on the complete-graph symmetry, but do you think some of this speedup survives for less symmetric graphs, say Hamming graphs which still are invariant under the symmetric group and Schur’s lemma would still apply? The symmetry reduction wouldn’t go through cleanly, but perhaps approximate concentration in the symmetric subspace could still yield results.
3. For the AK Synthesis Paper. I found your verification of the AK one-query bound especially nice. I like how you emphasized the geometric “no-garbage” constraint as the heart of the O(N)-bit dependence, rather than treating it as just a corollary of the polynomial method. I had a few follow-up thoughts and open questions from your review.
First, on the multi-query case, given that the RHW 2d constraints alone can’t force M=O(N), do you think there’s a viable hybrid approach that mixes the purely algebraic constraints with some geometric structure from the circuit (e.g., invariance properties of intermediate subspaces, like in Theorem 2.2)? My worry is that without pulling in that geometric ingredient, we’ll stay stuck at the O(N^2) orthogonality bound you mention in the star-graph discussion.
Second, for the extended model since your debunking shows the d=1, N=2 counterexample collapses under rephasing, it feels like Question 4.1 is still wide open. Do you lean towards the degree always being preservable under factorization (modulo phase), or do you suspect there’s some more pathological construction where the garbage register hides a true degree blow-up?
4. For the Hermite Transform paper, I found the ideas in your paper, particularly the QHT–QHO connection and the Gaussian Goldreich–Levin adaptation very intriguing, but while reading I noticed several points where I’m unsure the derivations hold as stated and would like clarification.
Why do you sometimes use e^{-x^2/2} and other times e^{-x^2} in the derivations? I can’t tell which Hermite convention you’re using overall, and I don’t see how Propositions 7 and 9 stay correct if the weight changes.
In the definition of κ, how does a Boolean function end up giving κ = 1? When I try to compute it from your formula, I get something else entirely.
For Proposition 15, I don’t follow how the tail bound scales like e^{-nL^2/4}. If I just apply a union bound, I get something different in n. Could you walk me through your derivation?
Theorem 18’s convergence rate seems to use an analytic-function bound, but Algorithm 2’s f is piecewise constant. How does that still give exponential convergence?
In the discrete QHO states, why is the normalization 1/√M instead of involving √h?
In Algorithm 1, the prepared state and the measurement probability seem to involve different Gaussian weights. How does that still produce the right coefficients?
For the GGL analysis, how does it still work when γ is infinite for sign functions?
Finally, for Lemma 35, where does the exponential decay for sgn(x) come from? My quick calculation for k=1 seems to already break that bound.
Could you explain these points? I feel like I’m missing the connecting logic in several places.
(i am not the much more famous hank green)
Comment #19 August 9th, 2025 at 12:32 pm
Hank Green #18: That’s a long list of questions! I’ll leave it to the student authors to answer them if they want to.