Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
arXiv:2305.14252 · doi:10.22331/q-2024-01-18-1230
Abstract
This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM). We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM. Moreover, we introduce (conditional) Kolmogorov complexity of quantum states and use it to study three particular aspects of the algorithmic information contained in a quantum state: a comparison of the information in a quantum state with that of its classical representation as an array of real numbers, an exploration of the limits of quantum state copying in the context of algorithmic complexity, and study of the complexity of correlations in quantum systems, resulting in a correlation-aware definition for algorithmic mutual information that satisfies symmetry of information property.
arXiv comment29 pages, 2 figures
References in corpus (15)
- Quantum entanglement
- Quantum cryptography: Public key distribution and coin tossing
- The classical-quantum boundary for correlations: discord and related measures
- Quantum Kolmogorov Complexity
- Quantum Kolmogorov Complexity Based on Classical Descriptions
- Quantum Algorithmic Entropy
- Algorithmic complexity and entanglement of quantum states
- Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
- Lower bound on the relative error of mixed-state cloning and related operations
- Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
- On Halting Process of Quantum Turing Machine
- The Halting Problem for Quantum Computers
- Quantum Kolmogorov Complexity and the Quantum Turing Machine
- Quantum Kolmogorov Complexity and Quantum Key Distribution
- Quantum Kolmogorov Complexity and Information-Disturbance Theorem