Entropy representation by prefix Kolmogorov complexity

From papers

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=HH=\overline{H} or H=HH=\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.