Algorithmic complexity and entanglement of quantum states
arXiv:quant-ph/0505200 · doi:10.1103/PhysRevLett.95.200503
Abstract
We define the algorithmic complexity of a quantum state relative to a given precision parameter, and give upper bounds for various examples of states. We also establish a connection between the entanglement of a quantum state and its algorithmic complexity.
4 pages. Replaced with published version
References in corpus (2)
Cited by in corpus (30)
- Quantum entanglement
- The theory of variational hybrid quantum-classical algorithms
- Are random pure states useful for quantum computation?
- Fundamentals of universality in one-way quantum computation
- Chaos and Complexity of quantum motion
- Trading T gates for dirty qubits in state preparation and unitary synthesis
- Multipartite Entanglement and Global Information
- Quantum Fingerprinting with Coherent States and a Constant Mean Number of Photons
- Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
- Low-rank quantum state preparation
- Renormalization algorithm with graph enhancement
- Compact quantum kernel-based binary classifier
- Thermal entanglement witness for materials with variable local spin lengths
- Quantum Kolmogorov Complexity and the Quantum Turing Machine
- State complexity and quantum computation
- The fastest generation of multipartite entanglement with natural interactions
- Introduction to quantum entanglement in many-body systems
- Algorithmic complexity of quantum capacity
- Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
- Maximal tree size of few-qubit states
- Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
- Entanglement, Complexity, and Causal Asymmetry in Quantum Theories
- Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications
- Quantum entropy and complexity
- Tree-size complexity of multiqubit states
- Monte Carlo Quantum Computing
- Quantum Oracle Separations from Complex but Easily Specified States
- On the Algorithmic Content of Quantum Measurements
- Second Quantized Kolmogorov Complexity
- Classical Hierarchical Correlation Quantification on Tripartite Qubit Mixed State Families