Properties of the (un)complexity of subsystems

2018/07/31 by Henry Stoltenberg
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computer science #Degeneracy (biology) #Density matrix #Exponential function #Generality #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum mechanics #Relation (database) #Scaling #State (computer science) #Statistical physics #Superadditivity #Theoretical computer science #gr-qc #hep-th #quant-ph

paper · pdf · doi:10.1103/physrevd.98.126012

published as Phys. Rev. D 98, 126012 (2018) · 7 pages, 3 figures V2: typos fixed and citations added

arxiv created 2018/10/26 · openalex publication_date 2018/12/27 · arxiv updated 2019/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

I investigate some properties of proposed definitions for subsystem/mixed state complexity and uncomplexity. A very strong dependence arises on the density matrix's degeneracy which gives a large separation in the scaling of maximum subsystem complexity with number of qubits (linear compared to exponential). I also investigate several cases where the uncomplexity of quantum states are superadditive and present some challenges and progress in showing that the relation holds in complete generality.

Citations

• Average entropy of a subsystem
• Complexity and shock wave geometries
• Holographic Derivation of Entanglement Entropy from the anti–de Sitter Space/Conformal Field Theory Correspondence
• Black holes as mirrors: quantum information in random subsystems
• Cool horizons for entangled black holes
• Holographic Complexity Equals Bulk Action?
• Thoughts on holographic complexity and its basis dependence
• The Second Law of Quantum Complexity