Results 1 - 10 of 24774

Classical computer science offers two powerful ways to construct simple substitutes for ideal randomness: k-wise independent functions, which look random on any k inputs, and pseudorandom functions, which look random to any computationally efficient algorithm. This talk explores how these classical ideas can be used to construct quantum operations that look random.

For quantum operations, the natural benchmark is a Haar random unitary matrix. These matrices play important roles in quantum computation and cryptography and provide models of chaotic physical systems such as black holes. I will introduce the PFC ensemble, which combines random permutations (P) and functions (F) with quantum Clifford (C) operations. It provides a unified approach to constructing unitary designs and pseudorandom unitaries, the quantum counterparts of the two classical notions. I will also highlight a few recent developments and open questions in quantum pseudorandomness. No background in quantum information will be assumed for this talk.

Based in part on joint work with Tony Metger, Alexander Poremba and Henry Yuen.

In a recent breakthrough, Williams (STOC 2025) showed that any decision problem solvable in time $t$ by a multitape Turing machine can be solved in space $\tilde{O}(\sqrt{t})$ and time $2^{\tilde{O}(\sqrt{t})}$. The immediate question is whether this result is an anomaly, or an inherent feature of computation more generally.

In this work we provide evidence that the resource trade-offs phenomenon first demonstrated by Williams is systematic, i.e. inherent to computation in general. Specifically, under a plausible complexity-theoretic hardness assumption, we show that $t$-time algorithms can be simulated in space $t^{\epsilon}$, for any constant $\epsilon>0$, where the simulation is correct on average over a random input. We also show, under similar complexity-theoretic hardness assumptions, that $t$-time algorithms can be simulated in \emph{linear time} using sufficiently many alternations (i.e., $\forall/\exists$ quantifiers), where again the simulation is correct on average over a random input.

Some hardness assumption is necessary to prove these conclusions (as they imply that $\mathsf{P}\ne\mathsf{PSPACE}$), and the specific hardness assumption that we rely on has been extensively studied in complexity theory in recent years: hardness of a computational problem called Range Avoidance. Specifically, we introduce a new ``low-space'' variant of Range Avoidance, and show (under mild derandomization assumptions) that average-case hardness of this problem for polynomial-time algorithms is in fact \emph{equivalent} to low-space simulation of $\mathsf{FP}$, and implies linear-time simulation with alternations. We then study the complexity of this new problem, showing conditional hardness results and algorithms.

Joint work with Roei Tell.