Complexity and Time
arXiv:1911.06178 · doi:10.1103/PhysRevD.101.065016
Abstract
For any quantum algorithm given by a path in the space of unitary operators we define the computational complexity as the typical computational time associated with the path. This time is defined using a quantum time estimator associated with the path. This quantum time estimator is fully characterized by the Lyapunov generator of the path and the corresponding quantum Fisher information. The computational metric associated with this definition of computational complexity leads to a natural characterization of cost factors on the Lie algebra generators. Operator complexity growth in time is analyzed from this perspective leading to a simple characterization of Lyapunov exponent in case of chaotic Hamiltonians. The connection between complexity and entropy is expressed using the relation between quantum Fisher information about quantum time estimation and von Neumann entropy. This relation suggest a natural bound on computational complexity that generalizes the standard time energy quantum uncertainty. The connection between Lyapunov and modular Hamiltonian is briefly discussed. In the case of theories with holographic duals and for those reduced density matrix defined by tracing over a bounded region of the bulk, quantum estimation theory is crucial to estimate quantum mechanically the geometry of the tracing region. It is suggested that the corresponding quantum Fisher information associated with this estimation problem is at the root of the holographic bulk geometry.
arXiv comment7 pages
References in corpus (36)
- Quantum Mechanics helps in searching for a needle in a haystack
- Chaos and Quantum Thermalization
- A bound on chaos
- Towards a derivation of holographic entanglement entropy
- Cool horizons for entangled black holes
- Complexity Equals Action
- Complexity and Shock Wave Geometries
- Stabilizer Codes and Quantum Error Correction
- Generalized uncertainty relations: Theory, examples, and Lorentz invariance
- Complexity, action, and black holes
- Quantum Computation as Geometry
- The approach to thermal equilibrium in quantized chaotic systems
- Circuit complexity in quantum field theory
- Towards Complexity for Quantum Field Theory States
- A Universal Operator Growth Hypothesis
- Liouville Action as Path-Integral Complexity: From Continuous Tensor Networks to AdS/CFT
- Anti-de Sitter Space from Optimization of Path Integrals in Conformal Field Theories
- Circuit Complexity in Fermionic Field Theory
- Quantum Computation as Gravity
- Circuit complexity for free fermions
- Operator growth in the SYK model
- Surface/State Correspondence as a Generalized Holography
- On The Evolution Of Operator Complexity Beyond Scrambling
- Gravity Dual of Quantum Information Metric
- Quantum Complexity and Negative Curvature
- Introduction to quantum Fisher information
- Classical and Quantum Fisher Information in the Geometrical Formulation of Quantum Mechanics
- Quantum Epidemiology: Operator Growth, Thermal Effects, and SYK
- Black holes, complexity and quantum chaos
- Quantum Complexity of Time Evolution with Chaotic Hamiltonians
- Canonical Energy is Quantum Fisher Information
- Uncertainty Relation Revisited from Quantum Estimation Theory
- Connecting Fisher information to bulk entanglement in holography
- Entanglement Wedges from Information Metric in Conformal Field Theories
- From Geometry to Quantum Computation
- A Comment on Fisher Information and Quantum Algorithms