Is there a quantum analog of Kolmogorov Complexity?

Question

Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar.

Since there is a quantum entropy is it reasonable to ask if there is quantum analog of Kolmogorov complexity that gives rise to some sort of shortest 'quantum' program interpretation or another suitable interpretation that corresponds to quantum entropy?

What is the right analogy and the right equivalence to quantum entropy?

Answer 1

Since there is a constant length Turing machine that simulates any quantum computer, a quantum version of Kolmogorov complexity would differ from any classical Kolmogorov complexity by at most a constant.

Answer 2

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S) https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

In summary, the von Neumann entropy of a density matrix measures the entropy of the distribution given by its eigenvalues and ignores the algorithmic complexity of its eigenvectors.

Answer 3

Markus Mueller's Phd thesis is about quantum Kolmogorov complexity.

Quantum Kolmogorov Complexity and the Quantum Turing Machine

Here is his definition:

Given a Quantum Turing Machine $M$ and a finite error $\delta>0$, the finite-error quantum Kolmogorov complexity of a qubit string $|x\rangle$ is

$K_\delta^Q(x)=\min\limits_p\Big\{\ell(p): \|x-M(p)\|_{\mathrm{tr}}<\delta\Big\}$

and the approximate-scheme quantum Kolmogorov complexity of $|x\rangle$ is

$K^Q(x)=\min\limits_p\left\{\ell(p): \forall k\in\mathbb{N}: \|x-M(p,k)\|_{\mathrm{tr}}<\frac{1}{k}\right\}$

where $\|\cdot\|_{\mathrm{tr}}$ is the trace norm, i.e. $\|\rho-\sigma\|_{\mathrm{tr}}:=\frac{1}{2}\operatorname{Tr}\left(\sqrt{(\rho-\sigma)^\dagger(\rho-\sigma)}\right)$.

Another version of quantum Kolmogorov complexity of $|x\rangle$ with respect to quantum Turing machine $M$ is

$K^Q(x)=\min\limits_p\left\{\ell(p)+\lceil -\log\|\langle z|x\rangle\|^2\rceil: M(p)=|z\rangle\right\}$

You can find this version in Ming Li and Paul Vitanyi's book: An Introduction to Kolmogorov Complexity and Its Applications