Description

In recent years, there has been an explosion of exciting work using ideas from the theory of quantum information and computation to study and understand open questions in areas of physics like high energy theory (holography and quantum gravity in particular) and condensed matter theory (topological phases of matter in particular). The exploration of ideas at the forefront of quantum gravity research using quantum information tools has been particularly fruitful, with many

conjectures having been made about what the theory of computation can tell us about a possible fundamental theory of nature. In this work, we explore broad connections between the Hamiltonian Quantum Cellular Automaton model of quantum computation, classical and quantum complexity theory, and a recent conjecture by Susskind which asserts notions of computational complexity as being fundamental in understanding certain aspects of the AdS/CFT correspondence used in string theory and quantum gravity.