Category Archives: Kolmogorov complexity

On The Notion of Quantum Transmission

In a canonical multisource algorithmic information theory example, actor $A$ wants to send a single text message $m$ to actor $B$. Both actors share the same copy of a universal Turing machine $T$. The actor $A$ sends a program $p$ to $B$ such that $m=T(p)$. The cost of the transmission is $\|p\|$. The actor $A$ can minimize cost by sending $k=\mathbf{K}(m)$ bits to $B$, where $\mathbf{K}$ is the Kolmogorov complexity of $m$.

We generalize now to the quantum case. Suppose that actor $A$ wants to send a pure quantum state of $N$ entangled qubits to actor $B$, represented as an normalized vector $|{\psi}\rangle\in (\mathbb{C}^2)^{\otimes N}$. Thus given the basis sets $|{\beta_i}\rangle$, a pure state can be represented as $|{\psi}\rangle= \sum_i c_i |{\beta_i}\rangle$, where $\sum_i |c_i|^2 = 1.$ Actor $A$ has access to two channels, a quantum channel and a classical channel. Actor $A$ can choose to send $M$ (possibly entangled) qubits $|{\theta}\rangle$ on the quantum channel and $L$ regular bits $p$ on the classical channel, describing a quantum circuit, representing a unitary operation $U=T(p)$. Actor $B$, upon receiving $|{\theta}\rangle$ and $p$, constructs the unitary operation $U$, and then applies it to $|\theta\rangle$ (with padded zeros) to produce $|{\psi’}\rangle= U|{\theta 0\dots}\rangle$. Actor $B$ is not expected to produce $|{\psi}\rangle$ exactly. Instead the fidelity of the attempt is measured by $F = -\log |\langle{\psi}|{\psi’}\rangle|^2$. The goal of actor $A$ is to minimize $\mathrm{Cost}(|{\theta}\rangle,p)=L+M+F$.

Claim: For all non-exotic states $|{\psi}\rangle$, actor $A$ can minimize $\mathrm{Cost}(|{\theta}\rangle,p)$ by only sending information on the classical channel, and leaving the quantum channel empty, with $|{\theta}\rangle = 0$.

The claim has logarithmic precision. A state $|{\psi}\rangle$ is exotic if a suitable (possibly infinite) description of $|{\psi}\rangle$, denoted by $\mathrm{Enc}(|{\psi}\rangle)\in\{0,1\}^\infty$ has high mutual information with the halting sequence $\mathcal{H}$, denoted by $\mathbf{I}(\mathrm{Enc}(|{\psi}\rangle){:}\mathcal{H})$. Thus, in the limit, qubits don’t offer much help in terms of compression of natural quantum states. The proof of this theorem expands upon established methods of proving inequalities of $(\alpha,\beta)$ stochastic objects.
Thanks! -Sam

Open questions from ARA

A list of open problems as discussed during the 2013 La Mothe retreat and during ARA 2013 in Nancy.

Computable randomness

If \(X\) is computably random and \(Y\) is \(X\)-computably random, is \(X \oplus Y\) computably random?

[J. Miller] Is there a computably random \(X\) such that for every non-computable \(Y\), \(X\) is not \(Y\)-computably random?

Randomness and Turing degrees

Continue reading

$K^X \ge_T X$

Written by Turetsky. Proved by Miller and Turetsky, and then vastly simplified by Bienvenu.

Proposition. For any real $X$, $K^X \ge_T X$.

Proof. $X$ is $X$-trivial. That is, $K^X(X\!\!\upharpoonright_n) \le K^X(n) + c$. Note that $K^X$ can compute the tree $\{\sigma \in 2^{<\omega} : K^X(\sigma) \le K^X(|\sigma|) + c\}$. This tree has finitely many infinite paths, and $X$ is one of them. As an isolated path, $K^X$ can compute $X$. [Source: The 2013 Logic Blog, page 31]