Generating Randomness from a Computable, Non-random Sequence of Qubits

Martin-Löf randomness for infinite sequences of bits, a central concept in algorithmic randomness[9], has recently been generalized to infinite sequences of qubits [10]. As is standard in the literature in algorithmic randomness and mathematical logic, let $2^{\omega}$ denote the collection of infinite sequences of bits, let $2^{n}$ denote the set of bit strings of length $n$, $2^{<\omega}:=\bigcup_{n}2^{n}$ and let $2^{\leq\omega}:=2^{<\omega}\cup 2^{\omega}$. $X\in 2^{\omega}$ is said to be Martin-Löf random (MLR) if it is not in any effectively null set with respect to the uniform measure on $2^{\omega}$ [9]. Nies and Scholz introduced the notion of a state to describe an infinite sequence of qubits [10] and then defined quantum-Martin-Löf randomness for states. We quickly sketch those parts of their work most relevant to the arguments in this paper. All definitions in the introduction section are from [10] or [9]. See [9] and [7] for a detailed introduction to Martin-Löf randomness and computability theory.

Here, $PT_{\mathbb{C}^{2}}$ denotes the partial trace which ‘traces out’ the last qubit from $\mathbb{C}^{2^{n}}$. $\rho$ is a infinite sequence of qubits whose first $n$ qubits are given by $\rho_{n}$. For this notion to be meaningful, $\rho$ is required to be coherent in the following sense; for all $n$, $\rho_{n}$, when ‘restricted’ via the partial trace to it’s first $n-1$ qubits, has the same measurement statistics as the state on $n-1$ qubits given by $\rho_{n-1}$. We now sketch a few notions from computability theory pertinent to us. Let $A\in 2^{\omega}$. We define an $A$-computable function to be a total function that can be realized by a Turing machine with $A$ as an oracle. By ‘computable’, we will refer to $\emptyset$-computable. The concept of an $A$-computable sequence of natural numbers will come up frequently in our discussion.

Since the algebraic complex numbers have a computable presentation (see [10]), we may identify a special projection with a natural number and hence talk about computable sequences of special projections. Let $I$ denote the two by two identity matrix.

While a $2^{n}$ by $2^{n}$ special projection may be thought of as a computable projective measurement on a system of $n$ qubits, a q-$\Sigma_{1}^{0}$ class corresponds to a computable sequence of projective measurements on longer and longer systems of qubits and mirrors the concept of a $\Sigma_{1}^{0}$ class in computability theory. One of the many equivalent ways of defining a $\Sigma_{1}^{0}$ class is as follows. If $C\subset 2^{n}$, let $\llbracket C\rrbracket\subseteq 2^{\omega}$ be the set of all $X\in 2^{\omega}$ such that the initial segment of $X$ of length $n$ is in $C$.

A $\Sigma_{1}^{0}$ class, S is coded (non-uniquely) by the index of the total computable function generating the sequence $(A_{i})_{i\in\mathbb{N}}$ occurring in (2) in the definition of $S$. Hence, the notion of a computable sequence of $\Sigma_{1}^{0}$ classes makes sense (see [9], section 3.2). One sees that the special projections $q_{i}$ in the definition of the q-$\Sigma_{1}^{0}$, $G$ play the role of the $A_{i}$s which generate a the $\Sigma_{1}^{0}$ class, $S$. The following notion is a quantum analog of the uniform measure of $S$ which equals $\lim_{n}(2^{-n}|A_{n}|)$, where $|.|$ refers to the cardinality. (The uniform measure on $2^{\omega}$ is the measure induced by letting the measure of $\llbracket\tau\rrbracket$ to be $2^{-|\tau|}$ for each $\tau\in 2^{<\omega}$. Here, $|\tau|:=n$ if $\tau\in 2^{n}$.)

Informally, a q-$\Sigma_{1}^{0}$ class, $G=(p_{n})_{n\in\mathbb{N}}$ may be thought of as an observable whose expected value, when ‘measured’ on a state $\rho=(\rho_{n})_{n\in\mathbb{N}}$ is $\rho(G):=\lim_{n}$ tr $(\rho_{n}p_{n})$. The positive-semidefiniteness of density matrices, the coherence of the components of $\rho$ and condition (3) in definition 1.5 ensure that $tr(\rho_{n}p_{n})$ is non decreasing in $n$. As $tr(\rho_{n}p_{n})\leq 1$ for all $n$, $\rho(G):=\lim_{n}$ tr $(\rho_{n}p_{n})$ exists.

Having established the necessary prerequisites, we can define a quantum Martin-Löf random (q-MLR) state. Roughly speaking, a state is q-MLR if it cannot be ‘detected by projective measurements of arbitrarily small rank’.

