Quantum Information

In describing condensed matter, some well established paradigms have allowed much progress to be made in understanding and using materials.  But in the last 15 - 20 years, new materials, such as heavy fermions, high temperature superconductors, and now charge density wave-supporting materials,  have been shown to require new paradigms in describing them.  While much progress has been achieved in that time, we still do not have  a widely accepted theoretical description of the nature of their electronic excitations.

I'll discuss some recent results, motivated by the black-hole firewall paradox and the AdS/CFT correspondence, about the quantum circuit complexity of preparing certain entangled states and implementing certain unitary transformations.  One result is a strengthening of an argument by Harlow and Hayden: I'll show that, under plausible assumptions, "decoding" useful information from Hawking radiation, as called for by the AMPS "firewall" thought experiment, requires the computational power to invert arbitrary cryptographic one-way functions, something we think not even quantum computers could do in sub-astronomical time.  A second result, joint with Lenny Susskind, considers the circuit complexity of the kinds of states that could arise in AdS/CFT, and shows that, under a reasonable conjecture about complexity classes (PSPACE is not in PP/poly), the complexity indeed becomes superpolynomially large, as predicted by a conjectured relationship between complexity and geometry.  I'll also discuss more general open questions about the complexities of states and unitary transformations (and the connections to quantum money, quantum proofs, and other topics), which I find fascinating even apart from the quantum-gravity motivation.