Understanding Why Quantum Proofs Can Be More Powerful Than Classical Ones

What makes a quantum proof more powerful than a classical one? A paper by John Bostanci (PhD ‘26) and his collaborators explores that question by showing, providing the strongest evidence that there is a difference between the power of quantum and classical proofs in a theoretical setting. The research was presented at the 58th ACM Symposium on Theory of Computing (STOC 2026) and received a Best Paper Award.

Their paper, “Separating QMA from QCMA with a Classical Oracle,” presents the first classical oracle separation between QMA, where a quantum computer can use a quantum proof, and QCMA, where the proof is classical. The work shows that there are problems that can be solved using a particular quantum state but cannot be solved by any classical proof.

The result builds on a fundamental feature of quantum mechanics known as the no-cloning principle: an unknown quantum state cannot simply be copied. While that may sound like a limitation, the researchers show that this property can actually make quantum states useful as proofs. Their work provides new ways to understand how quantum information can be both useful and un-clonable.

We spoke with Bostanci, who is now a postdoctoral fellow at the Simons Institute, about the problem behind the research, the new techniques the team developed, and what the findings could eventually mean for technologies such as quantum money and quantum cryptography.

Q: What did you set out to understand, and why is the idea of un-clonable quantum states important?
The main challenge we had to overcome was that before this work, we had basically no idea how to differentiate between a classical and quantum proofs in complexity theory. We are trying to build a mathematical framework for understanding how quantum states can be both useful and un-clonable. I want to use the un-clonability of quantum states to eventually build quantum money (that is, physical money that we both verify as legitimate, but also prove could not be cloned, because they contain quantum states), and verify quantum computation.

Our work builds a much better understanding of how un-clonability can appear in a problem, and provides tools for proving that certain families of quantum states are un-clonable.

Q: What was new about your approach? How did your work differ from previous attempts to understand QMA and QCMA?
Our work invents a lot of techniques that did not appear in prior work. For one thing, past work on the QMA versus QCMA problem did not approach the problem directly using un-clonability as a proof technique. In addition, our work takes a lot of inspiration from physics. We take a lot of inspiration from the study of bosons (particles like photons that are allowed to occupy the same “mode”), and use a lot of intuition from early quantum mechanics about the interplay between positions and momentum of those kinds of particles.

Q: Where could these ideas eventually have an impact outside of theoretical computer science?
To me, the main application is towards constructing quantum money, lightning, and one-shot signatures from a standard cryptographic assumption. These can help speed up blockchains, potentially help prevent counterfeiting, and be used to verify quantum computation on classical computers, which I think will be important to potentially running quantum computers on the cloud.

Q: What excites you most about this result?
I think ideas like quantum money, which can only exist in a quantum world, are some of the most promising applications of quantum technologies. I think that in order to get those applications working in the real world, we have a long way to go in understanding the basics of quantum computation, and this problem was a major bottleneck in our understanding of un-clonability.