Kolmogorov complexity in quantum mechanics and quantum computing

André Berthiaume, Wim van Dam, Sophie Laplante

Alexei Grinbaum

Alexei Grinbaum

Fabio Benatti, Tyll Krüger, Markus P. Müller +2 more

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.

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.