Computer science Ph.D. student Joseph Carolan developed a new technique for analyzing oracle problems, answering an open question about the quantum security of a key cryptographic method and creating a framework for studying future quantum algorithms.
As the best quantum computers accumulate more qubits and even more hype, computer scientists are still mapping the capabilities and limitations of these new machines.
Since the 1990s, researchers have known that, with enough qubits, quantum computers can quickly break down thousand-digit numbers into their prime factors, threatening some of the most widely used encryption protocols on the internet. In the meantime, among other advances, researchers have also shown that quantum computers can efficiently simulate quantum physics itself, potentially creating promising new opportunities for progress in materials science, chemistry, particle physics and a variety of other fields.
But despite all the progress, proving what these machines can and can’t do is often a painstaking mathematical exercise. Researchers typically start with an idealized model of a computer and a problem of interest, then ask how many resources an algorithm would need to solve it, often considering practical resources like time or memory.
A common way to simplify this analysis is to replace all the messy details of a computation with an all-knowing oracle. In this model of computation, fancifully dubbed the oracle model, all an algorithm can do is pose questions to the oracle and receive answers. If your problem is to find a chest full of treasure among a sea of empty duplicates, the oracle model would let you query one chest at a time, learning at each step whether the queried chest contained the treasure. In the oracle model, the only resource that counts is the number of queries you need to make to find the treasure.
Joseph Carolan, a Ph.D. student in the Joint Center for Quantum Information and Computer Science (QuICS), has developed a new technique for analyzing a family of oracle problems that had remained stubbornly unresolved for more than a decade. In a 70-page paper accepted at the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), one of the most selective conferences in computer science, Carolan used the oracle model to answer an open question about the quantum security of an important method in cryptography and described a new framework for analyzing other quantum algorithms in the future. He will deliver a talk on the new results at STOC 2026 during the week of June 22–27, 2026. Earlier this year, he presented the research in one of just seven short plenary talks in a full program of more than 130 accepted talks at the 29th Annual Quantum Information Processing Conference.
Original Article: https://quics.umd.edu/about/news/quantum-security-proof-earns-phd-student-top-conference-acceptance