LASIGE’s integrated researcher André Souto is co-author of the paper “Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines” published in Quantum, a top-tier journal ranked in the top 10% of Scimago Journal Ranking. The paper is first authored by Mariano Lemus (Instituto Superior Técnico) and also counts as co-authors Ricardo Faleiro, Paulo Mateus, and Nikola Paunković (all from Instituto Superior Técnico).

Determining the quantumness of a general state is a particularly interesting problem that has captured the attention of many researchers. One can consider several approaches to evaluate this characteristic, and they are usually based on the concept of (von Neumann) entropy. In this paper, the authors consider the Kolmogorov complexity, a measure of intrinsic information of an object (either a string or a state). Using deterministic controlled quantum Turing machines, they extend the Kolmogorov complexity to handle mixed-state inputs and outputs. Along the way, they show that dcq-computable states are the ones that can be approximated by a dcq-TM. They have also introduced the conditional Kolmogorov complexity of quantum states to investigate three key aspects of algorithmic information within a quantum state. These aspects include comparing the information within a quantum state representation as an array of real numbers, examining the limits of copying quantum states from an algorithmic complexity point of view and exploring the complexity of correlations in quantum systems. With the latter, they propose a definition of algorithmic mutual information that satisfies the symmetry of information property.

The full paper is available here.