Entropy representation by prefix Kolmogorov complexity

At least 11 years old · documented by

Let μ\mu be the universal lower-semicomputable semi-density matrix from the preceding conjecture. Let ∣1⟩,∣2⟩,…\ket{1},\ket{2},\ldots be a computable orthogonal sequence of states, and define real-valued functions by

H‾(∣ψ⟩)=−⟨ψ∣(log⁡μ)ψ⟩,H‾(∣ψ⟩)=−log⁡⟨ψ∣μψ⟩.\overline{H}(\ket{\psi})=-\braket{\psi|(\log\mu)\psi},\qquad \underline{H}(\ket{\psi})=-\log\braket{\psi|\mu\psi}.

Here K(i)K(i) denotes prefix Kolmogorov complexity.

Entropy-complexity conjecture. For H=H‾H=\overline{H} or H=H‾H=\underline{H}, one has

H(∣i⟩)=K(i)+O(1).H(\ket{i})=K(i)+O(1).

This is intended as a quantum analogue of the relationship between classical algorithmic entropy and prefix complexity. The supplied text gives no resolution status for this claim.

References

Primary source

Toru Takisaka, “On Gács' quantum algorithmic entropy”, arXiv:1412.8547 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.