Compressed Oracles and Coherent Workshops | Theory at the Institute and Beyond

by Nikhil Srivastava (senior scientist, Simons Institute for the Theory of Computing)

Let me start with a confession. For many years, I was afraid of quantum and crypto. Quantum scared me because I didn’t know how to think about tensor products, and crypto because I couldn’t keep track of the quantifiers involved in interactive protocols. I am still scared by one of those things.

Yet, I can’t resist telling you about the compressed oracle method (and its generalization, the path-recording oracle), a beautiful linear algebraic technique that led to fundamental discoveries in quantum cryptography and complexity over the past year and a half, apparently right outside my office in Calvin Lab.

The Quest for Pseudorandom Unitaries
To set the stage, recall that a (cryptographic) pseudorandom permutation (PRP) is a polynomial-time computable random permutation on \(\{0,1\}^n\) that cannot be distinguished from a uniformly random permutation by any \(poly(n)\) time algorithm given black-box query access to it. PRPs are known to exist under standard cryptographic assumptions and are a foundational object in classical cryptography.

The quantum analogue of PRPs is pseudorandom unitaries (PRUs), first defined by Ji, Liu, and Song in 2017. A pseudorandom unitary is an efficiently computable \(2^n \times 2^n\) unitary matrix that is indistinguishable from a uniformly (Haar) random unitary by any \(poly(n)\) time quantum algorithm, which we will refer to as an adversary. Besides being a natural object in quantum cryptography, PRUs were of interest to physicists, who use them to model black holes, among other things.

The question of the existence of PRUs captivated the quantum community, including at the Simons Institute, where many talks were given about it over the past few years. The first constructions of PRUs that could fool nonadaptive adversaries were given in early 2024, in two independent breakthrough works by Metger-Poremba-Sinha-Yuen and by Chen-Bouland-Brandão-Docter-Hayden-Xu. Nonadaptive adversaries are mathematically nice because the output of a \(t=poly(n)\) time distinguishing algorithm \(Alg\) given black box access to a unitary \(U\), which we will denote \(|Alg^U⟩\), is linear in the tensor power \(U^{\otimes t}\), and the problem boils down to showing closeness of (the covariance matrices of) these tensor powers of the random and pseudorandom unitaries in an appropriate norm. This is still difficult, but it can be approached using the framework of representation theory and random matrix theory.

Interestingly, both papers found (different) ways to reduce PRUs to PRPs. Metger et al. introduced a particularly simple construction based on representation theory called the “PFC ensemble,” which they conjectured could actually fool adaptive adversaries. Chen et al. developed a new approach in the spirit of random matrix theory, which as I pointed out in an earlier newsletter had a huge impact on random matrix theory itself.

Yet, the question of full PRUs that could fool adaptive adversaries remained mysterious.

Hidden Symmetries, and a Crash Course in Tensor Products
Enter the compressed oracle method, invented in 2018 by Mark Zhandry. In the classical world, you can analyze the interaction between an adversary and a random function \(f:\{0,1\}^n\rightarrow \{-1,1\}\) given as a black box — called a random oracle — by lazy evaluation: basically, you sample the bits of the oracle on the fly depending on the adversary’s queries and store past answers, yielding a succinct “stateful” description of the oracle that is useful in proofs. But this idea doesn’t work in the quantum world, because the adversary can query the oracle in superposition — mathematically, the oracle is a random \(\pm 1\) diagonal unitary matrix \(U\), and a single query means preparing a quantum state \(\sum_{x\in \{0,1\}^n} \alpha_x U|x⟩\), which can depend on all the values of \(U(x)\).

Zhandry’s beautiful insight was that it is nonetheless possible to “quantize” the lazy evaluation argument by exploiting three facts about the way measurement works in quantum mechanics. If you have not yet crossed the tensor product barrier, checking these facts for yourself is a good way to take the first step, and if you get nothing else out of this article, it will be worth it.

Observe that if \(U\) is a (discrete, for technical convenience) random variable with probability distribution \(p(U)\), then one can encode the behavior of an adversary on the entire distribution of \(U\) at once by considering the “purified” state

\(|\psi⟩:=\sum\limits_U \sqrt{p(U}) |Alg^U⟩|U⟩\),

where \(|a⟩|b⟩\) is the bra-ket notation for the tensor product \(a\otimes b\) of two vectors. If that seems unfamiliar, this is a good moment to study the definition of the tensor product of two vector spaces.

Fact 1. The covariance matrix

\(\mathbb{E}_{U\sim p(U)}|Alg^U ⟩ ⟨ Alg^U|\)

(which is the thing we care about in the PRU problem and in quantum query complexity) is equal to the reduced density matrix

\(\rho_{Alg} := Tr_2(|\psi⟩⟨\psi|)\)

on the first tensor factor, where \(Tr_2\) denotes the partial trace on the second tensor factor. This is the quantum analogue of taking a marginal probability distribution.

Fact 2. The reduced density matrix \(\rho_{Alg}\) is invariant under applying a unitary transformation of type \(I\otimes T\) to \(|\psi⟩\), i.e.,

