Quantum information

Computational complexity theory

Quantum complexity theory

Quantum

Physics

Black hole (networking)

Link-state routing protocol

Quantum entanglement

Mathematics

Theoretical physics

Quantum mechanics

Quantum state

Scrambling

Computer science

Quantum computer

Algorithm

Routing (electronic design automation)

Theoretical computer science

Routing protocol

Computer network

The European Physical Journal C

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.

Quantum computational complexity from quantum information to black holes and back