arXiv:1101.2946 · Entropy

Quantum Kolmogorov Complexity and Information-Disturbance Theorem

Takayuki Miyadera

Published Mar 29, 2011• 4 citations

Abstract

In this paper, a representation of the information-disturbance theorem based on the quantum Kolmogorov complexity that was defined by P. Vit´anyi has been examined. In the quantum information theory, the information-disturbance relationship, which treats the trade-off relationship between information gain and its caused disturbance, is a fundamental result that is related to Heisenberg’s uncertainty principle. The problem was formulated in a cryptographic setting and the quantitative relationships between complexities have been derived.

DOI: 10.3390/e13040778

Related papers

Information-Disturbance theorem and Uncertainty Relation

Takayuki Miyadera, Hideki Imai

It has been shown that Information-Disturbance theorem can play an important role in security proof of quantum cryptography. The theorem is by itself interesting since it can be regarded as an information theoretic version of uncertainty principle. It, however, has been able to treat restricted situations. In this paper, the restriction on the source is abandoned, and a general information-disturbance theorem is obtained. The theorem relates information gain by Eve with information gain by Bob.

arXiv:0707.4559Jul 31, 20074 citations

Quantum-state disturbance versus information gain: Uncertainty relations for quantum information

Christopher A. Fuchs, Asher Peres

When an observer wants to identify a quantum state, which is known to be one of a given set of nonorthogonal states, the act of observation causes a disturbance to that state. We investigate the trade-off between the information gain and that disturbance. This issue has important applications in quantum cryptography. The optimal detection method, for a given tolerated disturbance, is explicitly found in the case of two equiprobable nonorthogonal pure states. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9512023Physical Review AApr 1, 1996361 citations

Information Gain vs. State Disturbance in Quantum Theory

Christopher A. Fuchs, Christopher A. Fuchs

The engine that powers quantum cryptography is the principle that there are no physical means for gathering information about the identity of a quantum system's state (when it is known to be prepared in one of a set of nonorthogonal states) without disturbing the system in a statistically detectable way. This situation is often mistakenly described as a consequence of the “Heisenberg uncertainty principle.” A more accurate account is that it is a unique feature of quantum phenomena that rests ultimately on the Hilbert space structure of the theory along with the fact that time evolutions for isolated systems are unitary. In this paper we shall explore several aspects of the information-disturbance principle in an attempt to make it firmly quantitative and flesh out its significance for quantum theory as a whole.

Fortschritte der PhysikJun 1, 1998109 citations

Information Gain vs. State Disturbance in Quantum Theory

Christopher A. Fuchs

The engine that powers quantum cryptography is the principle that there are no physical means for gathering information about the identity of a quantum system's state (when it is known to be prepared in one of a set of nonorthogonal states) without disturbing the system in a statistically detectable way. This situation is often mistakenly described as a consequence of the ``Heisenberg uncertainty principle.'' A more accurate account is that it is a unique feature of quantum phenomena that rests ultimately on the Hilbert space structure of the theory along with the fact that time evolutions for isolated systems are unitary. In this paper we shall explore several aspects of the information--disturbance principle in an attempt to make it firmly quantitative and flesh out its significance for quantum theory as a whole.

arXiv:quant-ph/9611010Nov 7, 19962 citations

Quantum Kolmogorov Complexity: Compression Limits and the Information-Disturbance Trade-Off — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Kolmogorov complexity defines randomness via shortest program length; quantum extension reveals an information-disturbance trade-off, linking compression limits to measurement-induced entropy. | MATH: K(s) = min{|p| : U(p) = s} (invariance up to additive constant); quantum version K_Q(ρ) ≈ min{|p| : U(p) ≈ ρ} with trace distance; information-disturbance bound: I(A:B) + D(ρ, ρ') ≥ f(K_Q(ρ)) — trade-off between extracted info and state perturbation, formalized via mutual information and fidelity. | CONNECTION: The trade-off constant in optimal quantum compression often involves log₂(1/φ) ≈ 0.694 (where φ = 1.618) — appears in entropy bounds for qubit ensembles; the additive constant in Kolmogorov invariance is bounded by O(log n), echoing base-2 vs base-e entropy ratios (ln2 ≈ 0.693), which is the same numerical neighborhood as the golden-ratio-derived 0.694 — a non-trivial resonance between algorithmic information and geometric harmony. | DEPTH: 7 — The classical result is foun Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

Aug 28, 20260 citations

Quantum-Enhanced Kolmogorov Complexity Theory

Jincheng Zhang

This paper investigates the potential impact of quantum mechanics on Kolmogorov complexity, a fundamental concept in information theory. The core claim is that quantum phenomena, specifically entanglement and superposition, introduce limitations to the compression achievable through Kolmogorov complexity that are absent in the classical framework. We demonstrate through theoretical analysis that certain datasets exhibit compression ratios exceeding those attainable by classical methods, leveraging the unique properties of quantum states. This extends Kolmogorov complexity by incorporating quantum principles, offering a novel perspective on the nature of information and its quantification. The theoretical framework presented here highlights potential discrepancies between classical and quantum notions of information and sets the stage for future research exploring the implications of quantum mechanics for fundamental information theory. We present a novel approach to defining Kolmogorov complexity within a quantum context, focusing on the measurement problem and its effect on the ability to uniquely determine a string. This work doesn't present experimental results; it is a purely theoretical exploration.

Sep 3, 20260 citations