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

i-manager’s Journal on Mathematics

On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

Alexei Kaltchenko

Published Jan 1, 2022• 0 citations
Publisher

Abstract

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.

DOI
10.26634/jmat.11.2.19190

Related papers

Kolmogorov complexity of unitary transformations in quantum computing

Alexei Kaltchenko

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.

arXiv:2110.05937•Oct 10, 2021•1 citation

Descriptional complexity of unitary transformations

Alexei Kaltchenko

Weintroduce the notion of descriptional complexity of nite-dimensional unitary transformations, which is closely related to the notion of Kolmogorov complexity of a quantum state. In quantum computing, quantum states are associated with quantum data, and unitary transformations of quantum states are associated with quantum computer programs.

International Conference on Micro- and Nano-Electronics (ICMNE)•Jan 31, 2022•0 citations

Quantum Kolmogorov complexity and duality of unitary transformations and quantum states.

Alexei Kaltchenko

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.

•Oct 13, 2021•0 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

LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY

Caroline Rogers, Rajagopal Nagarajan

We show that the optimal rate of lossless quantum data compression is closely related to Berthiaume, van Dam and Laplante's quantum Kolmogorov complexity. We show that: • The expected quantum Kolmogorov complexity of a mixture is close to the optimal rate of lossless data compression of that mixture. • If quantum Kolmogorov complexity obeys some inequality, then so does the optimal rate of lossless quantum data compression.

International Journal of Quantum Information•Mar 1, 2011•2 citations

Quantum algorithmic entropy

Péter Gács

We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.

arXiv:quant-ph/0011046•Journal of Physics A Mathematical and General•Aug 24, 2001•68 citations
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.
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.
We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.