To fix notation, let $X(n)$ denote the $n$th bit of an $X\in 2^{\leq\omega}$ , let $p(E)$ stand for the probability of the event $E$.

Let $\rho=(\rho_{n})_{n\in\mathbb{N}}$ be a state and $B=((b^{n}_{0},b^{n}_{1}))_{n\in\mathbb{N}}$ be a measurement system. We now work towards formalizing a notion of qubitwise measurement of $\rho$ in the bases in $B$. A (probability) premeasure [7],$p$ (also called a measure representation [9]), is a function from the set of all finite bit strings to $[0,1]$ satisfying $\forall n$, $\forall\tau\in 2^{n},p(\tau)=p(\tau 0)+p(\tau 1)$. $p$ induces a measure on $2^{\omega}$ which is seen to be unique by Carathéodory’s extension theorem (See 6.12.1 in [7]). Flipping a $0,1$ sided fair coin repeatedly induces a probability measure (which happens to be the uniform measure) on $2^{\omega}$ as follows. Let the random variable $Z(n)$ denote the outcome of the the $n$th coin flip. The sequence $(Z(n))_{n\in\mathbb{N}}$ induces a premeasure, $p$, on $2^{<\omega}$ which extends to the uniform measure on $2^{\omega}$. Here, $p(\sigma)=2^{-n}$ is the probability that $Z(i)=\sigma(i)$ for all $i\leq|\sigma|$. Similarly the act of measuring $\rho$ qubit by qubit in $B$ induces a premeasure on $2^{<\omega}$ which extends to a probability measure (denoted $\mu_{\rho}^{B}$) on $2^{\omega}$ as follows. Let the random variable $X(n)$ be the $0,1$ valued outcome of the measurement of the $n$th qubit of $\rho$. Let $p$ be the premeasure induced by the sequence $(X(n))_{n\in\mathbb{N}}$ on $2^{<\omega}$. $p$ extends to $\mu_{\rho}^{B}$ on $2^{\omega}$. For any $A\subseteq 2^{\omega}$, $\mu_{\rho}^{B}(A)$ is the probability that $X\in A$ where $X$ is the element of $2^{\omega}$ obtained in the limit by the qubit by qubit measurement of $\rho$ in $B$. The most conspicuous difference between the two situations is that while the $(Z(n))_{n\in\mathbb{N}}$ are independent, $(X(n))_{n\in\mathbb{N}}$ need not be independent as the elements of $\rho$ can be entangled. We now formalize the above. The following calculations follow from standard results mentioned, for example, in [6].

We now define $(X(n))_{n\in\mathbb{N}}$ and $p$, the induced premeasure. Measure $\rho_{1}$ by the measurement operators $\{|b^{1}_{0}\big{>}\big{<}b^{1}_{0}|,|b^{1}_{1}\big{>}\big{<}b^{1}_{1}|\}$ and define $X(1):=i$ if $b^{1}_{i}$ was obtained by the above measurement. Let $\hat{\rho_{2}}$ be the density matrix corresponding to the post-measurement state of $\rho_{2}$ given that $\rho_{2}$ yields $|b^{1}_{X(1)}\big{>}\big{<}b^{1}_{X(1)}|\otimes I$ if measured in the system

I.e,

To define $X(2)$, measure $\hat{\rho_{2}}$ by the measurement operators

and set $X(2):=i$ if $I\otimes|b^{2}_{i}\big{>}\big{<}b^{2}_{i}|$ is obtained. We use $\hat{\rho_{2}}$ instead of $\rho_{2}$ to define $X(2)$ to account for the previous measurement of the first qubit. $X(n)$ is defined similarly. By the above,

Since $PT_{\mathbb{C}^{2}}(\rho_{2})=\rho_{1}$, $p(X(1)=i)=tr((|b^{1}_{i}\big{>}\big{<}b^{1}_{i}|\otimes I)\rho_{2}\big{)}$. So,

Given $\tau\in 2^{n}$, similar calculations show that

This defines $p$. The following lemma shows that $p(.)$ is a premeasure. Define $\mu^{B}_{\rho}$ to be the unique probability measure induced by it.

Here, $S\oplus T$ is obtained by putting $S$ on the even bits and $T$ on the odd bits [9].

Let $MLR\subset 2^{\omega}$ be the set of MLR bitstrings. If $\rho$ is a state and $B$ a measurement system, $\mu^{B}_{\rho}(MLR)$ is the probability of getting a MLR bitstring by a qubit-wise measurement of $\rho$ as described in the previous section.