The European Physical Journal C · 2022 · 133 citations · 170 references
Natural SciencesComputer SciencePhysicsMathematical PhysicsQuantum MechanicsTheoretical PhysicsBlack HolesComplexity TheoryComputational ComplexityQuantum ComputationQuantum Information TheoryGaussian StatesHolographic DualityMixed Quantum StatesQuantum Black HolesQuantum Complexity
Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.
170
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Particle creation by black holes
S. W. Hawking · Communications in Mathematical Physics · 1975 · 12.9K citations
Large N field theories, string theory and gravity
Ofer Aharony, Steven S. Gubser, Juan Maldacena et al. · Physics Reports · 2000 · 5.6K citations · Full text