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.
“Joe has done great work in many different areas since coming to UMD, but he has especially become an expert in quantum cryptography,” says QuICS Fellow Andrew Childs, a professor of computer science at UMD and Carolan’s academic adviser. “His work in that area has received a lot of attention and is really pushing the field forward.”
Carolan’s new result is specifically about permutations, the mathematical process of taking a group of objects and arranging them in a new order. Familiar examples of permutations include alphabetizing a list of words or shuffling a deck of cards. A permutation maps each element of a set into another, just as shuffling a deck of cards can send the card on top to the 37th spot, the next card to the 14th spot and so forth.
Importantly, a permutation can be undone, which means it has an inverse. This makes permutations useful for studying cryptography. In broad strokes, encryption scrambles a message in a way that can be reversed by someone with the right key. Similarly, a deck of cards could be unshuffled if you happened to keep track of all the positions of the cards before and after the shuffle. Permutations capture encryption and decryption in idealized mathematical form: They jumble everything up, but they do so without throwing away the information needed to recover the original. Encryption looks like a random permutation to everyone who doesn’t know how the jumbling was done.
Carolan, who graduated from the University of Illinois in 2022 with degrees in physics and computer science, didn’t arrive at QuICS expecting to work on permutation problems. Instead, a chat with a visiting researcher sitting in the office next door diverted his attention. “I got completely nerd-sniped by this area,” he says.
Because of the connection between permutations and cryptography, computer scientists have long studied the security of different cryptosystems through the lens of random permutations. They imagine that an oracle implements a particular permutation, representing a particular encryption scheme. If someone (like a nefarious attacker) were to learn which permutation the oracle is using, they would be able to crack the encryption.
To prove the security of an encryption scheme against an attacker in this setting, researchers must show that it’s not feasible to distinguish the permutation that the oracle implements from a random one—at least not without making an enormous number of queries to the oracle.
This has been a fruitful approach for studying cryptographic security in the context of classical algorithms, where the attacker only has the computational capabilities of an ordinary computer. But when it comes to quantum algorithms, where the attacker has a quantum computer, the same approach hit a dead end.
Carolan learned about the well-trod methods that computer scientists had used to study quantum algorithms in a closely related setting—one that describes not random permutations but instead random functions. In this model, the oracle implements a specific random function, so any query seems to return a totally random answer. Intuitively, this might not sound like an especially useful thing to consider, but it allowed computer scientists to prove many results about hash functions, which are widely used for digital signatures of computer files and documents.
Early attempts to follow the same logic for random permutations immediately ran into a crucial difference between functions and permutations: In general, random functions can’t be undone.
For a particular random function, a given input could have any output, and there is no relationship between the outputs for different inputs. Indeed, every input could conceivably give the same output, which would make the function impossible to invert. Permutations, on the other hand, have more stringent constraints. If a permutation maps some input to some output, no other input can yield the same value. This constraint has an outsized effect on how difficult it is to analyze the complexity of permutation problems.
That difficulty was standing in the way of resolving a longstanding open problem about a classic cryptographic procedure called the Feistel construction. Feistel provides a way to build a pseudorandom permutation from simpler pieces. It takes a string of bits, splits it in half, and then mixes the two halves together several times by applying a sequence of randomly chosen functions. Although it may seem like this would produce a random output, the result is actually a pseudorandom permutation that is much easier to specify than a truly random one. For practical reasons, the Feistel method has been a favorite of cryptographers since the 1970s.
The open question that Carolan resolved, first posed in 2012 by Mark Zhandry, a computer scientist at Stanford University, was whether the Feistel construction could be distinguished from a truly random permutation. Could a quantum attacker tell that the Feistel procedure was only imitating true randomness?
Carolan was finally able to answer the question by showing that seven rounds of Feistel are secure against a quantum attacker—meaning that, to distinguish seven-round Feistel from a truly random permutation, such an adversary would need to make a number of queries that grows exponentially with the length of the bit strings. This would be impractical for the attacker, so the safety of seven-round Feistel is assured even if quantum computers were widely available.
The core innovation in Carolan’s proof was to recast the oracle in an equivalent form that allowed him to keep track of how much the attacker learned from each query. He dubbed this tool the compressed permutation oracle, which borrows its name from the compressed oracles that Zhandry had previously introduced to do a similar kind of bookkeeping for oracles implementing random functions. The “compressed” part refers to the way that the records of queries get squeezed into a database that faithfully represents the knowledge of an attacker.
Extending the approach from random functions to permutations proved to be the biggest challenge. Because permutations need to be invertible, the database couldn’t be constructed in the same way and required new mathematical machinery. Ultimately, it took Carolan nearly 50 pages to define a compressed permutation oracle and prove that no efficient quantum algorithm can distinguish it from a truly random permutation.
In addition to resolving the open question about the Feistel construction, Carolan also applied the same framework to several other problems that had already been solved to demonstrate the broader impact of his framework. He hopes his new approach will have much wider applications.
“My hope is that problems that involve invertibility, sort of natively—this tool can be used for [them] even if they don't directly talk about permutations,” Carolan says. “The original compressed oracle went on to prove all these other things that you wouldn't expect it to. So I'm kind of hopeful that will happen with this, but who knows?”
—Story by Chris Cesare, Joint Quantum Institute communications group