\(\rho_{Alg} = Tr_2( I\otimes T (|\psi⟩⟨\psi|) I\otimes T^\dagger)\)

for all unitary \(T\). Here \(I \otimes T\) denotes the tensor product of two operators.

Fact 3. The tensor product is bilinear, in particular \((\alpha a)\otimes b = a\otimes (\alpha b)\) for a scalar alpha.

Conceptually, what this is saying is that there is a different description of the covariance matrix \(\rho_{Alg}\) in an enlarged space, which admits many more symmetries than the original description, in the form of Fact 2. The punch line is that by choosing \(T\) to be the Fourier transform — a certain symmetry of the uniform distribution on diagonal \(U\) — one obtains an alternate, succinct combinatorial description of the \(U\) oracle. This is the “compressed oracle,” which may be viewed as an efficient data structure that exactly simulates a random diagonal \(U\) to an efficient adversary. Though the proof is short, it seems magical to me that a mathematical duality (of the Fourier transform) yields a computational duality (of efficiency in the adversary and in the oracle), essentially by using Fact 3 to “push” the behavior of the adversary onto the oracle.

In October 2024, Fermi Ma and Hsin-Yuan Huang fully solved the problem of the existence of PRUs by showing that the PFC ensemble is in fact secure against adaptive adversaries assuming the existence of one-way functions, as Metger et al. had conjectured. Their striking insight was that the compressed oracle method can be generalized to the case of Haar random \(U\) (i.e., not diagonal) if one allows a small error — a generalization they named the “path-recording oracle.” This is surprising since the unitary group is highly noncommutative and does not admit nearly as nice a “Fourier transform.”

Unlike Zhandry, they did not particularly care about the succinctness or efficiency of this oracle viewed as a data structure. What was really important was the symmetries satisfied by the path-recording oracle — in particular, that it exactly simulates the uniform distribution on random signed \(2^n \times 2^n\) permutations, for a large subclass of adversaries known as the “distinct subspace,” which also played a role in the work of Metger et al. By exploiting a higher-order analogue of Fact 3, they upgraded this to the following dramatic conclusion:

The path-recording oracle approximately simulates every “mildly symmetric” distribution \(U\) against all adversaries.

Since both the PFC ensemble and the Haar unitary satisfy the required mild symmetries, they concluded that they must both be close to the path-recording oracle and therefore to each other in the appropriate sense, solving the problem. It is hard to imagine a more elegant proof than theirs. It is all identities, save for a single inequality which amounts to showing that a Euclidean projection cannot increase the norm of a vector. And yet, the motivation for this crisp linear algebraic proof came from considerations that are emblematic of theoretical computer science: simulation, interaction, efficiency, and approximation.

One-Day Workshops and Other Experiments
There is another curious feature of this story. Almost all the people I cited were affiliated in one way or another with the Simons Institute’s Quantum Pod or one of its thematic programs. While all this was going on, pod director Umesh Vazirani was experimenting with new ways of gathering people to catalyze progress. A particularly fruitful idea was “one-day workshops,” which have now become a regular feature of quantum activity at the Institute.

A one-day workshop consists of three to four talks focused on a single high-momentum research question or direction. The speakers are experts who have made progress on the question or surrounding topics and can teach what they know about it. The relatively small audience consists of interested program participants already at the Institute and a few carefully chosen visitors who might spark new connections. Participants then stick around for a few days to work on the problem.

The collaboration of Ma and Huang began at one of the first such workshops, in March 2024. The schedule juxtaposed a talk by Henry Yuen about the nonadaptive PFC construction and a talk by Ma that introduced compressed oracle–type ideas in this setting for the first time. Ma and Huang had their breakthrough weeks later. The compressed oracle technique continues to make waves in quantum complexity, with another beautiful result by Ewin Tang and John Wright this summer explaining the necessary conditions for quadratic speedups in quantum algorithms. To act on this momentum, an even more focused one-day workshop on this topic was held this June.

Not all one-day workshops are as successful, but I would like to reflect on the features of this format compared with traditional weeklong workshops. One is intellectual coherence. It is easier and more relaxing to make scientific and social connections if everyone is thinking about the same thing. I wonder whether this is neurologically similar to the vibe of a good concert or wedding, where everyone’s spins are aligned. Another is the trust that comes with a smaller group, which seems to allow people to share their ideas more freely without the fear of being scooped anonymously. And last is the relative ease of organizing a one-day event, especially one embedded in an Institute program, which allows the workshops to respond to a fast-moving research topic.

We continue to experiment with different formats at the Institute. Another device, which will feature prominently in this fall’s Complexity and Linear Algebra program, is to embed one or more working afternoons in a weeklong workshop. These can be AIM-style problem-solving sessions or tutorials in which people solve exercises together, as was beautifully done in the recent Simons Institute-SLMath joint workshop on AI and math. A bit of structure from the organizers goes a long way. Again, the idea is to create a container in which there is scientific coherence, making it easier for participants to interact adaptively rather than nonadaptively.

I encourage you to submit a semester or workshop proposal and try such experiments for yourself.

Many thanks to Fermi Ma and Umesh Vazirani for generous discussions, and to Henry Yuen for helpful feedback on a draft of this article.