Quantum Kolmogorov Complexity and Its Applications

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.

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.

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.

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.

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.

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...

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.

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.

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 .

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.