Henry Yuen

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using $\Theta(\log \log n)$-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of \emph{constant-time} quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class $\mathsf{QAC^0}$. Finally, our results suggest a new approach towards proving that PARITY is not computable in $\mathsf{QAC^0}$, a long-standing question in quantum complexity theory.

Uhlmann’s theorem is a fundamental result in quantum information theory that quantifies the optimal overlap between two bipartite pure states after applying local unitary operations (called Uhlmann transformations). We show that optimal Uhlmann transformations are rigid – in other words, they must be unique up to some well-characterized degrees of freedom. This rigidity is also robust: Uhlmann transformations achieving near-optimal overlaps must be close to the unique optimal transformation (again, up to well-characterized degrees of freedom). We describe two applications of our robust rigidity theorem: (a) we obtain better interactive proofs for synthesizing Uhlmann transformations and (b) we obtain a simple, alternative proof of the Gowers-Hatami theorem on the stability of approximate representations of finite groups.

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that ``look'' sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: t-designs are random unitaries that information-theoretically reproduce the first t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.In this work, we take a unified approach to constructing t-designs and PRUs. For this, we introduce and analyse the ``PFC ensemble'', the product of a computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the PFC ensemble to show the following:-Linear-depth t-designs. We give the first construction of a (diamond-error) approximate t-design with circuit depth linear in t. This follows from the PFC ensemble by replacing the random phase and permutation operators with their 2t-wise independent counterparts. - Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the PFC ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. - Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from n to n + \omega(log n) qubits, a small modification of our PRU construction achieves adaptive security, i.e.~even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Abstract Boris Tsirelson in 1993 implicitly posed "Tsirelson's Problem", a question about the possible equivalence between two different ways of modeling locality, and hence entanglement, in quantum mechanics. Tsirelson's Problem gained prominence through work of Fritz, Navascues et al., and Ozawa a decade ago that establishes its equivalence to the famous "Connes' Embedding Problem" in the theory of von Neumann algebras. Recently we gave a negative answer to Tsirelson's Problem and Connes' Embedding Problem by proving a seemingly stronger result in quantum complexity theory. This result is summarized in the equation MIP* = RE between two complexity classes. In the talk I will present and motivate Tsirelson's problem, and outline its connection to Connes' Embedding Problem. I will then explain the connection to quantum complexity theory and show how ideas developed in the past two decades in the study of classical and quantum interactive proof systems led to the characterization (which I will explain) MIP* = RE and the negative resolution of Tsirelson's Problem. Based on joint work with Ji, Natarajan, Wright and Yuen available at arXiv:2001.04383.

Abstract We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography. To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) proof system for the complexity class QMA. Our protocol has the so-called S format with a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK S-protocol for QMA is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.