Abstract
An approximate unitary t-design is a distribution of unitaries that mimic properties of the Haar measure for polynomials (in the entries of the unitaries) of degree up to t. It has been a conjecture in the theory of quantum pseudo-randomness that polynomial sized random quantum circuits form an approximate unitary poly(n)-design. Unfortunately, up to now, the best result known is that polynomial random quantum circuits are unitary 3-designs. In this talk I will discuss recent work that settles the conjecture, showing that poly(n) random circuits are indeed approximate unitary poly(n)-designs. The proof, which will be briefly outlined, is based on an interplay of techniques from quantum many-body theory, the theory of Markov chains, and representation theory of the symmetric group.
I will discuss two applications of the result, one concerned with hiding data from a computationally bounded adversary, and another with linking the time of equilibration of local quantum systems to the diagonalisation complexity of the system Hamiltonian.