Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IET Quantum Communication

Second quantised information distance

Songsong Dai

Published Sep 28, 2022• 0 citations
Publisher

Abstract

Abstract The Kolmogorov complexity of a string is the minimum length of a programme that can produce that string. Information distance between two strings based on Kolmogorov complexity is defined as the minimum length of a programme that can transform either string into the other one, both ways. The second quantised Kolmogorov complexity of a quantum state is the minimum average length of a quantum programme that can reproduce that state. In this paper, a second quantised information distance is defined based on the second quantised Kolmogorov complexity. It is described as the minimum average length of a transformation quantum programme between two quantum states. This distance's basic properties are discussed. A practical analogue of quantum information distance is also developed based on quantum data compression.

DOI
10.1049/qtc2.12050

Related papers

Quantum information distance

Songsong Dai

In this paper, we give a definition for quantum information distance. In the classical setting, information distance between two classical strings is developed based on classical Kolmogorov complexity. It is defined as the length of a shortest transition program between these two strings in a universal Turing machine. We define the quantum information distance based on Berthiaume et al.’s quantum Kolmogorov complexity. The quantum information distance between qubit strings is defined as the length of the shortest quantum transition program between these two qubit strings in a universal quantum Turing machine. We show that our definition of quantum information distance is invariant under the choice of the underlying quantum Turing machine.

International Journal of Quantum Information•Sep 1, 2021•2 citations

SECOND QUANTIZED KOLMOGOROV COMPLEXITY

Caroline Rogers, Vlatko Vedral, Rajagopal Nagarajan

The Kolmogorov complexity of a string is the length of its shortest description. We define a second quantized Kolmogorov complexity where the length of a description is defined to be the average length of its superposition. We discuss this complexity's basic properties. We define the corresponding prefix complexity and show that the inequalities obeyed by this prefix complexity are also obeyed by von Neumann entropy.

arXiv:0809.2642•International Journal of Quantum Information•Aug 1, 2008•12 citations

Quantum Kolmogorov complexity

A. Berthiaume, Wim van Dam, Sophie Laplante

In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.

IEEE Conference on Computational Complexity (CCC)•Nov 7, 2002•17 citations

Quantum Kolmogorov Complexity and the Quantum Turing Machine

Markus P. Müller

The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.

arXiv:0712.4377•Dec 28, 2007•14 citations

THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY

Caroline Rogers, Vlatko Vedral

The Kolmogorov complexity of a physical state is the minimal physical resources required to reproduce that state. We define a second quantized quantum Turing machine and use it to define second quantized Kolmogorov complexity. There are two advantages to our approach — our measure of the second quantized Kolmogorov complexity is closer to physical reality and unlike other quantum Kolmogorov complexities, it is continuous. We give examples where the second quantized and quantum Kolmogorov complexity differ.

arXiv:quant-ph/0506266•Modern Physics Letters B•May 20, 2008•7 citations

ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Caterina E. Mora, Hans J. Briegel

We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.

arXiv:quant-ph/0412172•International Journal of Quantum Information•Aug 1, 2006•24 citations
Abstract The Kolmogorov complexity of a string is the minimum length of a programme that can produce that string. Information distance between two strings based on Kolmogorov complexity is defined as the minimum length of a programme that can transform either string into the other one, both ways. The second quantised Kolmogorov complexity of a quantum state is the minimum average length of a quantum programme that can reproduce that state. In this paper, a second quantised information distance is defined based on the second quantised Kolmogorov complexity. It is described as the minimum average length of a transformation quantum programme between two quantum states. This distance's basic properties are discussed. A practical analogue of quantum information distance is also developed based on quantum data compression.
In this paper, we give a definition for quantum information distance. In the classical setting, information distance between two classical strings is developed based on classical Kolmogorov complexity. It is defined as the length of a shortest transition program between these two strings in a universal Turing machine. We define the quantum information distance based on Berthiaume et al.’s quantum Kolmogorov complexity. The quantum information distance between qubit strings is defined as the length of the shortest quantum transition program between these two qubit strings in a universal quantum Turing machine. We show that our definition of quantum information distance is invariant under the choice of the underlying quantum Turing machine.
In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.
The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.
The Kolmogorov complexity of a physical state is the minimal physical resources required to reproduce that state. We define a second quantized quantum Turing machine and use it to define second quantized Kolmogorov complexity. There are two advantages to our approach — our measure of the second quantized Kolmogorov complexity is closer to physical reality and unlike other quantum Kolmogorov complexities, it is continuous. We give examples where the second quantized and quantum Kolmogorov complexity differ.
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.