Circuit complexity of unitary evolutions generated by random GUE Hamiltonians

I will present some applications of random matrix theory and concentration of measure on the unitary group to the problem of circuit complexity in quantum computing. Quantum time evolutions are described by unitary matrices. Circuit complexity of a unitary matrix is the minimal number of "elementary operations" needed to approximate it to given accuracy. A notoriously difficult problem is to provide rigorous lower bounds on complexity of physically relevant evolutions. We use some basic properties of the GUE ensemble to provide such bounds in a specific model of random Hamiltonian evolution. Joint work with M. Oszmaniec and M. Horodecki.