Universal Hamiltonians for Exponentially Long Simulation

Abstract

We construct a Hamiltonian whose dynamics simulate the dynamics of every other Hamiltonian up to exponentially long times in the system size. The Hamiltonian is time-independent, local, one-dimensional, and translation invariant. As a consequence, we show (under plausible computational complexity assumptions) that the circuit complexity of the unitary dynamics under this Hamiltonian grows steadily with time up to an exponential value in system size. This result makes progress on a recent conjecture by Susskind, in the context of the AdS/CFT correspondence, that the time evolution of the thermofield double state of two conformal fields theories with a holographic dual has a circuit complexity increasing linearly in time, up to exponential time.

arXiv comment33 pages, typos and errors in transition rules corrected from v1, more references and acknowledgements added, more comments are welcome!

References in corpus (7)

• Hamiltonian simulation with nearly optimal dependence on all parameters
• Undecidability of the Spectral Gap (short version)
• The power of quantum systems on a line
• Hamiltonian Quantum Cellular Automata in 1D
• Quantum simulators, continuous-time automata, and translationally invariant systems
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• Characterization of universal two-qubit Hamiltonians

Cited by in corpus (2)

• Models of quantum complexity growth
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality