Category Archives: Algorithmic randomness

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

No-randomness-from-nothing for computable randomness

I recently added the short article “No-randomness-from-nothing for computable randomness” to the 2014 PDF Logic Blog.

There are two important properties that one would like a notion of algorithmic randomness to have.  The first is called randomness preservation.  It says that if $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is a computable measure-preserving map and $X \in \{0,1\}^\mathbb{N}$ is random, then so is $T(X)$.  While this property holds for most randomness notions—Kurtz randomness, Schnorr randomness, Martin-Löf randomness, weak $n$-randomness, difference randomness, Demuth randomness, Oberwolfach randomness, and $n$-randomness—it fails for computable randomness. (Nonetheless, I have work in preparation—extending previous work—showing that randomness preservation for computable randomness holds for all “naturally occurring” computable measure-preserving maps, but this is not the purpose of this article.)

The purpose of this article to show that the dual property, no-randomness-from-nothing, holds for computable randomness.

Theorem (No-randomness-from-nothing for computable randomness).  Assume $\mu$ is a computable measure and $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is an a.e. computable measure-preserving map.  If $Y \in \{0,1\}^\mathbb{N}$ is computably random, then there is some $X \in \{0,1\}^\mathbb{N}$ such that $T(X)=Y$.

(The proof can be found in the PDF Logic Blog.)

It is previously known that no-randomness-from-nothing holds for Martin-Löf randomness, weak $n$-randomness ($n\geq2$), and $n$-randomness.  This theorem answers a question of Bienvenu and Porter, who asked if it is true for Schnorr and computable randomness. The Schnorr randomness case still remains open.

Open question.  Does no-randomness-from-nothing hold for Schnorr randomness?

(Although, once again, I have work in preparation showing that no-randomness-from-nothing for Schnorr randomness holds for all “naturally occurring” computable measure-preserving maps.)

CCR 2014: Open questions

For a slightly more detailed discussion of the following questions, see the PDF version of the Logic Blog.

Computable randomness

Let $\mathrm{CR}$ denote the class of computably random sets.

Question. (van Lambalgen’s theorem for $\mathrm{CR}$) Let $X$ be computably random, and let $Y$ be computably random relative to $X$. Is $X \oplus Y$ computably random?

Question. (Joseph Miller) Let $X$ be computably random. Is there an incomputable oracle $A$ such that $X$ is computably random relative to $A$?


Let $\textrm{High}(\textrm{CR}, \textrm{MLR})$ denote the class of oracles $A$ such that $\textrm{CR}^A \subseteq \textrm{MLR}$.

Question. (Joseph Miller) Is every set in  $\mathrm{High}(\mathrm{CR}, \mathrm{MLR})$ PA-complete?


We write $A \le_{\mathrm{CR}} B$ if $\mathrm{CR}^B \subseteq \mathrm{CR}^A$.

Question.  (Nies) Is $\le_{\mathrm{CR}}$ equivalent to $\le_\mathrm{T}$?


Martin-Löf randomness

Let $A \triangle B$ denote the symmetric difference of sets $A$, $B$.

Definition. (Kihara) We say that $A$ is ML-additive if $Z \in \mathrm{MLR}$ implies $Z \triangle A\in \mathrm{MLR}$ for each $Z$.

Clearly every low for ML-random is ML-additive.

Question. Is every ML-additive oracle low for ML-randomness?


Definition. (Yu) We say $A$ is absolutely low for $R$ if for all $Y$,

$R \in \mathrm{MLR}^Y \rightarrow R\in\mathrm{MLR}^{Y\oplus A}.$

Fact. (Stephan and Yu) Let  $A$ be $K$-trivial. Then $A$ is absolutely low for $\Omega$.

Question. (Yu) Is every set that is absolutely low for $\Omega$ $K$-trivial?

Definition. (Merkle) We say an oracle $A$ is super-absolutely low for $\Omega$  if for each oracle  $Y$ which is low for $\Omega$,

$\forall n(K^Y(n)=K^{A\oplus Y}(n)+O(1)).$

Note that every such set  is  absolutely low for $\Omega$ by definition. In fact it  must be  low for $K$, by letting $Y= \emptyset$. We ask the converse.

Question. (Merkle) Is every low for $K$ set super-absolutely low for $\Omega$?

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