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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K. Shizume, T. Nakajima, R. Nakayama and Y. Takahashi, Quantum computational Riemannian and sub-Riemannian geodesics, Prog. Theor. Phys. 127 (2012) 997 [INSPIRE].
A.R. Brown and L. Susskind, Second law of quantum complexity, Phys. Rev. D 97 (2018) 086015 [arXiv:1701.01107] [INSPIRE].
L. Susskind, Lectures on complexity and black holes, to be announced (2018).
D. Stanford and L. Susskind, Complexity and shock wave geometries, Phys. Rev. D 90 (2014) 126007 [arXiv:1406.2678] [INSPIRE].
A.R. Brown et al., Holographic complexity equals bulk action?, Phys. Rev. Lett. 116 (2016) 191301.
A.R. Brown et al., Complexity, action, and black holes, Phys. Rev. D 93 (2016) 086006 [arXiv:1512.04993].
L. Susskind, Computational complexity and black hole horizons, Fortsch. Phys. 64 (2016) 44 [arXiv:1403.5695] [INSPIRE].
A. Kitaev, A simple model of quantum holography, talks given at KITP, U.S.A. (2015).
J. Maldacena and D. Stanford, Remarks on the Sachdev-Ye-Kitaev model, Phys. Rev. D 94 (2016) 106002 [arXiv:1604.07818] [INSPIRE].
A.R. Brown et al., The case of the missing gates: complexity of Jackiw-Teitelboim gravity, arXiv:1810.08741 [INSPIRE].
K. Goto et al., Holographic complexity equals which action?, arXiv:1901.00014 [INSPIRE].
J. Preskill, Lecture notes for physics 229: quantum information and computation, California Institute of Technology, U.S.A. (1998).
A.R. Brown, L. Susskind and Y. Zhao, Quantum complexity and negative curvature, Phys. Rev. D 95 (2017) 045010 [arXiv:1608.02612] [INSPIRE].
P. Diaconis, Random walks on groups: characters and geometry, in Groups St. Andrews 2001 in Oxford, C.M. Campbell ed., Cambridge University Press, Cambridge U.K. (2002).
L. Saloff-Coste, Random walks on finite groups, in Probability on discrete structures, H. Kesten, Springer, Germany (2004).
N. Berestycki and R. Durrett, A phase transition in the random transposition random walk, Prob. Theor. Rel. Fields 136 (2006) 203.
N. Berestycki, The hyperbolic geometry of random transpositions, Ann. Prob. (2006) 429.
W.M. Goh and E. Schmutz, The expected order of a random permutation, Bull. London Math. Soc. 23 (1991) 34.
N. Alon and Y. Roichman, Random Cayley graphs and expanders, Random Struct. Alg. 5 (1994) 271.
A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261.
D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Month. 93 (1986) 333.
L. Saloff-Coste, Random walks on finite groups, in Probability on discrete structures, H. Kesten, Springer, Germany (2004).
D.A. Roberts, D. Stanford and A. Streicher, Operator growth in the SYK model, JHEP 06 (2018) 122 [arXiv:1802.02633].
T. Toffoli, Reversible computing, in the proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), July 14–18, Noordwijkerhout, The Netherlands (1980).
V.V. Shende et al., Synthesis of reversible logic circuits, IEEE T. Comput. Aid. D. 22 (2003) 710.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License (CC-BY 4.0), which permits any use, distribution and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
ArXiv ePrint: 1808.06620
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.
The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
To view a copy of this licence, visit https://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Lin, H.W. Cayley graphs and complexity geometry. J. High Energ. Phys. 2019, 63 (2019). https://doi.org/10.1007/JHEP02(2019)063
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/JHEP02(2019)063