Cayley graphs and complexity geometry

Lin, Henry (0000 0001 2097 5006, Jadwin Hall, Princeton University, Princeton, NJ, 08540, U.S.A.) (0000 0004 0615 529X, Facebook AI Research, Facebook, New York, NY, 10003, U.S.A.)

13 February 2019

Abstract: The basic idea of quantum complexity geometry is to endow the space of unitary matrices with a metric, engineered to make complex operators far from the identity, and simple operators near. By restricting our attention to a finite subgroup of the unitary group, we observe that this idea can be made rigorous: the complexity geometry becomes what is known as a Cayley graph. This connection allows us to translate results from the geometrical group theory literature into statements about complexity. For example, the notion of δ-hyperbolicity makes precise the idea that complexity geometry is negatively curved. We report an exact (in the large N limit) computation of the average complexity as a function of time in a random circuit model.

Published in: JHEP 1902 (2019) 063
Published by: Springer/SISSA
DOI: 10.1007/JHEP02(2019)063
arXiv: 1808.06620
License: CC-BY-4.0

Back to search

Download fulltextXML Download fulltextPDF (PDFA)