Cayley graphs and complexity geometry
Author:
Open Access
- 12 February 2019
- journal article
- research article
- Published by Springer Nature in Journal of High Energy Physics
- Vol. 2019 (2) , 63
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.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Addendum to computational complexity and black hole horizonsFortschritte der Physik, 2016
- Quantum Computational Riemannian and Sub-Riemannian GeodesicsProgress of Theoretical Physics, 2012
- The hyperbolic geometry of random transpositionsThe Annals of Probability, 2006
- A phase transition in the random transposition random walkProbability Theory and Related Fields, 2005
- Random Walks on Finite Groups2004
- Random walks on groups: characters and geometry2003
- Synthesis of reversible logic circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- Random Cayley graphs and expandersRandom Structures & Algorithms, 1994
- The Expected order of a Random PermutationBulletin of the London Mathematical Society, 1991
- Ramanujan graphsCombinatorica, 1988