Quantum Kolmogorov Complexity and Its Applications
Caterina Mora2007, International Journal of Quantum Information
Sign up for access to the world's latest research
checkGet notified about relevant papers
checkSave papers to use in your research
checkJoin the discussion with peers
checkTrack your impact
Abstract
Kolmogorov complexity is a measure of the information contained in a binary string. We investigate here the notion of quantum Kolmogorov complexity, a measure of the information required to describe a quantum state. We show that for any definition of quantum Kolmogorov complexity measuring the number of classical bits required to describe a pure quantum state, there exists a pure n-qubit state which requires exponentially many bits of description. This is shown by relating the classical communication complexity to the quantum Kolmogorov complexity. Furthermore we give some examples of how quantum Kolmogorov complexity can be applied to prove results in different fields, such as quantum computation and thermodynamics, and we generalize it to the case of mixed quantum states.
Related papers
Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem
Communications in Mathematical Physics, 2006
In classical information theory, entropy rate and algorithmic complexity per symbol are related by a theorem of Brudno. In this paper, we prove a quantum version of this theorem, connecting the von Neumann entropy rate and two notions of quantum Kolmogorov complexity, both based on the shortest qubit descriptions of qubit strings that, run by a universal quantum Turing machine, reproduce them as outputs.
Algorithmic Complexity and Entanglement of Quantum States
Physical Review Letters, 2005
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.
Quantum Kolmogorov complexity and duality of unitary transformations and quantum states
2021
The Kolmogorov complexity of a quantum state is known as quantum Kolmogorov complexity. For every unitary transformation, we construct a corresponding quantum state. Then, we define the Kolmogorov complexity of the unitary transformation via the Kolmogorov complexity of the constructed quantum state and show the consistency of such an approach. Thus, we establish the duality of unitary evolutions and quantum states in quantum computing and quantum mechanics.
Quantum State Complexity Measure
2011
The complexity measures role has become much clearer in recent years as they help to better understand complex systems dynamical behavior. Even though the large number of measures proposed to tackle this issue for classical systems, for quantum systems only Kolmogorov's algorithm complexity extensions have been proposed. Hence, the present approach makes use of a new and mathematically well-established complexity measure for classical systems and extends it to assess quantum states complexity as well. Then the proposed extension is applied to a mixed state constructed with a W-state together with controlled white noise, showing a convex behavior of quantum state complexity. Thus, this reinforces the differences from previous known quantum complexities.
Towards quantifying complexity with quantum mechanics
The European Physical Journal Plus, 2014
While we have intuitive notions of structure and complexity, the formalization of this intuition is non-trivial. The statistical complexity is a popular candidate. It is based on the idea that the complexity of a process can be quantified by the complexity of its simplest mathematical model -the model that requires the least past information for optimal future prediction. Here we review how such models, known as -machines can be further simplified through quantum logic, and explore the resulting consequences for understanding complexity. In particular, we propose a new measure of complexity based on quantum -machines. We apply this to a simple system undergoing constant thermalization. The resulting quantum measure of complexity aligns more closely with our intuition of how complexity should behave.
Algorithmic Randomness and Kolmogorov Complexity for Qubits
arXiv (Cornell University), 2021
Quantum Communication Complexity Protocols Based on Higher-Dimensional Entangled Systems
International Journal of Quantum Information, 2003
We introduce new communication complexity problems whose quantum solution exploits entanglement between higher-dimensional systems. We show that the quantum solution is more efficient than the broad class of classical ones. The difference between the efficiencies for the quantum and classical protocols grows with the dimensionality of the entangled systems.
Lower bounds on information complexity via zero-communication protocols and applications
53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), 2012
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ 2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound.
Entanglement and Complexity of Measurement
Journal of physics, 2013
Notion about complexity of composite systems is applied to the problem of measurement of quantum states. An expression for the determination of the value of complexity of measurement is given. Its practical meaning is illustrated in the example how this value differs when measuring complexity of authorized and non-authorized receiving of information transferred by quantum channels in protocol of direct coding. Unconditional security of information in direct coding protocol with information masking by uniformly distributed state of carrier is shown.
Lower bounds on information complexity
2014
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck [JK10] and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ 2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2 −O(I) and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braverman [Bra12]. First, we show that the information complexity of the Vector in Subspace Problem [KR11] is Ω(n 1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an Ω(n) lower bound on the information complexity of the Gap Hamming Distance Problem.
Related papers
On relating one-way classical and quantum communication complexities
Quantum
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function f(x,y), where x is given to Alice and y is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f:X×Y→Z∪{⊥} be a partial function and μ be a distribution with support contained in f−1(Z). Denote d=|Z|. Let Rϵ1,μ(f) be the classical one-way communication complexity of f; Qϵ1,μ(f) be the quantum one-way communication complexity of f and Qϵ1,μ,∗(f) be the entanglement-assisted quantum one-way communication complexity of f, each with dist...
Quantum observer and Kolmogorov complexity: a model that can be tested
2010
Different observers do not have to agree on how they identify a quantum system. We explore a condition based on algorithmic complexity that allows a system to be described as an objective "element of reality". We also suggest an experimental test of the hypothesis that any system, even much smaller than a human being, can be a quantum mechanical observer.
Quantum Entropy and Complexity
Open Systems & Information Dynamics
We study the relations between the recently proposed machine-independent quantum complexity of P. Gacs [1] and the entropy of classical and quantum systems. On one hand, by restricting Gacs complexity to ergodic classical dynamical systems, we retrieve the equality between the Kolmogorov complexity rate and the Shannon entropy rate derived by A. A. Brudno [2]. On the other hand, using the quantum Shannon-McMillan theorem [3], we show that such an equality holds densely in the case of ergodic quantum spin chains.
Prefix-free quantum Kolmogorov complexity
Theoretical Computer Science, 2021
We introduce quantum-K (QK), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of QK. Many properties enjoyed by prefix-free Kolmogorov complexity (K) have analogous versions for QK; notably a counting condition. Several connections between Solovay randomness and K, including the Chaitin type characterization of Solovay randomness, carry over to those between weak Solovay randomness and QK. We work towards a Levin-Schnorr type characterization of weak Solovay randomness in terms of QK. Schnorr randomness has a Levin-Schnorr characterization using K C ; a version of K using a computable measure machine, C. We similarly define QK C , a version of QK. Quantum Schnorr randomness is shown to have a Levin-Schnorr and a Chaitin type characterization using QK C. The latter implies a Chaitin type characterization of classical Schnorr randomness using K C .
Bell's Inequalities and Quantum Communication Complexity
Pattern Recognition Letters, 2004
We prove that for every Bell's inequality, including those which are not yet known, there always exists a communication complexity problem, for which a protocol assisted by states which violate the inequality is more efficient than any classical protocol. Violation of Bell's inequalities is the necessary and sufficient condition for quantum protocol to beat the classical ones.
Extending SDL and LMC complexity measures to quantum states
Physica A: Statistical Mechanics and its Applications, 2013
h i g h l i g h t s
Kolmogorov Complexity and its Applications
Algorithms and Complexity, 1990
A Short Introduction to Kolmogorov Complexity
2010
This is a short introduction to Kolmogorov complexity and information theory. The interested reader is referred to the literature, especially the textbooks [CT91] and [LV97] which cover the fields of information theory and Kolmogorov complexity in depth and with all the necessary rigor. They are well to read and require only a minimum of prior knowledge.
Algorithmic Information Theory and Kolmogorov Complexity
2000
This document contains lecture notes of an introductory course on Kolmogorov complexity. They cover basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), notion of randomness (Martin-Löf randomness, Mises–Church randomness), Solomonoff universal a priori probability and their properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity) and applications (incompressibility method in computational complexity theory, incompleteness theorems).
Experimental quantum communication complexity
Physical Review A, 2005
We prove that the fidelity of two exemplary communication complexity protocols, allowing for an N-1 bit communication, can be exponentially improved by N-1 (unentangled) qubit communication. Taking into account, for a fair comparison, all inefficiencies of state-of-the-art setup , the experimental implementation outperforms the best classical protocol, making it the candidate for multi-party quantum communication applications.
Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.