domain: info phys

text:
Samuel Epstein
email: samepst@jptheorygroup.org

An Introduction to Algorithmic Information Theory and Quantum Mechanics

This article presents a survey of published and unpublished material of the intersection of Algorithmic Information Theory and Quantum Mechanics. It is, to the author's knowledge, the first of its type. Three different notions of the algorithmic content of quantum states are reviewed. Notions of algorithmic quantum typicality and mutual information are introduced. The relationship between algorithmic information and quantum measurements is explored. One of the surprising results is that an overwhelming majority of quantum (pure and mixed) states, when undertaking decoherence, will result in a classical probability with no algorithmic information. Thus most quantum states decohere into white noise. A quantum analouge of Martin Löf random sequence is reviewed. Algorithmic Information Theory presents new complications for the Many Worlds Theory, as it conflicts with the Independence Postulate. When algorithmically complicated processes are ruled out, measurements are required to produce distributions over quantum states that have cloneable information.

. Thus there is a positive constant c, where c(E ⊗ F ) ∈

Chapter 1

Introduction

Classical information theory studies the communication of bits across a noisy channel. Quantum Information Theory (QIT) studies the kind of information ("quantum information") which is transmitted by microparticles from a preparation device (sender) to a measuring apparatus (receiver) in a quantum mechanical experiment-in other words, the distinction between carriers of classical and quantum information becomes essential. The notion of a qubit can be defined at an abstract level, without giving preference to any particular physical system such as a spin-12 particle or a photon. Qubits behave very differently than bits. To start, qubits can be in a linear superposition between 0 and 1. Qubits can have entanglement, where two objects at a distance become a single entity. The study of entanglement and in particular the question how it can be quantified is therefore a central topic within quantum information theory. However, due to the no-cloning theorem [START_REF] Wootters | A single quantum cannot be cloned[END_REF], instant communication is not possible. Some other aspects of QIT are as follows.

1. Quantum Computing: includes hardware (quantum computers), software, algorithm such as Shor's factoring algorithm or Grover's algorithm, and applications.

2. Quantum Communication: quantum networking, quantum internet, quantum cryptography.

3. Applications in Physics: applications to convex optimizations, black holes, and exotic quantum phases of matter.

4. Quantum Shannon Theory: quantum channels, quantum protocols, quantum information and entropy.

One aspect of Quantum Shannon Theory (QST) that has had relatively little study is its relationship to Algorithmic Information Theory (AIT). AIT, in part, is the study of the information content of individual strings. A string is random if it cannot be compressed with respect to a universal Turing machine. This paper surveys the current state of research of QST and AIT and provides unpublished results from the author. Hopefully it will convince the reader that there is a fruitful area of research of QST and AIT. Some areas of this intersection include algorthmic content of quantum states, how typical a quantum state is with respect to a quantum source, and how to quantify the algorithmic content of a measurement. One can also gain further insight into quantum transformations, such as purification, decoherence, and approximations to quantum cloning.

As this survey will show, there are some aspects of AIT that directly transfer over to quantum mechanics. This includes comparable definitions of complexity, and conservation inequalities. In addition, there exist quantum versions of the EL Theorem, [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF] and the Outlier Theorem, [START_REF] Epstein | All sampling methods produce outliers[END_REF]. However there are some aspects of AIT that are different in the context of quantum mechanics. This includes the fact the self information of most quantum pure states is zero, with I(|ψ : ψ) ≈ 0. This has implications on the algorithmic content of measurements and decoherence. The main areas covered in this article are

• Chapter 2: This chapter covers the background material needed for the article. A new definition, the algorithmic information between probabilities, is introduced and shown to have information non-growth properties with respect to randomized processing.

• Chapter 3: Three different algorithmic measures of quantum states are covered. Their properties are described, including an addition inequality, a Quantum EL Theorem, and a generalized no-cloning theorem. Multiple relationships between the complexities are proven.

• Chapter 4: The notion of the algorithmic typicality of one quantum state with respect to another quantum state is introduced. Typicality is conserved with respect to quantum operations. A quantum outlier theorem is proven. This states that non-exotic projections must have atypical pure states in their images.

• Chapter 5: The definition of quantum algorithmic information is introduced. Quantum information differs from classical algorithmic information in that an overwhelming majority of pure states have negligible self-information. Information is conserved over quantum operations, with implications to quantum cloning, quantum decoherence, and purification.

• Chapter 6: Quantum algorithmic information upper bounds the amount of classical information produced by quantum measurements. Given a quantum measurement, for an overwhelming majority of pure states, the measurement will be random noise. An overwhelming majority of quantum pure states , when undertaking decoherence, will result in a classical probability with no algorithmic information.

• Chapter 7: A quantum equivalent to Martin Löf random sequence is introduced. Such quantum random states have incompressible initial segments with respect to a new measure quantum complexity called Quantum Operation Complexity. This complexity term measures the cost of approximating a state with a classical and quantum component.

• Chapter 8: This chapter shows the Many Worlds Theory and AIT are in conflict, as shown through the existence of a finite experiment that measures the spin of a large number of electrons. After the experiment there are branches of positive probability which contain forbidden sequences that break the Independence Postulate, a postulate in AIT.

• Chapter 9: This chapter concludes the paper with a discussion of the boundary between quantum information and classical information. We show that measurements are necessary to produce distributions over quantum states that have cloneable information.

• Appendix A: Properties of the quantum information of basis states are proven.

Chapter 2

Background

The reader is assumed to be familiar with both algorithmic information theory and quantum information theory, but we review the core terms. We use N, Z, Q, R, {0, 1}, {0, 1} * , and {0, 1} ∞ to denote natural numbers, integers, rational numbers, reals, bits, finite strings, and infinite sequences. {0, 1} * ∞ def = {0, 1} * ∪ {0, 1} ∞ . x denotes the length of the string. Let X ≥0 and X >0 be the sets of non-negative and of positive elements of X. [A] def = 1 if statement A holds, else [A] def = 0. The set of finite bit-strings is denoted by {0, 1} * . For set of strings A ⊆ {0, 1} * , A = {xα : x ∈ A, α ∈ {0, 1} ∞ }. When it is clear from the context, we will use natural numbers and other finite objects interchangeably with their binary representations.

The ith bit of α ∈ {0, 1} * ∞ is denoted α i , and its n bit prefix is denoted α ≤n . x ∈ {0, 1} * for x ∈ {0, 1} * is the self-delimiting code that doubles every bit of x and changes the last bit of the result. For positive real functions f , by < + f , > + f , = + f , and < log f , > log f , ∼f we denote ≤ f +O(1), ≥ f -O(1), = f ±O(1) and ≤ f +O(log(f +1)), ≥f -O(log(f +1)), = f ±O(log(f +1)). Furthermore, * <f , * >f denotes < O(1)f and > f /O(1). The term and * =f is used to denote * >f and * <f . A probability measure Q over {0, 1} * is elementary if it has finite support and range that is a subset of rationals. Elementary probability measures can be encoded into finite strings Q in the standard way.

Algorithmic Information Theory

T y (x) is the output of algorithm T (or ⊥ if it does not halt) on input x ∈ {0, 1} * and auxiliary input y ∈ {0, 1} * ∞ . T is prefix-free if for all x, s ∈ {0, 1} * with s = ∅, either T y (x) = ⊥ or T y (xs) = ⊥ . The complexity of x ∈ {0, 1} * with respect to T y is K T (x|y) def = inf{ p : T y (p) = x}. There exist optimal for K prefix-free algorithms U , meaning that for all prefix-free algorithms T , there exists c T ∈ N, where K U (x|y) ≤ K T (x|y) + c T for all x ∈ {0, 1} * and y ∈ {0, 1} * ∞ . For example, one can take a universal prefix-free algorithm U , where for each prefix-free algorithm T , there exists t ∈ {0, 1} * , with U y (tx) = T y (x) for all x ∈ {0, 1} * and y ∈ {0, 1} * ∞ . K(x|y) def = K U (x|y) is the Kolmogorov complexity of x ∈ {0, 1} * relative to y ∈ {0, 1} * ∞ .

The algorithmic probability is m(x|y) = {2 -p : U y (p) = x}. By the coding theorem K(x|y) = + -log m(x|y). The amount of mutual information between two strings x and y is I(x : y) = K(x) + K(y) -K(x, y). By the chain rule K(x, y) = + K(x) + K(y|x, K(x)). The halting sequence H ∈ {0, 1} ∞ is the infinite string where H i def = [U (i) halts] for all i ∈ N. The amount of information that H has about x ∈ {0, 1} * is I(x; H) = K(x) -K(x|H). The randomness deficiency of x ∈ {0, 1} * with respect to elementary probability P over {0, 1} * is d(x|P ) = -log P (x) -K(x| P ) . we say t : {0, 1} * → R ≥0 is a P -test, for some probability P , if

x t(x)P (x) ≤ 1. Let t P be a universal lower computable P -test, where for any other lower computable P -test t, t P (x) * > m(t)t(x). Then by the universality of the deficiency of randomness, [G 01], d(x|P ) = + log t P (x). The transform of a probability Q by f : {0, 1} * → {0, 1} * , is the probability f Q, where f Q(x) = f (y)=x Q(y). Both randomness deficiency and information enjoy conservation inequalities.

Theorem 1 (See [G 01]) d(f (x)|f Q) < + d(x|Q).
Theorem 2 ( [START_REF] Levin | Randomness conservation inequalities; information and independence in mathematical theories[END_REF]) I(f (x) : y) < + I(x : y).

Lemma 1 ( [START_REF] Epstein | The outlier theorem revisited[END_REF]) I(f (a); H) < + I(a; H) + K(f ).

Lemma 2 Let ψ a be an enumerable semi-measure, semi-computable relative to a. Proof. This requires a slight modification of the proof of Proposition 2 in [START_REF] Levin | Randomness conservation inequalities; information and independence in mathematical theories[END_REF], by requiring ψ to have a as auxilliary information. For completeness, we reproduce the proof. We The stochasticity of a string x ∈ {0, 1} * is Ks(x) = min Elementary Q K(Q)+3 log max{d(x|Q), 1}. Strings with high stochsticity measures are exotic, in that they have high mutual information with the halting sequence.

Lemma 3 ([Lev16, Eps21b]) Ks(x) < log I(x; H).

Algorithmic Information Between Probabilities

We can generalize from information from strings to information between arbitrary probability measures over strings.

Definition 1 (Information, Probabilities) For semi-measures p and q over {0, 1} * , I Prob (p : q) = log x,y∈{0,1} * 2 I(x:y) p(x)q(y).

Definition 2 (Channel) A channel f : {0, 1} * × {0, 1} * → R ≥0 has f (•|x) being a probability measure over {0, 1} * for each x ∈ {0, 1} * . For probability p, channel f , f p(x) = z f (x|z)p(z).
Theorem 3 For probabilities p and q over {0, 1} * , computable channel f , I Prob (f p : q) < + I Prob (p : q). Proof. Using Lemma 1,

I Prob (f p : q) = log x,y 2 I(x:y) z f (x|z)p(z)q(y) < + log y,z q(y)p(z) x 2 I((x,z):y) f (x|z).

6

Using Lemma 2, I Prob (f p : q) < + log z,y q(y)p(z)2 I(z:y) = + I Prob (p : q). Thus processing cannot increase information between two probabilities. If the the probability measure is concentrated at a single point, then it contains self-information equal to the complexity of that point. If the probability measure is spread out, then it is white noise, and contains no self-information. Some examples are as follows.

Example 1

• In general, a probability p, will have low I Prob (p : p) if it has large measure on simple strings, or low measure on a large number of complex strings, or some combination of the two.

• If probability p is concentrated on a single string x, then I Prob (p : p) = K(x).

• The uniform distribution over strings of length n has self information equal to (up to an additive constant) K(n).

• There are semi-measures that have infinite self information. Let α n be the n bit prefix of a Martin Löf random sequence α and n

∈ [2, ∞). Semi-measure p(x) = [x = α n ]n -2 has I Prob (p : p) = ∞.
• The universal semi-measure m has no self information.

Example 2 (Uniform Spread) An example channel f has f (•|x) be the uniform distribution over strings of length x . This is a cannonical spread function. Thus if p is a probability measure concentrated on a single string, then I Prob (p : p) = K(x), and I(f p : f p) = + K( x ). Thus f results in a decrease of self-information of p. This decrease of information occurs over all probabilities and computable channels.

Quantum Mechanics

We use the standard model of qubits used throughout quantum information theory. We deal with finite N dimensional Hilbert spaces H N , with bases |α 1 , |α 2 , . . . , |α n . We assume H n+1 ⊇ H n and the bases for H n are the beginning of that of H n+1 . An n qubit space is denoted by

Q n = n i=1 Q 1 , where qubit space Q 1 has bases |0 and |1 . For x ∈ Σ n we use |x ∈ Q n to denote n i=1 |x[i] .
The space Q n has 2 n dimensions and we identify it with H 2 n .

A pure quantum state |φ of length n is represented as a unit vector in Q n . Its corresponding element in the dual space is denoted by φ|.

p i |ψ i ψ i | is S(σ) = -p i log p i .
A pure quantum state |φ and (semi)density matrix σ are called elementary if their real and imaginary components have rational coefficients. Elementary objects can be encoded into strings or integers and be the output of halting programs. Therefore one can use the terminology K(|φ ) and K(σ), and also m(|φ ) and m(σ).

We say program q ∈ {0, 1} * lower computes positive semidefinite matrix σ if, given as input to universal Turing machine U , the machine U reads ≤ q bits and outputs, with or without halting, a sequence of elementary semi-density matrices {σ i } such that σ i ≤ σ i+1 and lim i→∞ σ i = σ. A matrix is lower computable if there is a program that lower computes it.

Quantum Operations

A quantum operation is the most general type of operation than can be applied to a quantum state. In Chapters 4 and 5, conservation inequalities will be proven with respect to quantum operations. A map transforming a quantum state σ to ε(σ) is a quantum operation if it satisfies the following three requirements 1. The map of ε is positive and trace preserving, with Tr(σ) = Tr(ε(σ)).

The map is linear with ε(

i p i σ i ) = i p i ε(σ i ).
3. The map is completely positive, were any map of the form ε ⊗ M acting on the extended Hilbert space is also positive.

Another means to describe quantum operations is through a series of operators. A quantum operation ε on mixed state σ A can be seen as the appending of an ancillia state σ b , applying a unitary transform U , then tracing out the ancillia system with

ε(σ A ) = Tr B (U (σ A ⊗ σ B )U * ) .
(2.1)

A third way to characterize a quantum operation is through Kraus operators, which can be derived using an algebraic reworking of Equation 2.1. Map ε is a quantum operation iff it can be represented (not necessarily uniquely) using a set of matrices {M i } where ε(σ) = i M i εM * i and i M * i M i ≤ I, where I is the identity matrix.

A quantum operation ε is elementary iff it admits a represented of the form in Equation 2.1 where B, U , and σ B are each elementary, in that they each can be encoded with a finite string. The encoding of an elementary quantum operation is denoted by ε = B U σ B . Each elementary quantum operation admits an elementary Kraus operator representation {M i }, in that each M i is an elementary matrix. This elementary Kraus operator is computable from ε .

Chapter 3

Quantum Complexity

Three Meausres of the Algorithmic Content of Individual Quantum States

The formal study of Algorithmic Information Theory and Quantum Mechanics began with the introduction of three independent measures of the algorithmic content of a mixed or pure quantum state, detailed in the papers [START_REF] Berthiaume | Quantum Kolmogorov Complexity[END_REF]G 01,[START_REF] Vitanyi | Quantum kolmogorov complexity based on classical descriptions[END_REF]. BVL complexity [START_REF] Berthiaume | Quantum Kolmogorov Complexity[END_REF] measures the complexity of a pure quantum state |ψ by the length of the smallest input to a universal quantum Turing machine that outputs a good approximation of |ψ . Vitányi complexity [START_REF] Vitanyi | Quantum kolmogorov complexity based on classical descriptions[END_REF] measures the entropy of a pure state |ψ as the amount of classical information needed to reproduce a good approximation of |ψ . Gács complexity measures the entropy of a pure or mixed quantum state by using a quantum analouge of of the universal semi-measure m.

BVL Complexity

BVL complexity, introduced in [BvL01], uses a universal quantum Turing machine to define the complexity of a pure quantum state. The input and output tape of this machine consists of symbols of the type 0, 1, and #. The input is an ensemble {p i } of pure states |ψ i of the same length n, where p i ≥ 0 and i p i = 1. This ensemble can be represented as a mixed state of n qubits. If, during the operation of the quantum Turing machine, all computational branches halt at a time t, then the contents on the output tape are considered the output of the quantum Turing machine.

The BVL Complexity of a pure state, Hbvl[ ](|ψ ) is the size of the smallest (possibly mixed state) input to a universal quantum Turing machine such that fidelity between the output and |ψ is at least . The fidelity between a mixed state output σ and |ψ is ψ| σ |ψ . We require that the input quantum state be elementary. We also require that universal quantum Turing machine be conditioned on the number of qubits n, on a classical auxillary tape.

Vitányi Complexity

Vitányi complexity [START_REF] Vitanyi | Quantum kolmogorov complexity based on classical descriptions[END_REF] is a measure of the algorithmic information content of a pure state |ψ . It is equal to the minimum of the Kolmogorov complexity of an approximating elementary pure state |φ summed with a score of their closeness. We use a slightly different definition than the original [START_REF] Vitanyi | Quantum kolmogorov complexity based on classical descriptions[END_REF], in that we use a classical machine and not a quantum machine for the approximation. Let N be the dimension of the Hilbert space.

Hv(|ψ ) = min

Elementary |θ ∈H N K(|θ |N ) -log | ψ|θ | 2 .

Gács Complexity

Gács complexity [G 01] is defined using the following universal lower computable semi-density matrix, parametered by x ∈ {0, 1} * , with

µ x = Eementary |φ ∈H N m(|φ |x, N ) |φ φ|.
The parameter N represents the dimension of the Hilbert space. We use µ X to denote the matrix µ over the Hilbert space denoted by symbol X. The Gács entropy of a mixed state σ, conditioned on x ∈ {0, 1} * is defined by

Hv(σ|x) = -log Trµ x σ .
We use the following notation for pure states, with Hg(|φ |x) = Hg( |φ φ| |x). For empty x we use the notaion Hg(σ). This definition generalizes H in [G 01] to mixed states. Note than in [G 01], there is another measure of quantum algorithmic entropy, H, which we will not cover in this paper. An infinite version of algorithmic entropy can be found at [START_REF] Benatti | Gacs Quantum Algorithmic Entropy in Infinite Dimensional Hilbert Spaces[END_REF].

Properties of Universal Matrix µ and Gács Complexity

The matrix µ is important in algorithmic information theory and quantum mechanics, as it is the foundation for the information term defined in Chapter 5. The following theorem shows that the lower computable semi-density matrix µ is universal. It is greater than any other lower computable matrix, weighted by their complexity. This parallels the classical case, where universal measure m majorizes lower computable semi measure p, with m(x) * > m(p)p(x). This theorem is used throughout the paper, and will not be explicitly cited.

Theorem 4 ([G 01]) Let q ∈ {0, 1} * , and the dimension of the Hilbert space, N , compute lower compute semi-density matrix A. Then µ * > m(q|N )A.

Proof. A can be composed into a sum i p(i) |ψ i ψ i |, where each |ψ i is elementary, p is a semi-measure, with i p(i) ≤ 1, and p is computable from q. Thus since p is computable from q and N ,

A = i p(i) |ψ i ψ i | * < m(p|N ) -1 i m(i|N ) |ψ i ψ i | * < m(q|N ) -1 i m(i|N ) |ψ i ψ i | * < µ/m(q|N ). Theorem 5 ([G 01]) µ ii * = m(i|N ). Proof. The matrix ρ = i m(i|N ) |i i| is lower computable, so ρ * < µ so µ ii * > m(i|N ). Fur- thermore, f (i) = |i µ i| is a lower computable semi-measure, so m(i|N ) * > µ ii . Theorem 6 ([G 01]) Tr Y µ XY * = µ X .
Proof. Let ρ = Tr Y µ XY , which is a lower computable semi-density matrix because one can enumerate elementary pure states |ψ ψ| in the space XY , take their partial trace, Tr T |ψ ψ|, and add the resulting pure or mixed state to the sum ρ. Thus ρ

* < µ X . Let σ = µ X ⊗ |ψ ψ|,
where |ψ is a reference elementary state. Thus σ * < µ XY so

µ X = Tr Y σ * < Tr Y µ XY . Theorem 7 ([G 01]) Hg(σ) < + Hg(σ ⊗ ρ).
Proof. Note that this theorem is not less general than that of Theorem 9, because both σ and ρ can be non-elementary. Using Theorem 6 and the properties of partial trace,

2 -Hg(σ) * > Trσµ X * > TrσTr Y µ XY * > Tr(σ ⊗ I)µ XY * > Tr(σ ⊗ ρ)µ XY * = 2 -Hg(σ⊗ρ) .

No Cloning Theorem

In classical algorithmic information theory, one can easily reproduce a string x, with

K(x) = + K(x, x).
However the situation is much different in the quantum case. Due to the no-cloning theorem, [START_REF] Wootters | A single quantum cannot be cloned[END_REF]

Hg(|ψ ) < + K(P S /M |N m ) -log ψ| 1 M P S /M |ψ < + K(m) + log m + N -1 m .
For the lower bound, let c = max

= m + N -1 m -1 c > + log m + N -1 m .

Addition Inequality

The addition theorem for classical entropy asserts that the joint entropy for a pair of random variables is equal to the entropy of one plus the conditional entropy of the other, with H(X ) + H(Y/X ) = H(X , Y). For algorithmic entropy, the chain rule is slightly more nuanced, with K(x) + K(y|x, K(x)) = + K(x, y). An analogous relationship cannot be true for Gács entropy, Hg, since as shown in Theorem 8, there exists elementary |φ where Hg(|φ |φ ) -Hg(|φ ) can be arbitrarily large, and Hg(|φ / |φ ) = + 0. However, the following theorem shows that a chain rule inequality does hold for Hg.

For n 2 × n 2 matrix A, let A[i, j] be the n × n submatrix of A starting at position (n(i -1) + 1, n(j -1) + 1). For example for n = 2 the matrix

A =    
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    has A[1, 1] = 1 2 5 6 , A[1, 2] = 3 4 7 8 , A[2, 1] = 9 10 13 14 , A[2, 2] = 11 12 15 16 .
For n 2 × n 2 matrix A and n × n matrix B, let M AB be the n × n matrix whose (i, j) entry is equal to TrA[i, j]B. For any n × n matrix C, in can be seen that TrA(C ⊗ B) = TrM AB C. Furthermore if A is lower computable and B is elementary, then M AB is lower computable.

For elementary semi density matrices ρ, we use ρ, Hg(ρ) to denote the encoding of the pair of an encoded ρ and an encoded natural number Hg(ρ).

Theorem 9 ([Eps19a]) For semi-density matrices σ, ρ, elementary ρ, Hg(ρ) + Hg(σ| ρ, Hg(ρ) ) < + Hg(σ ⊗ ρ).

Proof. Let µ 2n be the universal lower computable semi density matrix over the space of 2n qubits,

Q 2n = Q n ⊗Q n = Q A ⊗ Q B .
Let µ n be the universal matrix of the space over n qubits. We define the following bilinear function over complex matrixes of size n × n, with T (ν, δ) = Trµ 2n (ν ⊗ δ). For fixed ρ, T (ν, ρ) is of the form T (ν, ρ) = TrM µ 2n ρ ν. The matrix M µ 2n ρ has trace equal to

TrM µ 2n ρ = T (ρ, I ) = Trµ 2n (ρ ⊗ I) = Tr ((Tr Q B µ 2n )ρ) * = Trµ n ρ * = 2 -Hg(ρ) ,
using Theorem 6, which states Tr Y µ XY * = µ X . By the definition of M , since µ 2n and ρ are positive semi-definite, it must be that M µ 2n ρ is positive semi-definite. Since the trace of M µ 2n ρ is * = 2 -Hg(ρ) , it must be that up to a multiplicative constant, 2 Hg(ρ) M µ 2n ρ is a semi-density matrix.

Since µ is lower computable and ρ is elementary, by the definition of M , 2 Hg(ρ) M µ 2n ρ is lower computable relative to the string ρ, Hg(ρ) . Therefore we have that 2 Hg(ρ) M µ 2n ρ * < µ ρ,Hg(ρ) . So we have that -log Tr2 Hg(ρ) M µ 2n ρ σ = -Hg(ρ) -log T (σ, ρ) = + Hg(σ ⊗ ρ) -Hg(ρ) > + -log µ (ρ,Hg(ρ)) σ = + Hg(σ| ρ, Hg(ρ) ).

Subadditivity, Strong Subadditivity, Strong Superadditivity

Theorem 10 ([G 01]) Hg(σ) is subadditive, with Hg(σ ⊗ ρ) < + Hg(σ) + Hg(ρ).

Proof.

2 -Hg(σ)-Hg(ρ) = (Trµ X σ) (Trµ Y ρ) =Tr(σ ⊗ ρ)(µ X ⊗ µ Y ) * >Tr(σ ⊗ ρ)(µ XY ) * =2 -Hg(σ⊗ρ) .
A function L from quantum mixed states to whole numbers is strongly subadditive if there exists a constant c ∈ N such that for all mixed states ρ 123 , L(ρ 123 ) + L(ρ 2 ) < L(ρ 12 ) + L(ρ 23 ) + c. Similarly L is strongly superadditive if there exists a constant c ∈ N such that for all mixed states ρ 123 , L(ρ 12 ) + L(ρ 23 ) < L(ρ 123 ) + L(ρ 2 ) + c. Theorem 11 Hg is not strongly subadditive.

Proof. We fix the number of qubits n, and for i ∈ [1.. So Hg(ρ 123 ) + Hg(ρ 2 ) > + n and Hg(ρ 12 ) + Hg(ρ 23 ) = + 0, proving that Hg is not strongly subadditive.

Theorem 12 Hg is not strongly superadditive.

Proof. We fix the number of qubits n, and for i ∈ [1..2 n ], |i is the ith basis state of the n qubit space. Let |φ = So Hg(σ 123 ) + Hg(σ 2 ) < + n, and Hg(σ 12 ) + Hg(σ 23 ) > + 2n, proving that Hg is not strongly superadditive.

Relation Between Complexities

Vitányi Complexity and Gács Complexity

By definition Hg(|ψ ) < + Hv(|ψ ). In fact, as shown in the following theorem, Vitányi complexity is bounded with respect to Gács complexity.

Theorem 13 ([G 01]) Hg(|ψ ) < + Hv(|ψ ) < log 4Hg(|ψ ).

Proof. For semi-density matrix A with eigenvectors {|a i } and decreasing eigenvectors {a i } with ψ| A |ψ ≥ 2 -k and |ψ = c i |a i , let A m be a projector onto the m largest eigenvectors. Let m be the first i where a i ≤ 2 -k-1 . Since a i ≤ 1, we have m ≤ 2 k+1 . Since

i≥m a i |c i | 2 < 2 -k-1 i |c i | 2 = 2 -k-1 , we have ψ| A m |ψ ≥ i<m |c i | 2 ≥ i<m a i |c i | 2 ≥ 2 -k - i≥m a i |c i | 2 > 2 -k-1 .
Thus there is some i ≤ m such that

| ψ|a i | 2 ≥ 2 -2k-2 . Let ν = Trµ and ν k ∈ Q be a rational created from the first k digits of ν.
Let μ be a lower approximation of µ, with trace greater than

ν k . So K( μ) < log k. Thus if ψ| µ |ψ ≥ 2 -k , then ψ| μ |ψ ≥ 2 -k-1
. Thus there is an eigenvector

|u of μ of complexity K(|u |N ) < log 2k and | ψ|u | 2 * > 2 -2k , so Hv(|ψ ) ≤ K(|u |N ) -log | ψ|u | 2 < log 4k < log 4Hg(|ψ ).
We now describe an infinite encoding scheme for an arbitrary (not necessarily elementary) quantum pure state |ψ . This scheme is defined as an injection between the set of pure states and {0, 1} ∞ . We define |ψ to be an ordered list of the encoded tuples |θ , q, [| ψ|θ | 2 ≥ q] , over all elementary states |θ and rational distances q ∈ Q >0 . We use the following definition of the mutual information between sequences.

Definition 3 ([Lev74]) For α, β ∈ {0, 1} ∞ , I(α : β) = log x,y∈{0,1} * m(x|α)m(y|β)2 I(x:y) .
The following theorem states that only exotic pure states will have a Vitányi complexity much greater than Gács complexity. States are exotic if they have high mutual information, I, with the halting sequence H ∈ {0, 1} ∞ .

Theorem 14 ([Eps20]) Hg(|ψ ) < + Hv(|ψ ) < log Hg(|ψ ) + I( |ψ : H).
The proof to this theorem is quite extensive. We encourage the readers to review [START_REF] Epstein | An extended coding theorem with application to quantum complexities[END_REF] if they are interested in learning it.

BVL Complexity and Gács Complexity

Theorem 15 ([Eps20]) For pure state |ψ ∈ Q n , Hg(|ψ ) < + Hbvl[ ](|ψ ) + K(Hbvl (|ψ ) - log .
Proof. For each k and t in N, let H k,t be the smallest linear subspace spanning elementary kqubit inputs to the universal quantum Turing machine M of size k that halt in t steps, outputing a n qubit mixed state. As shown in [START_REF] Muller | Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity[END_REF], if t = t , then H k,t is perpendicular to H k,t . Let P k,t be the projection onto H k,t . For each k and t, the universal quantum Turing machine defines a completely positive map Ψ k,t over H k,t , where Ψ k,t (ν) = ρ implies that the quantum Turing machine, with semi-density matrix ν of length k on the input tape will output the n qubit mixed state ρ and halt in time t. Let ρ be a k qubit mixed state that minimizes

k = Hbvl[ ](|ψ ) in time t. ρ ≤ P k,t 2 -k ρ ≤ 2 -k P k,t Ψ k,t 2 -k ρ ≤ Ψ k,t 2 -k P k,t Ψ k,t 2 -k ρ ≤ t Ψ k,t 2 -k P k,t
The semi density matrix t Ψ k,t 2 -k P k,t is lower computable relative to k, so

m(k|N )2 -k Ψ k,t ρ ≤ m(k|N ) t Ψ k,t 2 -k P k,t * < µ m(k|N )2 -k ψ| Ψ k,t (ρ) |ψ * < ψ| µ |ψ k + K(k|N ) -log > + Hg(|ψ ). Theorem 16 ([Eps20]) Hbvl[2 -Hg(|ψ )-O(log Hg(|ψ )) ](|ψ ) < log Hg(|ψ ).
Proof. We use reasoning from Theorem 7 in [G 01]. From Theorem 7 in [START_REF] Epstein | An extended coding theorem with application to quantum complexities[END_REF] there exists a ρ such that K(ρ|N

) -log ψ| ρ |ψ < log Hg(|ψ ). Let -log ψ| ρ |ψ = m. Let |u 1 , |u 2 , |u 3 , . . . be the eigenvectors of ρ with eigenvalues u 1 ≥ u 2 ≥ u 3 . . . For y ∈ N, let ρ y = y i=1 u i |u i u i |.
We expand |ψ in the basis of

{|u i } with |ψ = i c i |u i . So we have that i u i |c i | 2 ≥ 2 -m . Let s ∈ N be the first index i with u i < 2 -m-1 . Since i u i ≤ 1, it must be that s ≤ 2 m+2 . So i≥s u i |c i | 2 < 2 -m-1 i |c i | 2 ≤ 2 -m-1 , ψ| ρ 2 m+2 |ψ ≥ Tr ψ| ρ s |ψ > i<s u i |c i | 2 ≥ 2 -m - i≥s u i |c i | 2 > 2 -m-1 .
We now describe a program to the universal quantum Turing machine that will construct ρ 2 m+2 . The input is an ensemble

{u i } 2 m+2 i=1 of vectors {|cB(i) }, where B(i) is the binary encoding of index i ∈ N which is of length m + 2. Helper code c of size = + K(p|N ) transforms each |cB(i) into |u i . Thus the size of the input is < + K(p|N ) + m < log Hg(|ψ ). The fidelity of the approximation is ψ| ρ 2 m+2 |ψ > 2 -m-1 ≥ 2 -Hg(|ψ )-O(log Hg(|ψ )) .

Quantum EL Theorem

In this paper we prove a Quantum EL Theorem. In AIT, the EL Theorem [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF] states that sets of strings that contain no simple member will have high mutual information with the halting sequence.

Theorem 17 ([Lev16, Eps19c]) For finite set D ⊂ {0, 1} * , min x∈D K(x) < log -log x∈D m(x) + I(D; H).
It has many applications, including that all sampling methods produce outliers [START_REF] Epstein | All sampling methods produce outliers[END_REF]. The Quantim EL Theorem states that non exotic projections of large rank must have simple quantum pure states in their images. By non exotic, we mean the coding of the projection has low information with the halting sequence. The Quantum EL Theorem has the following consequence.

Claim. As the von Neumann entropy associated with the quantum source increases, the lossless quantum coding projectors have larger rank and thus must have simpler (in the algorithmic quantum complexity sense) pure states in their images.

Theorem 18 (Quantum EL Theorem [START_REF] Epstein | A quantum el theorem[END_REF]) Fix an n qubit Hilbert space. Let P be a elementary projection of rank > 2 m . Then, relativized to (n, m), min |φ ∈Image(P ) Hv(|φ ) < log 3(n -m) + I( P ; H).

Proof. We assume P has rank 2 m . Let Q be the elementary probability measure that realized the stochasticity, Ks(P ), of an encoding of P . We can assume that every string in the support of Q encodes a projection of rank 2 m . We sample N independent pure states according to the uniform distribution Λ on the n qubit space. For each pure state |ψ i and projection R in the support of Q, the expected value of

ψ i | R |ψ i is ψ i | R |ψ i dΛ = TrR |ψ i ψ i | dΛ = 2 -n TrRI = 2 m-n . Let random variable X R = 1 N N i=1 ψ i | R |ψ i be
the average projection size of the random pure states onto the projection R. Since

ψ i | R |ψ i ∈ [0, 1] with expectation 2 m-n , by Hoeffding's inequality, Pr(X R ≤ 2 m-n-1 ) < exp -N 2 -2(m-n)-1 Let d = d(P |Q). Thus if we set N = d2 2(m-n)+1 , we can find N elementary n qubit states such that Q({R : X R ≤ 2 m-n-1 }) ≤ exp(-d)
, where X R is now a fixed value and not a random variable. Thus X P > 2 m-n-1 otherwise one can create a Q-expectation test, t, such that t(R) = exp d. This is a contradiction because 1.44d < + log(P )

< + d(P |Q) < + d,
for large enough d which we can assume without loss of generality. Thus there exists i such that

ψ i | P |ψ i ≥ 2 m-n-1 . Thus |φ = P |ψ i / ψ i | P |ψ i is in the image of P and | ψ i |φ | 2 = ψ i | P |ψ i ≥ 2 m-n-1 . The elementary state |ψ i has classical Kolmogorov complexity K(|ψ i ) < log log N + K(Q, d) < log 2(m -n) + Ks(P ). Thus by Lemma 3, min{Hv(|ψ ) : |ψ ∈ Image(P )} ≤ Hv(|φ ) < log K(|ψ i ) + | ψ i |φ | 2 < log 3(n -m) + Ks(P )
< log 3(n -m) + I(P ; H).

Computable Projections

Theorem 23 is in terms of elementary described projecctions and can be generalized to arbitrarily computable projections. For a matrix M , let M = max i,j |M i,j | be the max norm. A program p ∈ {0, 1} * computes a projection P of rank if it outputs a series of rank projections {P i } ∞ i=1 such that P -P i ≤ 2 -i . For computable projection operator P , I(P ; H) = min{K(p) -K(p|H) : p is a program that computes P }.

Corollary 1 ([Eps23b]

) Fix an n qubit Hilbert space. Let P be a computable projection of rank > 2 m . Then, relativized to (n, m), min |φ ∈Image(P ) Hv(|φ ) < log 3(n -m) + I(P ; H).

Proof. Let p be a program that computes P . There is a simply defined algorithm A, that when given p, outputs P n such that min |ψ ∈Image(P ) Hv(|ψ ) = + min |ψ ∈Image(Pn) Hv(|ψ ). Thus by Lemma 1, one gets that I(P n ; H) < + I(P ; H). The corollary follows from Theorem 23.

Quantum Data Compression

A quantum source consists of a set of pure quantum states {|ψ i } and their corresponding probabilities {p i }, where i p i = 1. The pure states are not necessarily orthogonal. The sender, Alice wants to send the pure states to the receiver, Bob. Let ρ = i p i |ψ i ψ i | be the density matrix associated with the quantum source. Let S(ρ) be the von Neumann entropy of ρ. By Schumacher compression, [START_REF] Schumacher | Quantum coding[END_REF], in the limit of n → ∞, Alice can compress n qubits into S(ρ)n qubits and send these qubits to Bob with fidelity approaching 1. For example, if the message consists of n photon polarization states, we can compress the inital qubits to nS(ρ) photons. Alice cannot compress the initial qubits to n(S(ρ) -δ) qubits, as the fidelity will approach 0. The qubits are compressed by projecting the message onto a typical subspace of rank nS(ρ) using a projector P . The projection occurs by using a quantum measurement consisting of P and a second projector (I -P ), which projects onto a garbage state.

The results of this paper says that as S(ρ) increases, there must be simple states in the range of P . There is no way to communicate a quantum source with large enough S(ρ) without using simple quantum states.

Chapter 4

Quantum Typicality

Definition of Quantum Randomness Deficiency

In [G 01], the quantum notion of randomness deficiency was introduced. This quantum randomness deficiency measures the algorithmic atypicality of a pure or mixed quantum state ρ with respect to a second quantum mixed state σ. Mixed states σ are used to model random mixtures {p i } of pure states {|ψ i }, so quantum randomness deficiency is a score of how atypical a quantum state is with respect to a mixture. We first describe typicality with respect to computable σ, and then generalize to uncomputable σ. Given a density matrix σ, a σ-test is a lower computable matrx T such that TrT σ = 1. Let T σ be the set of all σ-tests. If σ is computable, there exists a universal σ test t σ , that is lower computable relative to the number of qubits n, Trσt σ ≤ 1, and for every lower computable σ test

T , O(1)t σ > m(T |σ)T .
This universal test can be computed the following manner, analagously to the classical case (see [G 21]). A program enumerates all strings p and lower computes m(p|σ). The program then runs p and continues with the outputs as long as p outputs a series of positive semi-definite matrices T i such that TrT i σ ≤ 1 and T i ≤ T i+1 . If p outputs something other than this sequence or does not halt, the sequence is frozen. t σ = p m(p|σ) lim i T i is the weighted sum of all such outputs of progams p.

Definition 4 (Quantum Randomness Deficiency) For mixed states σ and ρ, computable σ, d(ρ|σ) = log Tr t σ ρ.

The quantum randomness deficiency, among other interpretations, is score of how typical a pure state is with respect to an algorithmically generated quantum source. Indeed, suppose there is a computable probability P over encodings of elementary orthogonal pure states { |ψ i } of orthogonal pure states {|ψ i }, with corresponding density matrix σ = Proof. The positive semi-definite matrix

i P ( |ψ i ) |ψ i ψ i |. Then there is a lower-computable σ-test T = i 2 d( |ψ i |P ) |ψ i ψ i | with O(1)t σ > T . Thus d(|ψ i |σ) > + d( |ψ i |P ),
T = i 2 d(i|p) |i i| is a σ-test, so T * < t σ and thus d(|i |σ) > + log i| T |i = + d(i|p). The function t(i) = i| t σ |i is a lower computable p-test, so d(i|P ) > + d(|i |σ).
The following theorem shows that randomness deficiency d(ρ|σ) parallels the classical definition of randomness decificiency, d(x|P ) = log m(x)/P (x).

Theorem 20 ([G 01]) Relativized to elementary σ, log d(ρ|σ) = + log Trρσ -1/2 µσ -1/2 σ Proof. The matrix σ 1/2 t σ σ 1/2 is a lower-computable semi density matrix, so

t σ * < σ -1/2 µσ -1/2 . This implies Trt σ ρ * < Trρσ -1/2 µσ -1/2 .

Uncomputable Mixed States

We now extend d to uncomputable σ. For uncomputable σ, T σ is not necessarily enumerable, and thus a universal lower computable randomness test does not necessarily exist, and cannot be used to define the σ deficiency of randomness. So in this case, the deficiency of randomness is instead defined using an aggregation of σ-tests, weighted by their lower algorithmic probabilities. The lower algorithmic probability of a lower computable matrix σ is m(σ|x) = {m(q|x) : q lower computes σ}. Let T σ = ν∈Tσ m(ν|n)ν. Proof.

d(σ|ρ) + d(ν|ξ) = log Tr ρ ∈Tρ m(ρ )ρ σ + log Tr ξ ∈T ξ m(ξ )ξ ν = log Tr     ρ ∈Tρ m(ρ )ρ   ⊗   ξ ∈T ξ m(ξ )ξ     (σ ⊗ ν) = log Tr   ρ ∈Tρ,ξ ∈T ξ m(ρ )m(ξ )ρ ⊗ ξ   (σ ⊗ ν) < + log Tr   ρ ∈Tρ,ξ ∈T ξ m(ρ ⊗ ξ )ρ ⊗ ξ   (σ ⊗ ν) < + log Tr   κ∈T ρ⊗ξ m(κ)κ   (σ ⊗ ν) = + d(σ ⊗ ν|ρ ⊗ ξ).

Conservation Over Quantum Operations

Proposition 1 For semi-density matrix ν, relativized to a finite set of elementary matrices {M i },

m( i M * i νM i |N ) * > m(ν|N ).
Proof. For every string q that lower computes ν, there is a string q M of the form rq, that lower computes i M * i νM i . This string q M uses the helper code r to take the intermediary outputs ξ i of q and outputs the intermediary output i M * i ξ i M i . Since q M has access to {M i } on the auxilliary tape, m(q

M |N ) * > m(q|N ). m(ν|N ) = {m(q|N ) : q lower computes ν} * < {m(q M |N ) : q lower computes ν} * < {m(q |N ) : q lower computes i M * i νM i } * <m i M * i νM i /n .
The following theorem shows conservation of randomness with respect to elementary quantum operations. It generalizes Theorems 2 and 3 from [START_REF] Epstein | On the algorithmic probability of sets[END_REF].

Theorem 22 (Randomness Conservation) Relativized to elementary quantum operation ε, for semi-density matrices ρ, σ, d(ε(ρ)|ε(σ)) < + d(ρ|σ).

Proof. Since the universal Turing machine is relativized to ε, there is an elementary Kraus operator {M i } that can be computed from ε where ε(ξ

) = i M i ξM * i . If ν is a i M i ρM * i -test, with ν ∈ T i M i ρM * i , then i M * i νM i is a ρ-test, with i M * i νM i ∈ T ρ . This is because by assumption Trν i M i ρM * i ≤ 1. So by the cyclic property of trace Tr i M * i νM i ρ ≤ 1. Therefore since i M * i νM i is lower computable, i M * i νM i ∈ T ρ . From Proposition 1, m( i M * i νM i |n) * > m(

ν|n). So we have the following inequality

d i M i σM * i | i M i ρM * i = log ν∈T i M i ρM * i m(ν|N )Trν i M i σM * i < + log ν∈T i M i ρM * i m i M * i νM i |N Tr i M * i νM i σ < + d(σ|ρ).

A Quantum Outlier Theorem

One recent result in the classical randomness deficiency case is that sampling methods produce outliers [START_REF] Epstein | All sampling methods produce outliers[END_REF]. There are several proofs to this result, with one of them derived from the fact that large sets of natural numbers with low randomness deficiencies are exotic, in that they have high mutual information with the halting sequence.

In this paper, we prove a quantum version of this result. Projections of large rank must contain pure quantum states in their images that are outlying states. Otherwise, the projections are exotic, in that they have high mutual information with the halting sequence. Thus quantum coding schemes that use projections, such as Schumacher compression, must communicate using outlier quantum states. The classical and quantum theorems are analogous, but their proofs are very different! Theorem 23 ( [START_REF] Epstein | A quantum outlier theorem[END_REF]) Relativized to an n qubit mixed state σ, for elementary 2 m rank projector P , 3m -2n < log max |φ ∈Image(P ) d(|φ |σ) + I( P ; H).

Proof. We relativize the universal Turing machine to σ and (3m -2n). Thus it is effectively relativized to m, n, and σ. Let elementary probability measure Q and d ∈ N realize Ks(P ), where d = max{d(P |Q), 1}. Without loss of generality we can assume that the support of Q is elementary projections of rank 2 m . There are d2 n-m+2 rounds. For each round we select an σ-test T , that is of dimension 1, TrσT ≤ 1, and for a certain Q-probability of projections B, TrT B is large. We now describe the selection process.

Select a random test T to be 2 m-2 |ψ ψ|, where |ψ is an n qubit state chosen uniformly from the unit sphere, with distribution Λ.

E[TrT σ] = 2 m-2 Tr ψ| σ |ψ dΛ = 2 m-2 Trσ |ψ ψ| dΛ = 2 m-n-2 Trσ = 2 m-n-2 .
Thus the probability that T is a σ-test is ≥ 1 -2 m-n-2 . Let I m be an n-qubit identity matrix with only the first 2 m diagonal elements being non-zero. Let K m = I -I m . Let p = 2 m-n and T = T /2 m-2 . For any projection B of rank 2 m , Pr(TrB T ≤ .5p)

= Pr(TrI m T ≤ .5p) = Pr(TrK m T ≥ 1 -.5p) E[TrK m T ] = 1 -p Pr(TrK m T ≥ 1 -.5p) ≤ (1 -p)/(1 -.5p) Pr(TrB T ≥ .5p) = 1 -Pr(TrK m T ≥ 1 -.5p) ≥ 1 -(1 -p)/(1 -.5p) = .5p/(1 -.5p) ≥ .5p Pr(TrBT ≥ 2 2m-n-3 ) ≥ .5p.
Let Ω be the space of all matrices of the form 2 m-2 |φ φ|. Let R be the uniform distribution over Ω. Let [A, B] be 1 if TrAB > 2 2m-n-3 , and 0 otherwise. By the above equations, for all

A ∈ Support(Q), Ω [A, B]dR(B) ≥ .5p. So A Ω [A, B]Q(A)dR(B) ≥ .5p. For Hermitian matrix A, {A} is 1 if TrAσ ≤ 1, and 0 otherwise. So Ω {A}dR(A) ≥ (1 -p2 -2 ). Let f = max T {T } Q(A)[T, A]. So .5p ≤ A Ω [A, B]Q(A)dR(B) = A Ω {B}Q[A, B](A)dR(B) + A Ω (1 -{B})[A, B]Q(A)dR(B) ≤ A Ω {B}[A, B]Q(A)dR(B) + Ω (1 -{B})dR(B) ≤ A Ω {B}[A, B]Q(A)dR(B) + p2 -2 p/4 ≤ A Ω {B}[A, B]Q(A)dR(B) = Ω {B} A [A, B]Q(A) dR(B) ≤ Ω f dR(B) p/4 ≤ f.
Thus for each round i, the lower bounds on f proves there exists a one dimensional matrix

T i = 2 m-2 |ψ ψ| such that TrT i σ ≤ 1 and R {Q(R) : TrT i R ≥ 2 2m-n-3 } ≥ p/4 = 2 m-n-2 .
Such a T i is selected, and the the Q probability is conditioned on those projections B for which [T i , B] = 0, and the next round starts. Assuming that there are d2 n-m+2 rounds, the Q measure of projections B such there does not exist a

T i with [T i , B] = 1 is ≤ (1 -p/4) d2 n-m+2 ≤ e -d .
Thus there exists a T i such that [T i , P ] = 1, otherwise one can create a Q test t that assigns e d to all projections B where there does not exist T i with [T i , B] = 1, and 0 otherwise. Then t(P ) = e d so 1.44d < log t(P )

< + d(P |Q) < + d.
d(P |σ) + K(T i ) 2m -n < + max |φ ∈Image(P ) d(P |σ) + (n -m) + log d + K(d) + K(Q) 2m -n < + max |φ ∈Image(P ) d(P |σ) + (n -m) + Ks(P ) 3m -2n < log max |φ ∈Image(P ) d(P |σ) + I(P ; H).
Note that due to the fact that the left hand side of the equation is (3m-2n) and it has log precision, this enables one to condition the universal Turing machine to (3m -2n). Chapter 5

Computable Projections

Quantum Information

Definition of Quantum Algorithmic Information

For a pair of random variables, X , Y, their mutual information is defined to be

I(X : Y) = H(X ) + H(Y) -H(X , Y) = H(X ) -H(X /Y) =
x,y p(x, y) log p(x, y)/p(x)p(y). This represents the amount of correlation between X and Y. Another intrepretation is that the mutual information between X and Y is the reduction in uncertainty of X after being given access to Y. Quantum mutual information between two subsystems described by states ρ A and ρ B of a composite system described by a joint state ρ AB is I(A : B) = S(ρ A ) + S(ρ B ) -S(ρ AB ), where S is the Von Neumman entropy. Quantum mutual information measures the correlation between two quantum states.

As stated in Chapter 2, The algorithmic information between two strings is defined to be I(x : y) = K(x) + K(y) -K(x, y). By definition, it measures the amount of compression two strings achieve when grouped together.

The three definitions above are based off the difference between a joint aggregate and the separate parts. Another approach is to define information between two semi-density matrices as the deficiency of randomness over µ ⊗ µ, with the mutual information of σ and ρ being d(σ ⊗ ρ|µ ⊗ µ). This is a counter argument for the hypothesis that the states are independently chosen according to the universal semi-density matrix µ. This parallels the classical algorithmic case, where I(x : y) = + d((x, y)|m ⊗ m) = + K(x) + K(y) -K(x, y). However to achieve the conservation inequalities, a further refinement is needed, with the restriction of the form of the µ ⊗ µ tests. Let C C⊗D be the set of all lower computable matrices A ⊗ B, such that Tr

(A ⊗ B)(C ⊗ D) ≤ 1. Let C C⊗D = A⊗B∈C C⊗D m(A ⊗ B|N )A ⊗ B.
Definition 6 (Information) The mutual information between two semi-density matrices σ, ρ is defined to be I(σ : ρ) = log TrC µ⊗µ (σ ⊗ ρ).

Up to an additive constant, information is symmetric.

Theorem 24 I(σ : ρ) = + I(ρ : σ).

Proof. This follows from the fact that for every A ⊗ B ∈ C µ⊗µ , the matrix B ⊗ A ∈ C µ⊗µ . Furthermore, since m(A⊗B|N ) * = m(B ⊗A|N ), this guarantees that TrC µ⊗µ (σ ⊗ρ) * = TrC µ⊗µ (ρ⊗ σ), thus proving the theorem.

Paucity of Self-Information

Pure States

For classical algorithmic information, for all x ∈ {0, 1} * ,

I(x : x) = + K(x).
As shown in this section, this property differs from the quantum case, where there exists quantum states with high descriptional complexity and negligible self information. In fact this is the case for most quantum states, where for most n qubit pure states |ψ ,

Hg(|ψ ) ≈ n, I(|ψ : |ψ ) ≈ 0.
The following theorem states that the information between two elementary states is not more than the combined length of their descriptions.

Theorem 25 For elementary ρ and σ, I(ρ : σ) < + K(ρ|N ) + K(σ|N ).

< + 0.

Mixed States

The results of the previous section can be extended to mixed states. Given a uniform measure over mixed states, an overwhelming majority of such states contain no algorithmic self information.

Let Λ be the uniform distribution of the unit sphere of

H N . Fix any number M ∈ N. Let the M -simplex be ∆ M = {(p i ) 1≤i≤M |p i ≥ 0, p 1 + • • • + p M = 1}.
Let η be any distribution over ∆ M . Let

µ M i=1 p i |ψ i ψ i | = η(p 1 , . . . , p M ) M i=1 Λ(|ψ i ),
Theorem 27 2 I(σ:σ) dµ(σ) < + 0.

Proof.

2 I(σ:σ) dµ(σ)

=TrC µ⊗µ ∆ M Λ 1 • • • Λ M M i=1 p i |ψ i ψ i | ⊗ M i=1 p i |ψ i ψ i | dΛ 1 . . . dΛ M dη(p 1 , . . . , p M ) =TrC µ⊗µ ∆ M Λ 1 • • • Λ M   M i,j=1 p i p j |ψ i ψ i | ⊗ |ψ j ψ j |   dΛ 1 . . . dΛ M dη(p 1 , . . . , p M ) =TrC µ⊗µ ∆ M Λ M i=1 p 2 i |ψψ ψψ| dΛdη(p 1 , . . . , p M ) + TrC µ⊗µ ∆ M Λ 1 Λ 2 i,j∈{1,...,M },i =j 2p i p j |ψ 1 ψ 1 | ⊗ |ψ 2 ψ 2 | dΛ 1 dΛ 2 dη(p 1 , . . . , p M ).
The first term is not greater than

TrC µ⊗µ ∆ M Λ M i=1 |ψψ ψψ| dΛdη(p 1 , . . . , p M ) =TrC µ⊗µ Λ M i=1
|ψψ ψψ| dΛ.

At this point, reasoning from the proof of Theorem 26 can be used to show that this term is O(1).

The second term is not greater than

TrC µ⊗µ ∆ M Λ 1 Λ 2 i p i i p i |ψ 1 ψ 1 | ⊗ |ψ 2 ψ 2 | dη(p 1 , . . . , p M ) =TrC µ⊗µ ∆ M Λ 1 Λ 2 |ψ 1 ψ 1 | ⊗ |ψ 2 ψ 2 | dη(p 1 , . . . , p M ) =TrC µ⊗µ Λ 1 Λ 2 |ψ 1 ψ 1 | ⊗ |ψ 2 ψ 2 | =TrC µ⊗µ (I/N ⊗ I/N ).
Again, at this point, reasoning from the proof of Theorem 26 can be used to show that this term is O(1).

Information Nongrowth

Classical algorithmic information non-growth laws asserts that the information between two strings cannot be increased by more than a constant depending on the computable transform f , with I(f (x) : y) < I(x : y) + O f (1) (Theorem 2). Conservation inequalities have been extended to probabilistic transforms and infinite sequences. The following theorem shows information non-growth in the quantum case; information cannot increase under quantum operations, the most general type of transformation that a mixed or pure quantum state can undergo. The following theorem shows information nongrowth with respect to elementary quantum operations. It generalizes Theorems 5 and 10 from [START_REF] Epstein | On the algorithmic probability of sets[END_REF].

Theorem 28 (Information Conservation) Relativized to elementary quantum operation ε, for semi-density matrices ρ, σ, I(ε(ρ) : σ) < + I(ρ : σ).

Proof. Since the universal Turing machine is relativized to ε, there is an elementary Kraus operator {M i } that can be computed from ε where ε(ξ

) = i M i ξM * i . Given density matrices A, B, C and D, we define d (A ⊗ B|C ⊗ D) = log C C⊗D A ⊗ B. Thus I(σ : ρ) = d (σ ⊗ ρ|µ ⊗ µ).

The semi-density matrix

i M i µM * i is lower semicomputable, so therefore i M i µM * i * < µ and also ( i M i µM * i ⊗ µ) C ( i M i µM * i )⊗µ . So we have d i M i σM * i ⊗ ρ|µ ⊗ µ = log E⊗F ∈C µ⊗µ m(E ⊗ F |N )Tr(E ⊗ F )( i M i σM * i ⊗ ρ) < + log E⊗F ∈C µ⊗µ m(c(E ⊗ F )|N )Trc(E ⊗ F ) i M i σM * i ⊗ ρ < + d i M i σM i * ⊗ ρ| i M i µM * i ⊗ µ .
Using the reasoning of the proof of Theorem 22 on the elementary Kraus operator {M i ⊗ I} and d , where C replaces T , we have that

d i M i σM * i ⊗ ρ| i M i µM * i ⊗ µ < + d (σ ⊗ ρ|µ ⊗ µ).
Therefore we have that

I i M i σM * i : ρ = d i M i σM * i ⊗ ρ|µ ⊗ µ < + d i M i σM * i ⊗ ρ| i M i µM * i ⊗ µ < + d (σ ⊗ ρ|µ ⊗ µ) = + I(σ : ρ).

Algorithmic No-Cloning Theorem

The no-cloning theorem states that every unitary transform cannot clone an arbitrary quantum state. Hiowever some unitary transforms can clone a subset of pure quantum states. For example, given basis states |1 , |2 , |3 , . . . there is a unitary transform that transforms each |i |0 to |i |i . In addition, there exists several generalizations to the no-cloning theorem, showing that imperfect clones can be made. In [START_REF] Buzek | Quantum copying: Beyond the no-cloning theorem[END_REF], a universal cloning machine was introduced that can clone an arbitrary state with the fidelity of 5/6. Theorem 8 shows a generalization of the no-cloning theorem using Gács complexity. Given the information function introduced in this chapter, a natural question to pose is whether a considerable portion of pure states can use a unitary transform to produce two states that share a large amount of shared information. The following theorem answers this question in the negative. It states that the amount of information created between states with a unitary transform is bounded by the self information of the original state. Proof. We have the inequalities

I(|φ : |ϕ ) < + I(|φ |ϕ ) : |φ |ϕ ) < + I(|ψ |0 n : |ψ |0 n ) < + I(|ψ : |ψ ),
where the first inequality is derived using partial trace, the second inequality is derived using the unitary transform C, and the third inequality is derived by appending of an environment, all constituting quantum operations, whose conservation of information is proven in Theoerem 28.

Theorem 29, combined with the paucity of self-information in pure states (Theorem 26) shows that only a very sparse set of pure states can, given any unitary transform, duplicate algorithmic information.

Purification

Every mixed state can be considered a reduced state of a pure state. The purification process is considered physical, so the extended Hilbert space in which the purified state resides in can be considered the existing environment. It should therefore be possible to regard our system with its mixed state as part of a larger system in a pure state. In this section we proof that the purifications of two mixed states will contain more information than the reduced states.

Purification occurs in the following manner, starting with a density matrix ρ = n i=1 p i |i i|. A copy of the space is defined with orthonormal basis {|i }. In this instance the purification of ρ is |ψ = n i=1 √ p i |i ⊗ |i . For a density matrix ρ of size n, let P m ρ be the set of purifications of ρ of dimension m ≥ 2n.

Corollary 3 For all |ψ σ ∈ P n σ , |ψ ρ ∈ P n ρ , d(σ|ρ) < + d(|ψ σ | |ψ ρ ).
Corollary 4 For all |ψ σ ∈ P n σ , |ψ ρ ∈ P n ρ , I(σ : ρ) < + I(|ψ σ : |ψ ρ ). This all follows from conservation of randomness (Theorem 22) and information (Theorem 28) over quantum operations, which includes the partial trace function.

Decoherence

In quantum decoherence, a quantum state becomes entangled with the environment, losing decoherence. The off diagonal elements of the mixed state become dampened, as the state becomes more like a classical mixture of states.

The single qubit example is as follows. The system is in state

|ψ Q = α |0 + β |1 and the environment is in state |ψ E . The initial state is |ψ QE |ψ Q ⊗ |ψ E = α |0, ψ E + β |1, ψ E .
The combined system undergoes a unitary evolution U , becoming entangled, with the result

U |ψ QE = α |0, E 1 +β |1, E 2 . The density matrix is ρ QE = |α| 2 |0, E 1 0, E 1 |+|β| 2 |1, E 2 1, E 2 |+ α * β |1, E 2 0, E 1 | + αβ * |0, E 1 1, E 2 |.
The partial trace over the environment yields

ρ Q = |α| 2 |0 0| E 1 |E 1 + |β| 2 |1 1| E 2 |E 2 + α * β |1 0| E 2 |E 1 + αβ * |0 1| E 1 |E 2 .
We have E 1 |E 1 = E 2 |E 2 = 1. Two environment-related terms are time dependent and can be described by an exponential decay function

E 1 |E 2 = e -γ(t) .
The larger the decay, the more off diagonal terms are suppressed. So

ρ Q ≈ |α| 2 α * βe -γ(t) αβ * e -γ(t)
|β| 2 .

The above example can be generalzied to n qubit density matrices. Let Decohere(σ, t) be a decoherence operation that dampens the off-diagonal elements of σ with decay t. By definition, Decohere is a quantum operation. Randomness is conserved over decoherence. Thus if two states decohere, the first state does not increase in algorithmic atypicality with respect to the second state.

Corollary 5 d(Decohere(σ, t)|Decohere(ρ, t)) < + d(σ|ρ).

This is a corollary to Theorem 22. When a state loses coherence into the environment will not gain information with any other state.

Corollary 6 For semi-density matrices σ and ρ, I(Decohere(σ, t) : Decohere(ρ, t)) < + I(σ : ρ).

Chapter 6

Quantum Measurements

In quantum mechanics, measurements are modeled by POVMs. A POVM E is a finite or infinite set of positive definite matrices {E k } such that k E k = I. For a given semi-density matrix σ, a POVM E induces a semi measure over integers, where Eσ(k) = TrE k σ. This can be seen as the probability of seeing measurement k given quantum state σ and measurement E. An elementary POVM E has a program q such that U (q) outputs an enumeration of {E k }, where each E k is elementary. A quantum instrument with respect to POVM E, is a quantum operation Φ E that takes a state σ to a set of outcomes and their probabilities, Φ E (σ) = k E(σ(k)) |k k|.

Typicality and Measurements

Theorem 30 shows that measurements can increase only up to a constant factor, the deficiency of randomness of a quantum state with respect to another quantum state. The classical deficiency of randomness of a probability with respect to a another probability is denoted as follows.

Definition 7 (Deficiency, probabilities (Folkflore)) For probabilities p and q over {0, 1} ∞ , d(q|p) = log x q(x)m(x)/p(x).

Note that in the following theorem, d(Eσ|Eρ) term represents the classical deficiency of randomness of a semimeasure Eσ with respect to a computable probability measure Eρ,.

Theorem 30 ( [START_REF] Epstein | Algorithmic no-cloning theorem[END_REF]) For density matrices σ, ρ, relativized to elementary ρ and POVM E,

d(Eσ|Eρ) < + d(σ|ρ). Proof. 2 d(Eσ|Eρ) = k (TrE k σ)m(k|N )/(TrE k ρ) = Tr( k (m(k|N )/TrE k ρ)E k )σ = Trνσ, where the matrix ν = ( k (m(k|N )/TrE k ρ)E k ) has ν ∈ T ρ , since ν is lower computable and Trνρ ≤ 1. So 2 d(σ|ρ) ≥ m(ν|N )Trνσ = m(ν|N )2 d(Eσ|Eρ) . Since m(ν|N ) * > 1, d(Eσ|Eρ) < + d(σ|ρ).

Information and Measurements

Given two mixed states σ and ρ and POVM E, the mutual information between the probabilities of Eσ and Eρ, from Definition 1, is I Prob (Eσ : Eρ). The following theorem states that given two states, the classical (algorithmic) information between the probabilities generated by two quantum measurements is less, up to a logarithmic factor, than the information of the two states. Thus I represents an upper bound on the amount of classical algorithmic information that can be extracted between two states.

Theorem 31 Relative to POVMS E and F , I Prob (Eσ : F ρ) < log I(σ : ρ).

Note than since the universal Turing machine is relativized to E and F , all K and m are conditioned to the number of qubits N . Quantum instruments with respect to POVMs E and F produces two mixed states Ψ E (σ) = m i=1 E i (σ) |i i| and Ψ F (ρ) = m j=1 F j (ρ) |j j|, where, without loss of generality, m can be considered a power of 2. By Theorem 5, the (i, i)th entry of µ is * = m(i), so T ij = 2 K(i)+K(j)-O(1) |i i| |j j| is a µ ⊗ µ test, with TrT i,j (µ ⊗ µ) < 1. So, using the fact that x/ log x is convex,

I(σ : ρ) > + I(Ψ E (σ) : Ψ F (ρ)) > + log i,j m(T i,j )T i,j Ψ E (σ) ⊗ Ψ F (ρ) > + log i,j 2 K(i)+K(j) m(i, j, K(i) + K(j))E i (σ)F j (ρ) > + log i,j
2 I(i:j)-K(I(i:j)) E i (σ)F j (ρ)

> + log i,j 2 I(i:j) I(i : j) -O(1) E i (σ)F j (ρ) > log log i,j 2 I(i:j) E i (σ)F j (ρ) > log I Prob (Eσ : F ρ).
Corollary 7 For density matrices ρ and σ, and i, j ∈ N, relativized to POVMS E and F , I(i : j) + log E i (ρ)F j (σ) < log I(ρ : σ).

Algorithmic Contents of Measurements

This sections shows the limitations of the algorithmic content of measurements of pure quantum states. Theorem 32 says that given a measurement apparatus E, the overwhelming majority of pure states, when measured, will produce classical probabilities with no self-information, i.e. random noise. Theorem 3 shows that there is no randomized way to process the probabilities to produce more self-information, i.e. process the random noise. This is independent of the number of measurement outcomes of E.

To prove this result, we need to define an upper-information term I that is defined using upper computable tests. We say a semi-density matrix ρ is upper computable if there a program q ∈ {0, 1} * such that when given to the universal Turing machine U , outputs, with or without halting, a finite or infinite sequence of elementary matrices ρ i such that ρ i+1 ρ i and lim i→∞ ρ i = ρ. If U reads ≤ q bits on the input tape, then we say p upper computes ρ. The upper probability of an upper computable mixed state σ is defined by m(σ/x) = {m(q/x) : q upper computes σ}.

Let G C⊗D be the set of all upper computable matrices (tests) of the form A ⊗ B, where Lemma 4

Tr(A ⊗ B)(C ⊗ D) ≤ 1. Let G C⊗D = A⊗B∈C C⊗D m(A ⊗ B/n)(A ⊗ B)
• Let Λ be the uniform distribution on the unit sphere of an n qubit space.

2 I(|ψ : |ψ ) dΛ = O(1),

• 2 I(σ : σ) dµ(σ) = O(1).

Proof. The proof follows identically to that of Theorems 26 and 27, with reference to Proposition 2.

Lemma 5 ([Eps21a]) Relativized to POVM E, I Prob (Eσ:Eσ) < + I(σ:σ).

Proof. Note that all complexity terms are relativized to N , due to the relativization of E.

Since z(k) = TrµE k is lower semi-computable and k z(k) < 1, m(k) * > TrµE k , and so 1 > 2 K(k)-O(1) TrµE k . So ν i,j = 2 K(i)+K(j)-O(1) (E i ⊗ E j ) ∈ G µ⊗µ , with m(ν i,j ) * > m(i, j). I(σ:σ) = log A⊗B∈G µ⊗µ m(A ⊗ B)(A ⊗ B)(σ ⊗ σ) > + log Tr ij ν i,j m(ν i,j )(σ ⊗ σ) > + log 2 K(i)+K(j) m(i, j)Eσ(i)Eσ( (j)
> + I Prob (Eσ:Eσ).

Theorem 32 ([Eps21a]) Let Λ be the uniform distribution on the unit sphere of an n qubit space. Relativized to POVM E, 2 I Prob (E|ψ :E|ψ ) dΛ = O(1).

Proof. By Lemma 5, 2 I(|ψ :|ψ ) * > 2 I Prob (E|ψ :E|ψ ) . From Lemma 4, 2 I(|ψ :|ψ ) dΛ = O(1). The integral 2 I Prob (E|ψ :E|ψ ) dΛ is well defined because 2 I Prob (E|ψ :E|ψ ) = Tr i,j m(i, j)ν i,j (|ψ ψ| ⊗ |ψ ψ|), for some matrices ν i,j which can be integrated over Λ.

Theorem 33 Relativized to POVM E, 2 I Prob (Eσ:Eσ) dµ(σ) = O(1).

Proof. By Lemma 5, 2 I(σ:σ) * > 2 I Prob (Eσ:Eσ) . From Lemma 4, 2 I(σ:σ) dµ(σ) = O(1).

An implication of Theorems 32 and 33 is that for an overwhelming majority of quantum states, the probabilities induced by a measurement will have negligible self information.

Algorithmic Content of Decoherence

Decoherence was explained in Section 5.3.3. In the idealized case, decoherence transforms an arbitrary density matrix σ into a classical probability, with the off-diagonal terms turned to 0. Let p σ be the classical probability that σ decoheres to, with p σ (i) = σ ii . The following corollary to Theorem 32, for an overwhelming majority of pure or mixed states σ, p σ is noise, that is, has negligible self-information. The corollary follows from the fact that there is a POVM E, where

E i = |i i| with E i |ψ = p |ψ (i).
Corollary 8 Let Λ be the uniform distribution on the unit sphere of an n qubit space.

• 2 I Prob( p |ψ :p |ψ ) dΛ = O(1),

• 2 I Prob (pσ:pσ) dµ(σ) = O(1).

PVMs

Quantum measurements is also of the form of PVMs, or projection value measures. A PVM P = {Π i } is a collection of projectors Π i with i Π i = I, and TrΠ i Π j = 0 when i = j. When a measurement occurs, with probability ψ| Π i |ψ , the value i is measured, and the state collapses to

|ψ = Π i |ψ / ψ| Π i |ψ .
Further measurements of |ψ by P will always result in the i measurement, so P |ψ (i) = 1. To look at the effects of a measurement operation on the algorithmic information theoretic properties of a state, take a PVM,

F = {Π i } 2 n-c
i=1 , where n is the number of qubits of the Hilbert space. Let Λ F be the distribution of pure states when F is measured over the uniform distribution Λ over n qubit spaces. Thus Λ F represents the F -collapsed states from Λ.

Theorem 34 n -2c < + log 2 I Prob (F :|ψ :F |ψ ) dΛ F .

Proof. Note that ψ| Π i |ψ dΛ = Dim(Π i )2 -n . Furthermore, let κ ⊂ {1, . . . , 2 n-c } be the set of numbers a ∈ κ such that K(a) > + n -c. So |κ| * > 2 n-c . We have that if ψ| Π i |ψ = 1 then I Prob (F |ψ : F |ψ ) = I Prob (j → [i = j] : j → [i = j]) = I(i : i) = + K(i). 2 I(F :|ψ :F |ψ ) dΛ F = 2 n-c i=1 Dim(Π i )2 -n 2 K(i) * > i∈κ Dim(Π i )2 -n 2 n-c * >|κ|2 -n 2 n-c * >2 n-2c .
Chapter 7

Infinite Quantum Spin Chains

A qubit abstracts the properties of a single spin 1/2 particle. A complex system can be described by the collection of qubits, which model properties of superposition and entanglement. It can be convenient to consider a system's thermodynamic limit, which is the limit of infinite system size. This model is an infinite quantum spin chain. In the study of infinite quantum spin chains one can make a distinction between local and global effects. In addition, one does not need to consider boundary conditions.

A Martin Löf random sequence is the accepted definition in AIT for a random infinite sequence. Can one define a quantum Martin Löf infinite quantum state? This chapter shows that this can be answered in the affirmative, and even landmark theorems in AIT like the Levin-Schnorr theorem can transfer over to the quantum domain.

We first review Martin Löf random sequences. A Martin Löf test is an effective null set of the form n G n , where the measure of open set G n of the Cantor space goes toward zero. An infinite sequence passes a Martin Löf test if it is not contained in its null set. A Martin Löf random infinite sequence passes all Martin Löf tests. Let MLR be the set of Martin Löf random sequences.

In [START_REF] Nies | Martin-Löf Random Quantum States[END_REF], the set of random infinite quantum states was introduced, which we call a NS random state. Just like the classical setting, a NS random state passes allso-called NS tests. An NS test is a quantum analog to Martin Löf tests, and it is defined by projections instead of open sets.

Infinite Quantum Bit Sequences

Before we introduce NS random sequences, we revisit the notion of C * algebras and functional states. A C * algebra, M, is a Banach algebra and a function * : M → M such that

• For every x ∈ M, x * * = x.
• For every x, y ∈ M, (x + y) * = x * + y * and (xy) * = y * x * .

• For every λ ∈ C and x ∈ M, (λx) * = λx * .

• For all x ∈ M, x * x = x x * . A C * algebra M is unital if it admits a multiplicative identity 1. A state over unital M is a positive linear functional Z : M → C such that Z(1) = 1. States are used to define NS random sequences. The set of states of M is denoted by S(M). A state is tracial if Z(x * x) = Z(xx * ), for all x ∈ M.

The C * algebra over matrices of size 2 k over C is denoted by M k . Each state ρ ∈ S(M k ), can be identified with a density matrix S such that ρ(X) = TrSX, for all X ∈ M. States that cannot be represented as the convex combination of other states are called pure states. Otherwise they are called mixed states. States are used interchangeably with density matrices, depending on the context. The tracial state τ n ∈ S(M n ) corresponds to the matrix 2 -n I 2 n . The algebra M ∞ is the direct limit of the ascending sequence of M n . . A state Z ∈ S(M ∞ ) over M ∞ can be seen as a sequence of density matrices {ρ n } that are coherent under partial traces, with Tr M n+1 ρ n+1 = ρ n . We use Z n to denote the restriction of state Z to the algebra M n . There is a unique tracial state τ ∈ S(M ∞ ), where τ n = τ n . A projection p ∈ M ∞ is a self adjoint positive element such that p = p 2 . A special projection p ∈ M n is a projection represented by an elementary matrix.

NS Randomness

An NS Σ 0 1 set is a computable sequence of special projections {p i } in M ∞ with p i ≤ p i+1 over all i. For state ρ and NS Σ 0 1 set G, ρ(G) = sup i ρ(p i ). We define NS tests. But initially, we will provide the definition for the classical Martin Löf random sequence, to provide a point of reference. A classical Martin Löf test, is a sequence {U n } of uniformly Σ 0 1 sets of infinite sequences

U n ⊆ {0, 1} ∞ such that µ(U n ) ≤ 2 -n . An infinite sequence α ∈ {0, 1} ∞ is Martin-Löf random if there is no Martin Löf test {U n } such that α ∈ n U n . There is a universal Martin Löf test {V n } such that if α ∈ n V n , then α is random.
Mirroring the classical case, a NS test is an effective sequence of NS Σ 0 1 sets G r such that τ (G r ) ≤ 2 -r . Unlike a classical test, which can either pass or fail a sequence, a NS test can pass a quantum state up to a particular order. For δ ∈ (0, 1), state Z ∈ S(M ∞ ) fails test G r at order δ if Z(G r ) > δ for all r. Otherwise Z passes the test at order δ. We says Z passes a NS test if it passes it at all orders δ ∈ (0, 1).

A state is NS random if it passes every NS test at every order.

Theorem 35 ([NS19]

) There exists a universal NS test R n , where for each NS test G k and each state Z and for each n there exists a k such that

Z(R n ) ≥ Z(G k ). Proof. Let G k n ∞
n=1 be an enumeration of NS tests, performed analgously to the classical case (see [G 01]). Furthermore let G e m = p e m,r r∈N . For each k, n ∈ N, let q n k = e+n+1≤k p e e+n+1,k . Thus q n k ≤ q n k+1 and τ q n k ≤ e τ (p e e+n+1,k ) ≤ 2 -n . The universal NS test is

R n = q n k k∈N . Since τ (R r ) ≤ 2 -n , R n is a NS test. For a set e, ρ(R n ) = sup k ρ(q n k ) ≥ sup k ρ(p e n+e+1,k ) = ρ(G e n+e+1 ).
A state Z is NS random if it passes the test R n . . More information about R r can be found in [START_REF] Nies | Martin-Löf Random Quantum States[END_REF].

Closure Properties

The set of NS random sequences has closure properties over (possibly noncomputable) convex combinations, as shown in the following theorem.

Theorem 36 Every convex combination Z = i αZ i of NS random states Z i , with i α i = 1 and α i ≥ 0, is NS random.

Proof. Given an NS test G r = p r t , there exists a NS test H r such that for all states Z, inf r Z(H r ) ≥ inf r Z(G r ) and H r ⊇ H r+1 . This is by setting H r equal to i≥r G i . More formally, H r = q r t , where q r t = t i=1 p r+i t . Thus there exists a universal NS test L r such that L r ⊇ L r+1 . Assume that Z is not NS random. Then

lim r→∞ Z(L r ) > 0 lim r→∞ i α i Z i (L r ) > 0 i α i lim r i →∞ Z i (L r i ) > 0.
So there exists an i such that lim r→∞ Z i (L r ) > 0, and thus Z i is not NS random.

Gács Complexity and NS Random Sequences

In this section, we characterize NS random states in terms of Gács complexity, Hg.

Theorem 37 Given state Z ∈ M ∞ , and program p that enumerates infinite set A ⊆ N, then

sup n∈N n -Hg(Z n) < + sup n∈A n -Hg(Z n) + K(p).
Proof. There exists a program p of size p +O(1) that outputs a list {a n } ⊆ A such that n < a n . For a given a n , σ = 2 n-an µ n ⊗ I an-n is a lower computable 2 an × 2 an semi-density matrix. There is a program q = q a n , n that lower computes σ where q is helper code that uses the encodings of a n and n. By the universal properties of µ, we have the inequality m(q|a n )σ * < µ an . So, using properties of partial trace,

a n + log m(q|a n )TrσZ a n < + a n + log Trµ(Z a n ) a n + log Tr2 n-an (µ n ⊗ I an-n )Z a n -K(q|a n ) < + a n + log Trµ(Z a n ) n + log Tr(µ n ⊗ I an-n )Z a n -K( n, a n |a n ) < + a n + log Trµ(Z a n ) n + log Tr(µ n Tr n Z a n ) -K(p |a n ) < + a n + log Trµ(Z a n ) n -Hg(Z n) < + a n -Hg(Z a n ) + K(p). So sup n∈N n -Hg(Z n) < + sup an∈{an} a n -Hg(Z a n ) + K(p) < + sup n∈A n -Hg(Z n) + K(p).
Theorem 38 Suppose for state Z, and for infinite enumerable set

A ⊆ N, sup n∈A n -Hg(Z n) < ∞. Then Z is NS random.
Proof. Suppose Z is not NS random. Let L r = p r t be the universal NS test. So Rank(p r n ) ≤ 2 n-r . Thus inf r Z(L r ) = δ > 0. For each r, there exists an n such that Tr(p r n z n ) ≥ δ, where z n = Z n. Since 2 r-n p r n is a computable semi-density matrix given n and r, m(r|n)2 r-n p r n * < µ.

So m(r|n)2 r-n δ * < Trµz n , which implies that Hg(Z n) < + n -r + K(r|n). Since this property holds for all r ∈ N, sup n n -Hg(Z n) = ∞. From Theorem 37, sup n∈A n -Hg(Z n) = ∞.

Encodings of States

Let [Z] ∈ {0, 1} ∞ be an encoding of the state Z described as follows. For each n, let e(n, m) be the mth enumeration of a pair (p, k) consisting of a special projection p of M n and a rational 0 ≤ k ≤ 1. For [Z], the ith bit, where i = 2 n m for maximum n, corresponds to 1 if and only if TrpZ n > k, where (p, k) is the pair enumerated by e(n, m). We say that state Z ∈ QH if and only if the halting sequence can be computed from [Z].

Quantum Operation Complexity

In a canonical algorithmic information theory example, Alice wants to send a single text message x to Bob. Alice sends a program q to Bob such that x = U (q), where U is a fixed universal Turing machine. The cost of the transmission is the length of q. Alice can minimize cost by sending K(x) bits to Bob, where K is the Kolmogorov complexity function.

We now look at the quantum case. Suppose that Alice wants to send a (possibly mixed) n qubit quantum state σ to Bob, represented as an density matrix over C 2 n , or an element of S(M n ). Alice has access to two channels, a quantum channel and a classical channel. Alice can choose to send m ≤ n qubits ρ on the quantum channel and classical bits q ∈ {0, 1} * on the classical channel, describing an elementary quantum operation η, where U (q) = [η]. Bob then applies η to ρ to produce σ = η(ρ). Bob is not required to produce σ exactly. Instead the fidelity of the attempt is measured by the trace distance between σ and σ . The trace distance D between two matrices A and B is D(A, B) = 1 2 A -B Tr , with A Tr = Tr|A|. We use O m,n to denote the set of elementary quantum operations that take m qubit quantum states to n ≥ m qubit quantum states.

Definition 9 For n qubit density matrix σ, the quantum operation complexity at accuracy is

Hoc (σ) = min{K([η]) + m : η ∈ O m,n , ξ ∈ S(M m ), D(σ, η(ξ)) < }.

Initial Segment Incompressibility

Due to Levin and Schnorr,[START_REF] Levin | Laws of Information Conservation (Non-growth) and Aspects of the Foundations of Probability Theory[END_REF][START_REF] Schnorr | A unified approach to the definition of random sequences[END_REF] α is random iff there is an r such that for all n, K(α ≤n ) ≥ n -r, where α ≤n is a prefix of α of size n, and K is prefix free Kolmogorov complexity. In this section, we prove a quantum analog to this result. We show that NS states that are NS random have incompressible prefixes with respect to quantum operation complexity. Theorem 39 builds upon the proof of the Theorem 4.4 in [NS19] using quantum operation complexity Hoc.

Theorem 39 Let Z be a state on M ∞ .

1. Let 1 > > 0, and suppose Z passes each NS test at order 1 -. Then there is an r where for all n, Hoc (Z n ) > n -r.

2. Let 1 > > 0 be lower computable and Z fails some NS test at order 1 -. Then either Z ∈ QH or for all r, there is an n where Hoc

√ (Z n ) < n -r.
Proof. (1). Let K t (x) be the smallest program to produce x in time t. Let s(n, r, t) be the set of pure n qubit states ρ ∈ S(M n ) such that there exists a quantum operation η ∈ O z,n and pure state σ ∈ S(M z ) such that ρ = η(σ) and K t ([η]) + z ≤ n -r. Let p(n, r, t) be the orthogonal projection in M n with minimum τ (p(n, r, t)) such that ρ(p(n, r, t)) = 1 for all ρ ∈ s(n, r, t). Let p(r, t) = sup n≤t p(n, r, t). So p(r, t) is in M t and p(r, t) is computable from r and t and p(r, t) ≤ p(r, t + 1).

Let b(y, n, z) be the number of programs of length y which outputs an encoding of an elementary quantum operation η ∈ O z,n . Let b(y, n) be the number of programs of length y which outputs an encoding of an elementary quantum operation η ∈ O z,n , for any z ≤ n. So

Range(p(n, r, t)) ≤ y+z≤n-r b(y, n, z)2 z τ (p(n, r, t)) ≤ y+z≤n-r b(y, n, z)2 z-n ≤ y+z≤n-r b(y, n, z)2 -y-r ≤ n-r y=1 b(y, n)2 -y-r τ (p(r, t)) ≤ ∞ n=1 τ (p(n, r, t)) ≤ ∞ n=1 n-r y=1 b(y, n)2 -y-r = 2 -r ∞ n=1 n-r y=1 b(y, n)2 -y ≤ 2 -r .
So for NS Σ 0 1 set G r enumerated by the sequence {p(r, t)} t , G r is a NS test. For each r suppose there is an n such that Hoc (Z n) ≤ n -r. So there is an elementary quantum operation η ∈ O z,n and input ρ ∈ S(M z ) such that K([η]) + z ≤ n -r and D(Z n , η(ρ)) < . So η(ρ) is in the range p(n, r, t) for some t and so Trη(ρ)p(n, r, t) = 1. This implies 1 -< Z(p(n, r, t)) ≤ Z(G r ). Since this is for all r, Z fails the test at order 1 -.

(2). Let bb(n) be the longest running time of a halting program of length ≤n. Let L r be the universal NS test, where each L r is enumerated by {p r t }, with p r t ∈ M n(r,t) . Assume there is an infinite number of r where TrZ n(r, bb(r/2))p r bb(r/2) > 1 -. Fix one such r and let n = n(r, bb(r/2)), and p = p r bb(r/2) . Projection p has eigenvectors {u i } and kernel spanned by {v i }. Thus 2 -r ≥ τ (p). Let p ≥ p with p ∈ M n such that each u i is in the range of p and {v i } k i=1 is in the range of p such that k is minimized such that τ (p ) = 2 -r . Thus TrZ n(p ) > 1-. The eigenvectors of p are {w i } 2 n-r i=1 and its kernel is spanned by the vectors {y i } 2 n -2 n-r i=1

. Let z = Proj(Z n; p ) be a density matrix with eigenvalues v i ∈ R corresponding to eigenvectors w i . For i ∈ [1, 2 n ], let B(i) ∈ {0, 1} * be an encoding of n bits of the number i, with B(1) = 0 (n) , B(2) = 10 (n-1) , and

B(2 n ) = 1 (n) . Let U be a 2 n × 2 n unitary matrix, of the form U = 2 n-r i=1 |B(i) w i | + 2 n -2 n-r i=1 |B(i + 2 n-r ) y i |. Proposition 3 ([NS19]) Let Proj(s; h) = 1 Tr[sh] hsh.
Let p be a projection in M n and σ be a density matrix in M n . If α = Trpσ and σ = Proj(σ; p) then D(σ, σ ) ≤ √ 1 -α.

Proof. Let |ψ σ be a purification of σ. Then α -1 2 p |ψ σ is a purification of σ . Uhlmann's theorem states

F (σ, σ ) ≥ α -1 2 ψ σ | p |ψ σ = α 1 2 , where F is fidelity, with F (σ, σ ) = Tr √ σ σ √ σ . Thus the proposition follows from D(σ, σ ) ≤ 1 -F (σ, σ ).
The quasilocal C * algebra A ∞ is defined to be the norm closure of Λ⊂Z A Λ . For states Ψ over A ∞ , we use Ψ n to denote Ψ restricted to the finite subalgebra A {1,...,n} of A ∞ . The right shift T is a * -automorphism on A ∞ uniquely defined by its actions on local observables T : a ∈ A {m,...,n} → A {m+1,...,n+1} . A quantum state Ψ is stationary if for all a ∈ A ∞ , Ψ(a) = Ψ(T (a)). The set of shift-invariant states on A ∞ is convex and compact in the weak* topology. The extremal points of this set are called ergodic states.

Lemma 6 Let R j be the smallest subspace spanned by pure states produced by elementary quantum operations η ∈ O z,n with K(η) + z < j . Then Dim(R j ) < 2 j .

Proof. Let b(y, z) be the number of programs of length y that outputs an elementary quantum operation η ∈ O x,z over the Hilbert space H 2 n . Let b(y) be the number of programs of length y that outputs an elementary quantum operation O z,n over the Hilbert space

H 2 n . Dim(R j ) ≤ y+z<j b(y, z)2 z = 2 j y+z<j b(y, z)2 z-j < 2 j y,z b(y, z)2 -y = 2 j y b(y)2 -y ≤ 2 j .
Theorem 40 Let Ψ be an ergodic state with mean entropy h. For all δ > 0, for almost all n, there is an orthogonal projector P n ∈ A n such that for all > 0,

1. Ψ n(P n ) > 1 -δ.
2. For all one dimensional projectors p ≤ P n , Hoc (p)/n ∈ (h -δ, h + δ).

Proof. Let δ < δ < δ. From [BDK + 05], there is a sequence of projectors P n ∈ A n where for almost all n, Ψ n(P n ) > 1 -δ , for all one dimensional projectors p ≤ P n , 2 -n(h+δ ) < Ψ n(p ) < 2 -n(h-δ ) , and 2 n(h-δ ) < TrP n < 2 n(h+δ ) . Let S n be the subspace that P n projects onto. Let R n be the smallest subspace spanned by all pure states produced by an elementary quantum operation η ∈ O g,n , where K(η) + g < n(h -δ ). Let Q n be the projector onto R n . By Lemma 6, Dim(R n ) < 2 n(h-δ ) . Let S n be the largest subspace of S n that is orthogonal to R n . Let P n be the orthogonal projector onto S n . So for sufficiently large n,

Ψ n(P n ) ≥ Ψ n(P n )-Dim(R n )2 -n(h-δ ) > 1 -δ -2 n(h-δ ) 2 -n(h-δ ) = 1 -δ -2 n(δ -δ ) > 1 -δ, for large enough n.
By definition, since P n is orthogonal to R n , for all , for all one dimensional projectors p ≤ P n ,

Hoc (p) ≥ n(h -δ ) > n(h -δ).
Furthermore, all such p can be produced from an elementary quantum operation η that maps n(h + δ ) length pure states into S n . Therefore for large enough n,

Hoc (p) ≤ K(η) + n(h + δ ) < + K(n, h) + n(h + δ ) < n(h + δ).

Measurement Systems

We note that pre-measures are of the form γ : {0, 1} * → R ≥0 , where γ(x) = γ(x0) + γ(x1). By the Carathéodory's Extension Theorem, each such pre-measure can be uniquely extended to a measure Γ over {0, 1} ∞ . in Chapter 6, measurements of finite collections of qubits are studied. This section deals with measurement measurement systems, which can be applied to infinite quantum states.

Definition 10 (Meaurement System ([Bho21])) An α-computable measurement system B = {(|b n 0 , |b n 1 )} is a sequence of orthonormal bases for Q 1 such that each |b n i is elementary and the sequence |b n 1 , |b n 0 ∞ n=1 is α-computable.
Note that the above defiinition can be generalized to a sequence of PVMs. We now define the application of a measurement system B to an infinite quantum state Z which produces a premeasure p. Let ρ n be the density matrix associated with Z n. For the first bit, we use the standard definition of measurement, where

p(i) = Tr |b 1 i b 1 i | ρ 1 .
Given ρ 2 , if i is measured on the first bit, then the resulting state would be

ρ i 2 = (|b 1 i b 1 i | ⊗ I)ρ 2 (|b 1 i b 1 i | ⊗ I) Tr(|b 1 i b 1 i | ⊗ I)ρ 2 So p(ij) = p(i)p(j|i) = Tr |b 1 i b 1 i | ρ 1 Tr I ⊗ |b 2 j b 2 j | |b 1 i b 1 i | ⊗ I ρ 2 |b 1 i b 1 i | ⊗ I |b 1 i b 1 i | ⊗ I ρ 2 Since Tr 2 ρ 2 = ρ 1 , Tr |b 1 i b 1 i | ρ 1 = Tr |b 1 i b 1 i | ⊗ I ρ 2 . Therefore p(ij) = Trρ 2 |b 1 i b 2 j b 1 i b 2 j | .
More generally for x ∈ {0, 1} n , we define the pre-measure p to be

p(x) = Trρ n |⊗ n i=1 b i x i ⊗ n i=1 b i x i | ;
It is straightforward to see that p is a pre-measure, with p(x) = p(x0) + p(x1). Let µ B Z be the measure over {0, 1} ∞ derived from the described pre-measure, using measurement system B and state Z. We recall that MLR is the set of Martin Löf random sequences.

S m = m≤i A m i ,
where A m i ⊆ A m i+1 , and A m i {τ m,i 1 , . . . , τ m,i k m,i } ⊂ {0, 1} i for some 0 ≤ k m-i ≤ 2 i-m . Thus µ(S m ) ≤ 2 -m , where µ is the uniform distribution over {0, 1} ∞ . We define an NS test as follows. For all m and i, with m ≤ i, let τ a = τ m,i a and define the special projection

p m i = a≤k m,i |⊗ i q=1 b q τα[q] ⊗ i q=1 b q τα[q] | .
We define P m = {p m i } m≤i we have that P m is an NS Test. The special tests p m i is uniformly computable in i and m since B and A m i are uniformly computable in i and m. Since

A m i ⊆ A m i+1 , Range(p m i ) ⊆ Range(p m i+1 )
. So P m is an NS Σ 0 1 set for all m. Since k m,i ≤ 2 i-m for all m and i, this implies τ (P m ) ≤ 2 -m for all m.

For all m, {0, 1} ∞ \ MLR ⊆ S m . Since by assumption µ B Z ({0, 1} ∞ \ MLR) > δ, for all m there exists i(m) > m such that µ B Z ( A m i(m ) > δ. Fix an m and i = i(m) and let A m i = {τ 1 , . . . , τ k m,i }, where k m,i ≤ 2 i-m . Let p be the pre-measure associated witth µ B Z . So we have

δ < a≤k m,i p(τ a ) = a≤k m,i Trρ i |⊗ i q=1 b q τ [q] ⊗ i q=1 b q τ [q] | = Trρ i a≤k m,i |⊗ i q=1 b q τ [q] ⊗ i q=1 b q τ [q] |
So we see that for all m there is an i such that δ < Trρ i p m i ≤ Z(P m ).

So inf m Z(P m ) > δ, contradicting that Z is NS random.

Theorem 42 ([Bho21]

) There are states that are Bhojraj random and not NS Random.

NS Solovay States

A NS Solovay test is a sequence of NS Σ 1 0 sets G n such that n τ (G n ) < ∞. A state Z fails a quantum NS test G r at order δ ∈ (0, 1) if there is an infinite number of r ∈ R such that inf r∈R Z(G r ) > δ. Otherwise state Z passes the quantum NS test at order δ. A quantum state Z is NS Solovay random if it passes all NS Solovay tests at all orders. The following theorem shows the equivalence of NS randomness and NS Solovay randomness with respect to every order δ. Given a special projection p, NS Σ 1 0 set Q = {q n }, and state Z, we define Z(p \ Q) = inf n Z(p \ q n ). In [START_REF] Bhojraj | Algorithmic randomness and kolmogorov complexity for qubits[END_REF], it was proven that NS randomness is equivalent to NS Solovay randomness.

Proposition 4 Given a special projection p, NS Σ 1 0 set Q, and state Z, Z(p

) -Z(Q) ≤ Z(p \ Q) ≤ Z(p).
The proof is straightforward.

Theorem 43 If a state Z fails an NS test at order δ then it fails an NS Solovay test at order δ.

Proof. Assume that state Z fails a NS test G r at order δ. Since r τ (G r ) ≤ 1, and each G r is an NS Σ 0 1 set, G r is a NS Solovay test. Furthermore since inf r Z(G r ) ≥ δ, there exists an infinite number of r such that Z(G r ) > δ. Thus Z fails a NS Solovay test at order δ.

Theorem 44 For all δ < δ, if a state Z fails an NS Solovay test at order δ then it fails an NS test at order δ .

Proof. Assume state Z fails NS Solovay test G r at order δ. Given G r , where G r = p r n n∈N , we construct an NS test H r as follows. There exists an m such that n>m τ (G n ) ≤ 1. Fix r. Enumerate all unordered sets of r + 1 natural numbers {D r n } n∈N , D r n ⊂ N, with infinite repetition.

H r = {q r n }, q r n = m<n q r m   t∈D r n p t n   .
Each H r can be seen to be an NS Σ 0 1 set. Furthermore τ (H r ) ≤ t>r Z(G t ) ≤ t>r 2 -t = 2 -r . So H r is an NS test. For each r, Z(H r ) > δ . Assume not. Then there exists a k such that Z(H k ) ≤ δ . Since Z fails G r at order δ, there exists an infinite number of r ∈ R and n r ∈ N such that Z(p r nr ) ≥ δ , for some δ < δ < δ. We reorder the NS Solovay test G r such that r ranges over solely R. Let z r = p r n,r . Let D n,k be the set of all unordered subsets of {1, . . . , n} of size k.

For k > n let F n,k = ∅. Let F n,k =   A∈D n,k r∈A z r   \ s>k F n,s .
So for all n ∈ N, using Proposition 4,

n(δ -δ ) ≤ n r=1 (Z(z r ) -Z(H k )) ≤ n r=1 Z(z r \ H k ) ≤ n r=1 Z k s=1 F n,s ∧ z r (7.1)
Equation 7.1 is due to the fact that for s > k there is a t where we have Range(F n,s ) ≤ Range(q k s ). Let F n,s,r = F n,s ∧ z r , with for a fixed s

≤ k, n i=1 Z(F n,s,i ) ≤ s. n(δ -δ ) ≤ n r=1 Z k s=1 F n,s,r = k s=1 n r=1 Z (F n,s,r ) ≤ k s=1 s = O(k 2 ).
This is a contradiction for large enough n.

Corollary 10 A quantum state is NS random if and only if it is NS Solovay random.

Chapter 8

The Many Worlds Theory

The Many Worlds Theory (MWT) was formulated by Hugh Everett [START_REF] Everett | relative state" formulation of quantum mechanics[END_REF] as a solution to the measurement problem of Quantum Mechanics. Branching (a.k.a splitting of worlds) occurs during any process that magnifies microscopic superpositions to the macro-scale. This occurs in events including human measurements such as the double slit experiments, or natural processes such as radiation resulting in cell mutations.

One question is if MWT causes issues with the foundations of computer science. The physical Church Turing Thesis (PCTT) states that any functions computed by a physical system can be simulated by a Turing machine. A straw man argument for showing MWT and PCTT are in conflict is an experiment that measures the spin of an unending number of electrons, with each measurement bifurcating the current branch into two sub-branches. This results in a single branch in which the halting sequence is outputted. However this branch has Born probability converging to 0, and can be seen as a deviant, atypical branch.

In fact, conflicts do emerge between MWT and Algorithmic Information Theory. In particular, the Independence Postulate (IP) is a finitary Church-Turing thesis, postulating that certain infinite and finite sequences cannot be found in nature, a.k.a. have high "addresses". If a forbidden sequence is found in nature, an information leak will occur. However MWT represents a theory in which such information leaks can occur. This blog entry covers the main arguments of this conflict.

Many Worlds Theory

Some researchers believe there is an inherent problem in quantum mechanics. On one hand, the dynamics of quantum states is prescribed by unitary evolution. This evolution is deterministic and linear. On the other hand, measurements result in the collapse of the wavefunction. This evolution is non-linear and nondeterministic. This conflict is called the measurement problem of quantum mechanics.

The time of the collapse is undefined and the criteria for the kind of collapse are strange. The Born rule assigns probabilities to macroscopic outcomes. The projection postulate assigns new microscopic states to the system measured, depending on the the macroscopic outcome. One could argue that the apparatus itself should be modeled in quantum mechanics. However it's dynamics is deterministic. Probabilities only enter the conventional theory with the measurement postulates.

MWT was proposed by Everett as a way to remove the measurement postulate from quantum mechanics. The theory consists of unitary evolutions of quantum states without measurement collapses. For MWT, the collapse of the wave function is the change in dynamical influence of one However, the Born rule and the projection postulate are not assumed by MWT. The dynamics are totally deterministic. Each branch is equally real to the observers in it. To address these issues, Everett first derived a typicality-measure that weights each branch of a state's superposition. Assuming a set of desirable constraints, Everett derived the typicality-measure to be equal to the norm-squared of the coefficients of each branch, i.e. the Born probability of each branch. Everett then drew a distinction between typical branches that have high typicality-measure and exotic atypical branches of decreasing typicality-measure. For the repeated measurements of the spin of an electron |φ = a |φ ↑ + b |φ ↓ , the relative frequencies of up and down spin measurements in a typical branch converge to |a| 2 and |b| 2 , respectively. The notion of typicality can be extended to measurements with many observables.

In a more recent resolution to the relation between MWT and probability, Deutsch introduced a decision theoretic interpretation [START_REF] Deutsch | Quantum theory of probability and decisions[END_REF] that obtains the Born rule from the non-probabilistic axioms of quantum theory and non-probabilistic axioms of decision theory. Deutsch proved that rational actors are compelled to adopt the Born rule as the probability measure associated with their available actions. This approach is highly controversial, as some critics say the idea has circular logic.

Another attempt uses subjective probability [START_REF] Vaidman | On schizophrenic experiences of the neutron or why we should believe in the many-worlds interpretation of quantum theory[END_REF]. The experimenter puts on a blindfold before he finishes performing the experiment. After he finishes the experiment, he has uncertainty about what world he is in. This uncertainty is the foundation of a probability measure over the measurements. However, the actual form of the probability measure needs to be postulated: Probability Postulate. An observer should set his subjective probability of the outcome of a quantum experiment in proportion to the total measure of existence of all worlds with that outcome.

Whichever explanation of the Born rule one adopts, the following section shows there is an issue with MWT and IP. There exist branches of substantial Born probability where information leaks occurs.

Violating the Independence Postulate

In [START_REF] Levin | Randomness conservation inequalities; information and independence in mathematical theories[END_REF][START_REF] Levin | Forbidden information[END_REF], the Independence Postulate, IP, was introduced: Let α ∈ {0, 1} * ∞ be a sequence defined with an n-bit mathematical statement (e.g., in Peano Arithmetic or Set Theory), and a sequence β ∈ {0, 1} * ∞ can be located in the physical world with a k-bit instruction set (e.g., ip-address). Then I(α : β) < k +n+c IP , for some small absolute constant c IP .

The I term is an information measure in Algorithmic Information Theory. For this blog, the information term we use is I(x : y) = K(x)+K(y)-K(x, y), where K is the prefix-free Kolmogorov complexity. We can use this definition of I because we only deal with finite sequences.

Let Ω m be the first m bits of Chaitin's Omega (the probability that a universal Turing machine will halt). We have m < + K(Ω m ). Furthermore Ω m can be described by a mathematical formula of size O(log m). Thus by IP, where Ω m = α = β, Ω m can only be found with addresses of size at least m -O(log m).

IP can be violated in the following idealized experiment measuring the spin |φ ↑ and |φ ↓ of N isolated electrons. We denote |φ 0 for |φ ↑ and |φ 1 for |φ ↓ . The "address" (in the sense of IP) of this experiment is < O(log N ). The measuring apparatus will measure the spin of N electrons in the state |φ = 1 2 |φ ↑ + 1 2 |φ ↓ . There is a measuring apparatus A with initial state of |ψ A , and after reading N spins of N electrons, it is in the state |ψ A [x] , where x ∈ {0, 1} N , whose ith bit is 1 iff the ith measurement returns |φ 1 .

The experiment evolves according to the following unitary transformation:

N i=1 |φ ⊗ |ψ A unitary -→ a 1 ,...,a N ∈{0,1} N 2 -N/2 N i=1 |φ a i ⊗ |ψ A [a 1 a 2 . . . a n ] .
If the bits returned are Ω N then a memory leak of size N -O(log N ) has occurred, because Ω N has been located by the address of the experiment, which is O(log N ). Thus Born-Probability(a memory leak of size N -O(log N ) occurred) ≥ 2 -N .

Conclusion

There are multiple variations of MWT when it comes to consistency across universes. In one formulation, all universes conform to the same physical laws. In another model, each universe has its own laws, for example different values of gravity, etc. However, the experiment in the previous section shows that mathematics itself is different between universes, regardless of which model is used. In some universes, IP holds and there is no way to create information leaks. In other universes information leaks occur, and there are tasks where randomized algorithms fail but non-algorithmic physical methods succeeds. One such task is finding new axioms of mathematics. This was envisioned as a possibility by Gödel [G 61], but there is a universal consensus of the impossibility of this task. Not any more! In addition, because information leaks are finite events, the Born probability of worlds containing them is not insignificant. In such worlds, IP cannot be formulated, and the the foundations of Algorithmic Information Theory itself become detached from reality.

Formulated another way, let us suppose the Born probability is derived from the probability postulate. We have a "blindfolded mathematician" who performs the experiment described above. Before the mathematician takes off her blindfold, she states the Independence Postulate. By the probability postulate, with measure 2 -N over all worlds, there is a memory leak of size N -O(log N ) and IP statement by the mathematician is in error.

As a rebuttal, one can, with non-zero probability, just flip a coin N times and get N bits of Chaitin's Omega. Or more generally, how does one account for a probability P over finite or infinite sequences learning information about a forbidden sequence β with good probability? Due Thus the probability of a single event creating a leak is very small. However if many events occur, then the chances of a memory leak grows. However as there is many events, to locate one such leak, one will probably need a long address to find the leak, balancing out the IP equation.

This still leaves open the possibility of a memory leak occuring at an event with a small address. Since there are a small number of events that have a small address, the probability of a signifcant memory leak is extremely small. In physics on can postulate away events with extremely small probabilities. For example, the second law of thermodynamics states that entropy is nondecreasing, postulating away the extremely unlikely event that a large system suddenly decreases in thermodynamic entropy.

There is no way to postulate such memory leaks in MWT. Assuming the probability postulate, probability is a measure over the space of possible worlds. Thus when Bob now threatens to measure the spin of N particles, Alice now knows 2 -N of the resultant worlds will contain N bits of Chaitin's Omega, violating IP. Information non-growth laws say information about a target source cannot be increased with randomized processing. In classical information theory, we have

I(g(X) : Y ) ≤ I(X : Y ).
where g is a randomized function, X and Y are random variables, and I is the mutual information function. Thus processing a channel at its output will not increase its capacity. Information conservation carries over into the algorithmic domain, with the inequalities I(f (x) : y) < + I(x : y); I(f (a); H) < + I(a; H).

These inequalities ensure target information cannot be obtained by processing. If for example the second inequality was not true, then one can potentially obtain information about the halting sequence H with simple functions. Obtaining information about H violates the Independence Postulate, discussed in Chapter 8. Information non growth laws can be extended to signals [START_REF] Epstein | On the algorithmic information between probabilities[END_REF] which can be modeled as probabilities over N or Euclidean space1 . The "signal strength" of a probability p over N is measured by its self information. I Prob (p : p) = log i,j 2 I(i:j) p(i)p(j).

A signal, when undergoing randomized processing f (see Section 2.1.1), will lose its cohesion. Thus any signal going through a classical channel will become less coherent.

I Prob (f (p) : f (p)) < + I Prob (p : p).
In Euclidean space, probabilities that undergo convolutions with probability kernels will lose self information. For example a signal spike at a random position will spread out when convoluted with the Gaussian function, and lose self information. The above inequalities deal with classical transformations. One can ask, is whether, quantum information processing can add new surprises to how information signals occur and evolve.

One can start with the prepare-and-measure channel, also known as a Holevo-form channel. Alice starts with a random variable X that can take values {1, . . . , n} with corresponding probabilities {p 1 , . . . , p n }. Alice prepares a quantum state, corresponding to density matrix ρ X , chosen from {ρ 1 , . . . , ρ n } according to X. Bob performs a measurement on the state ρ X , getting a classical outcome, denoted by Y . Though it uses quantum mechanics, this is a classical channel X → Y . So using the above inequality, cohesion will deteriorate regardless of X s probability, with

I Prob (Y : Y ) < + I Prob (X : X).
There remains a second option, constructing a signal directly from a mixed state. This involves constructing a mixed state, i.e. density matrix σ, and then performing a measurement E on the state, inducing the probability Eσ(k) = TrσE k . However from [START_REF] Epstein | On the algorithmic information between probabilities[END_REF], for elementary (even enumerable) probabilities Eσ, I Prob (Eσ : Eσ) < + K(σ, E).

Thus for simply defined density matrices and measurements, no signal will appear. So experiments that are simple will result in simple measurements, or white noise. However it could be that a larger number of uncomputable pure or mixed states produce coherent signals. Theorems 32 and 33 say otherwise, in that the POVM measurement E of a vast majority of pure and mixed states will have negligible self-information. Thus for uniform distributions Λ and µ over pure and mixed states (see Section 5.2.2),

2 I Prob (E|ψ :E|ψ ) dΛ = O(1); 2 I Prob (Eσ:Eσ) dµ(σ) = O(1).
This can be seen as a consequence of the vastness of Hilbert spaces as opposed to the limited discriminatory power of quantum measurements. In addition, there could be non-uniform distributions of pure or mixed states that could be of research interest. In quantum decoherence, a quantum state becomes entangled with the environment, losing decoherence. The off diagonal elements of the mixed state become dampened, as the state becomes more like a classical mixture of states. Let p σ be the idealized classical probability that σ decoheres to, with p σ (i) = σ ii . Corollary 8 states that for an overwhelming majority of pure or mixed states σ, p σ is noise, that is, has negligible self-information.

2 I Prob( p |ψ :p |ψ ) dΛ = O(1); 2 I Prob (pσ:pσ) dµ(σ) = O(1).
This is to be expected, with one supporting fact being for an n qubit space, i ∈ {1, . . . , 2 n }, E Λ [p |ψ (i)] = 2 -n . With Algorithmic Information Theory, we've taken this fact one step further, showing that p |ψ has no (in the exponential) self-algorithmic information and cannot be processed by deterministic or randomized means to produce a more coherent signal. In addition, it appears a more direct proof of the first decoherence inequality could be possible.

However the measurement process has a surprising consquence, in that the wave function collapse causes an massive uptake in algorithmic signal strength. Let F be a PVM, of size 2 n-c , of an n qubit space and let Λ F be the distribution of pure states when F is measured over the uniform distribution Λ. Thus Λ F represents the F -collapsed states from Λ. Theorem 34 states n -2c < log log 2 I Prob (F |ψ :F |ψ ) dΛ F .

Apriori Distributions

To avoid the pitfall of a signalless distribution that only produces white noise, we can conjecture a new apriori distribution for quantum states that is not signalless. Note that we are dealing with measures over the density operator space and not directly with density operators because we are measuring properties, such as self-information, over all possible (pure or mixed) states. Properties of this apriori distribution can be discerned by working backwards. Indeed, suppose there are a set of (possibly infinite) systems {|ψ i }, where for each system |ψ i , a measurement occurs, producing a discernable signal. By Theorem 31, this implies the states |ψ i have high I(|ψ i : |ψ i ), where I is the information function between mixed states introduced in Definition 6. Thus any universal quantum apriori distribution over these systems must be weighted toward states with high self information. One candidate is an probability measure ξ over pure states where ξ(|ψ ) ∝ 2 I(|ψ :|ψ ) . However this area of research is still ongoing. Another clue to this universal quantum apriori distribution is the measurement operation, which as shown above, causes an uptake in signal strength. Take a PVM measurement F , which procures a value i from a state |ψ , projecting to a new state |ψ . P |ψ (i) = 1. By Corollary 7, this new state |ψ has self information

K(i) < log I(|ψ : |ψ ).
The error term is on the order of K(P ). Most of the measurement values i of P will be random, i.e. have large K(i) (just look at the Kolmorogov complexity of the first 2 n numbers!). Thus simple quantum measurements increase the self information of most measured quantum states (see Figure 9.1). So this fact, and Theorem 26, leads us to the following conclusion.

Take a distribution over density operators, such as Λ, where an overwhelming majority of states have negligible self-information. When each such state in its support is measured with a simple apparatus, the result is new a distribution where most of the states have substantial self-information.

However, the situation is reversed for quantum channels. A quantum state that is transformed by a quantum operation will not increase in self-information. So by Theorem 28, we get the following claim, where equality occurs if the quantum operation is a unitary transform.

Given any distribution over density operators, if all the density matrices its support are transformed by a simple quantum operation, then the resultant distribution will give more measure to mixed states with less self-information.

Thus simple measurements with many operators can only increase self-information, simple quantum operations can only decrease self-information, and simple unitary transforms leave the selfinformation unaltered. If the operation is complex, then nothing so far has been proven.

Measurements Before Information Cloning

The no-cloning theorem states that every unitary transform cannot clone an arbitrary quantum state. However there is the possibility of copying information from a subset of states. By "copying information", we mean that two measurements of two states will produce two values that are similar. More formally, the information cloned from a state |ψ relative to unitary transform U , and POVMs E and F is, The question is, given an initial distribution over density operators with low expected I Clone , what sort of transform is required to increase this expectation. In this section, we discuss necessary conditions of this transform. We require the following two assumptions.

Assumption (1): The initial distribution has low expected self information. Theorem 26 shows there is a large set of natural distributions that have this property. Any distribution Ω that is less than 2 c Λ will have log 2 I(|ψ :|ψ ) dΩ < + c. Another way to intrepret this assumption is through parmeterized distributions. Let P be a probability over parameters θ over pure state distribution, Γ(|ψ |θ). Assumption (2): The universal Turing machine is relativized to all the transforms and operators. This assumption states that for a system, the operations are known quantities. This is congruent with quantum information theory, in which actors are seen to compute unitary transforms or quantum operations. It is asumed that these actors have knowledge of the transforms.

How do you create a distribution with high expected I Clone , where most states can have cloneable information? Any transform that increases cloneable information must increase self-information. However Theorem 28, along with assumption (2) bars quantum operations as a means to create selfinformation, as the complexity of the quantum operations is O(1). Thus the only way to potentially increase self-information is to perform a measurement, which as Theorems 31 and 34 show, often times cause an uptake in self-information (see Figure 9.2). This is also discussed in the quotes of Section 9.2. Thus we get the following claim.

Measurements are required to produce distributions over quantum states that have cloneable information.

For example, take the starting distribution to be the uniform measure over pure states, Λ. Let E = F = {|i i|} be POVM measurements over projectors to the basis states and let U be any unitary transform such that U |i |0 = |i |i for i ∈ {1, . . . , 2 n }. By Theorems 26 and 29, we have that 2 I Clone (|ψ ) dΛ = O(1).

Now suppose we apply the measurement G = E to Λ, producing a new distribution Λ G concentrated evenly among the basis states, where Λ G (|i ) = 2 -n . Thus we have that I Clone (|i ) = I Prob (E |i : F |i ) = K(i). Since there are 2 n-O(1) basis states |i where n < + K(i), we have the following uptake in cloneable information.

n < + log 2 I Clone (|ψ ) dΛ G .

Other such applications can be seen as generalizations from this extreme example. Future work involves determining how tightly self information covers cloneable information. (4) This follow as a special case of Theorem 31.

(5) Let s(i, j) = m(i|N )m(j|N )2 I(|i :|j ) . The function s is lower semicomputable relative to H because m and T µ⊗µ are lower computable relative to H. Furthermore we have that where λ i are the eigenvalues of ρ. Due to concavity -2S(ρ) ≤ 2 log i λ 2 i . So I(ρ : ρ) > + 2Hg(ρ) -K(ρ, Hg(ρ)) -2S(ρ). The inequality follows from Hg(|i ) = + K(i) and S(|i i|) = 0. For I(|i : |i < + K(i) + I(i : H|n), we note that it is a special case of (5). (8) This follows from (5) and (6).

Corollary 11 For elementary ρ, 2Hg(ρ) -K(ρ, Hg(ρ)) -2S(ρ) < + I(ρ : ρ).

  c 2 I( a,c :b) ψ a (c) * < 2 I(a:b) /m(ψ).

  need to show m(a, b)/(m(a)m(b)) * > c (m(a, b, c)/(m(b)m(a, c)))m(ψ)ψ a (c), or c (m(a, b, c)/m(a, c))m(c|a) * < m(a, b)/m(a), since m(c|a) * > m(ψ)ψ a (c). Rewrite it c m(c|a)m(a, b, c)/m(a, c) * < m(a, b)/m(a) or c m(c|a)m(a)m(a, b, c)/m(a, c) * < m(a, b). The latter is obvious since m(c|a)m(a) * < m(a, c) and c m(a, b, c) * < m(a, b).

  The tensor product of two vectors is denoted by |φ ⊗ |ψ = |φ |ψ = |φψ . The inner product of |ψ and φ| is denoted by ψ|φ . The symbol Tr denotes the trace operation. The conjugate transpose of a matrix M is denoted by M * . For Hermitian matrix with eigenvalue decomposition A = a i |ψ i ψ i |, |A| = |a i | |ψ i ψ i |. The tensor product of two matrices is denoted by A ⊗ B. Projection matrices are Hermitian matrices with eigenvalues in {0, 1}. For tensor product space G X ⊗ G Y , the partial trace is denoted by Tr Y . For B X = Tr Y B, Tr(A•B X ) = Tr((A⊗I)•B), which is used frequently throughout the paper. For positive positive semidefinite matrices, σ and ρ we say σ ≤ ρ if ρ -σ is positive semidefinite. For positive semidefinite matrices A, B, C, if A ≤ B then TrAC ≤ TrBC. Mixed states are represented by density matrices, which are, self adjoint, positive semidefinite, operators of trace 1. A semi-density matrix has non-negative trace less than or equal to 1. The von Neumann entropy of a density matrix σ with orthogonal decomposition

  |ψ ∈H N Hg(|ψ ⊗m ). We have for all |ψ ∈ H N Trµ |ψ m ψ| m * > 2 -c . (3.1) Let Λ be the uniform distribution on the unit sphere of H N . And let ρ = |ψ m ψ| m dΛ. Trρ = Tr |ψ m ψ| m dΛ = dΛ = 1. Furthermore for |φ m , |ν m ∈ Sym(H m N ), with unitary transform U such that U m |ψ m = |ρ m , we have ν| n ρ |ν n = φ| m (U * m |ψ m ψ| m U m ) |φ m dΛ = φ m |ψ m ψ m |φ m m dΛ = φ| n ρ |φ n . For any pure state |ψ ∈ H m N , such that ψ| P S |ψ = 0, then ψ| ρ |ψ = 0. Thus ρ = P S /M . Integrating Equation 3.1, by dΛ results in 2 -c * < Trµρ * = TrµP S /M *

  2 n ], |i is the ith basis state of the n qubit space. Let |ψ = 2 n i=1 2 -n/2 |i |i . The pure state |ψ is elementary, with K(|ψ |2 2n ) = + 0. We define the the 3n qubit mixed state ρ 123 = .5 |ψ ψ| ⊗ |1 1| + .5 |1 1| ⊗ |ψ ψ|. ρ 12 = .5 |ψ ψ| + .5 |1 1| ⊗ 2 -n I. ρ 23 = .5 * 2 -n I ⊗ |1 1| + .5 |ψ ψ|. ρ 2 = 2 -n I. Hg(ρ 12 ) = + -log Trµ 2n ρ 12 < + -log Trµ 2n |ψ ψ| < + -log m(|ψ |2 2n )| ψ|ψ | 2 < + 0. Similarly, Hg(ρ 23 ) = + 0. Hg(ρ 2 ) = + n.

2 n i=1 2

 2 -n/2 |i |i |i , with K(|φ |2 3n ) = 0. Let σ 123 = |φ φ|. σ 12 = σ 23 = 2 n i=1 2 -n |i i| ⊗ |i i|. Hg(σ 123 ) = + -log Trσ 123 µ 3n < + -log Tr m(|φ |2 3n )| φ|φ | 2 < + 0. Let D be a unitary transform where D |i |i = |i |1 and K(D|2 2n ) = + 0. So Hg(σ 12 ) = + Hg(Dσ 12 D * ) = + Hg(2 -n I ⊗ |1 1|) = + n -log Tr(I ⊗ |1 1|)µ 2n . By Theorem 5 and properties of partial trace, Hg(2 -n I ⊗ |1 1|) = + n -log Tr |1 1| µ n = + n. So Hg(σ 12 ) = Hg(σ 23 ) = + n.

  giving high scores to pure states |ψ i which are atypical of the source. In general the d(|φ |σ) score for arbitrary |φ will be greater than a combination of d(•|P ) scores, with d(|φ |σ) > + log 2 d( |ψ i |P ) | φ|ψ i | 2 . In fact d is equivalent to the classical definition of randomness deficiency when σ is purely classical, i.e. only diagonal. Theorem 19 For diagonal σ = i p(i) |i i|, d(|i |σ) = + d(i|p).

Definition 5 (

 5 Quantum Randomness Deficiency (Uncomputable States)) The randomness deficiency of ρ with respect to σ is d(ρ|σ) = log TrT σ ρ. If σ is computable, then Definition 5 equals Definition 4. By definition, T σ is universal, since for every lower computable σ-test ν, m(ν)ν < T σ . Theorem 21 For n qbit density matrices σ, ρ, ν, and ξ, d(σ|ρ) + d(ν|ξ) < + d(σ ⊗ ν|ρ ⊗ ξ).

<

  Proof. Assume not. Then for any positive constant c, there exists semi-density matrices ρ and σ, such that cm(ρ|N )m(σ|N )2I(ρ:σ) = cTrm(ρ|N )m(σ|N )C µ⊗µ (ρ ⊗ σ) > 1.By the definition of µ, m(ρ|N )ρ * < µ and m(σ|N )σ * < µ. Therefore by the definition of the Kronecker product, there is some positive constant d such that for all ρ and σ, dm(ρ|N )m(σ|N )(ρ⊗ σ) < (µ ⊗ µ), and similarlydTrm(ρ|N )m(σ|N )C µ⊗µ (ρ ⊗ σ) < TrC µ⊗µ (µ ⊗ µ).By the definition of C, it must be that TrC µ⊗µ µ ⊗ µ ≤ 1. However for c = d, there exists a ρ and a σ, such that TrC µ⊗µ µ ⊗ µ > dTrm(ρ|N )m(σ|N )C µ⊗µ (ρ ⊗ σ) > 1, causing a contradiction. Theorem 26 ([Eps19b]) Let Λ be the uniform distribution on the unit sphere of H N . 1. Hg(I/N ) = + log N , 2. I(I/N : I/N ) < + 0, 3. 2 -Hg(|ψ ) dΛ * = N -1 , 4. 2 I(|ψ : |ψ ) dΛ < + 0. Proof. (1) follows from Hg(I/N ) = + -log TrµI/N = + log N -log Trµ = + log N . (2) is due to Theorem 25, with I(I/N : I/N ) < + 2K(I/N |N ) < + 0. (3) uses the fact that ρ = |ψ ψ| dΛ = I/N , because Trρ = 1, and ψ| ρ |ψ = φ| ρ |φ . Thus 2 -Hg(|ψ ) dΛ * = Trµ |ψ ψ| dΛ * = Trµ |ψ ψ| dΛ * = N -1 . (4) uses the proof of Theorem 8, which states |ψ ψ| ⊗ |ψ ψ| dΛ = |ψψ ψψ| dΛ = N +1 2 -1 P , where P is the projection onto the space of pure states |ψψ . So 2 I(|ψ : |ψ ) dΛ = TrC µ⊗µ |ψ ψ| ⊗ |ψ ψ| dΛ = TrC µ⊗µ |ψ ψ| ⊗ |ψ ψ| dΛ TrC µ⊗µ N -2 I * = 2 I(I/N :I/N )

  Theorem 29 ([Eps19b]) Let C |ψ |0 n = |φ |ϕ , where C is an elementary unitary transform. Relativized to C, I(|φ : |ϕ ) < + I(|ψ : |ψ ).

  be an aggregation of upper computable C ⊗ D tests of the form A ⊗ B, weighted by their upper probability. Definition 8 The upper information between semi-density matrices A and B is I(A : B) = log TrG µ⊗µ (A ⊗ B). Proposition 2 I(I/N : I/N ) = O(1). Proof. 1 ≥ TrG µ⊗µ (µ ⊗ µ) * > TrG µ⊗µ (I/N ⊗ I/N ) * > 2 I(I/N :I/N ) .

  to probabilistic conservation laws [Lev74, Lev84], we have Pr α∼P [I(α : β) > I( P : β) + m] * < 2 -m .

  Signals from Classical and Quantum Sources

Figure 9

 9 Figure 9.1: Each box on the top row represents an n qubit Hilbert space, with the shaded rectangles being the subspaces of the PVM projectors. Thus there are three PVMs. The self-information majorizes these subspaces, inversely weighted by the PVM's complexity.

I

  Clone (|ψ ) = I Prob (E |φ 1 :F |φ 2 ), where U |ψ |0 = |φ 1 |φ 2 .This represents the shared signal strength between |1 and |2 when the states 2 were created from a unitary transform U of |ψ tensored with an ancillia state |0 . Note that by Theorems 29 and 31, cloneable information is less than self information, with I Clone (|ψ ) < log I(|ψ : |ψ ).

  The distribution is balanced, where Γ(|ψ |θ)dP (θ) = Λ(|ψ ). Then because of Theorem 26, P ({θ : E |ψ ∼Γ(•|θ) [I(|ψ : |ψ )] ≥ m}) ≤ 2 -m+1 .

Figure 9 . 2 :

 92 Figure 9.2: The intial distribution has low self information and cloneable information. A measurement increases the self information and potentially increases the cloneable information.

From

  each T , let T = i,j ( k m(k|j, N ) i| k| T |i |k ) |i |j i| j|. Since m and T are lower computable, then so is T . In addition, O(1)T ∈ T µ⊗µ , becauseTrT µ ⊗ µ = i,j i| j| µ ⊗ µ |i |j k m(k|j, N )( i| k| T |i |k ) * = i,j m(i|N )m(j|N ) k m(k|j, N )( i| k| T |i |k ) * < i,j m(i|N ) k m(j, k|N )( i| k| T |i |k ) * = i,j m(i|N ) k m(k|N )m(j|k, K(k), N )( i| k| T |i |k ) * = i,k m(i|N )m(k|N ) j m(j|k, K(k), N ) i| k| T |i |k * < i,k m(i|N )m(k|N )( i| k| T |i |k ) * < TrT µ ⊗ µ < O(1). So I(|i : |j ) > log TrT m(O(1)T |N 2 )O(1)T |i |j i| j| > + log Tr T m(T |N 2 )T |i |j i| j| > + log T m(T |N 2 ) k m(k|j, N ) k| i| T |k |i > + log T m(T |N 2 )m(k|j, N ) k| i| T |k |i = + I(|k : |i ) -K(k|j).

  )m(j|N )TrT µ⊗µ |i i| ⊗ |j j| =TrT µ⊗µ i,j m(i|N )) |i i| ⊗ m(j|N ) |j j| <O(1)TrT µ⊗µ µ ⊗ µ < O(1). Therefore s(i, j) * < m(i, j|N, H) and so I(|i : |j ) < + log m(i, j|N, H)|(m(i|N )m(j|N )) = + I(i : j|N ) + I(i, j : H|N ). (6) For K(i|N ) < + I(|i : |i ), we prove the stronger statement: for elementary ρ, 2Hg(ρ) -K(ρ, Hg(ρ)) -2S(ρ) < + I(ρ : ρ). Let ν = 2 2Hg(ρ)-2 (ρ ⊗ ρ). The matrix ν ∈ T µ⊗µ because 57 Tr(µ ⊗ µ)ν ≤ 1. Therefore I(ρ : ρ) = log TrT µ⊗µ (ρ ⊗ ρ) ≥ log m(ν)Trν(ρ ⊗ ρ) > + log m(ν)2 2Hg(ρ) Tr(ρρ ⊗ ρρ) > + 2Hg(ρ) -K(ρ, Hg(ρ)) + 2 log i λ 2 i ,

( 7 )

 7 If T ∈ T µ n ⊗µ n , then TrT * < 2 2n . This is because 1 ≥ TrT (µ n ⊗ µ n ) * > TrT (2 -n I ⊗ 2 -n I).Since the set of lower computable matrices of trace not more than 2 2n is enumerable, 2-2n T µ n ⊗µ n * < µ 2n . Assume I(|i : |i ) = log TrT µ n ⊗µ n |ii ii| = 2n -c. Then -log Tru 2n |ii ii| < + c. This means that K(ii|2 2n ) < + c. So K(i|2 n ) < + c. So 1 ≥ TrT µ n ⊗µ n µ⊗µ * > m(i|2 n ) 2 TrT µ n ⊗µ n |ii ii| * > 2 2n-3c. Thus c > + 2n/3. This implies that I(|i : |i ) = 2n -c < + 4n/3.

  one cannot clone a quantum state. The following theorem generalizes this no-go result, by showing there exist tensor products |ψ m that has signifigantly more Hg measure than |ψ . The following theorem presents a new proof to this result. ) is spanned by M basis vectors, where M is the number of multisets of size m from the set {1, . . . , N }. This is because for each such multiset S = {i 1 , . . . , i m }, one can construct a basis vector |ψ S that is the normalized superposition of all basis vectors of Sym(H m N ) that are permutations of S. If S = S, then |ψ S is orthogonal to |ψ S . Thus the dimension of Sym(H m

	Theorem 8 ([G 01]) log m+N -1 m	< + max |ψ Hg(|ψ ⊗m ) < + K(m) + log m+N -1 m
	Proof. Let H N be an N dimensional Hilbert space and let H m N be an m-fold tensor space of H N . Let Sym(H m N ) be the subspace of H m N consisting of all pure states of the form |ψ ⊗m . The subspace Sym(H m N N ) M , is m+N -1 because choosing a multiset is the same as splitting an interval of size m into N m intervals. For the upper bounds, let P S be the projector onto Sym(H m N ). If |ψ ∈ Sym(H m N ), then
	ψ| P S |ψ = 1 so

  computes a projection P of rank if it outputs a series of rank projections {P i } ∞ i=1 such that P -P i ≤ 2 -i . For computable projection operator P , I(P ; H) = min{K(p) -K(p|H) : p is a program that computes P }. Relativized to an n qubit mixed state σ, for computable 2 m rank projector P , 3m -2n < log max |φ ∈Image(P ) d(|φ |σ) + I( P ; H).Proof. Let p be a program that computes P . There is a simply defined algorithm A, that when given p and σ, outputs P n such that max |ψ ∈Image(P ) d(|ψ |σ) = + max |ψ ∈Image(Pn) d(|ψ |σ). Thus by Lemma 1, one gets that I(P n ; H) < + I(P ; H). The corollary follows from Theorem 23.

	Corollary 2 ([Eps23c])

Theorem 23 is in terms of elementary described projecctions and can be generalized to arbitrarily computable projections. For a matrix M , let M = max i,j |M i,j | be the max norm. A program p ∈ {0, 1} *

  Proof. Let state Z be NS random. Let {ρ n } be the density matrices associated with Z. Suppse not. Then there is δ ∈ (0, 1) and computable measurement systemB = {|b n 0 , |b n 1 } ∞ n=1 where µ B Z ({0, 1} ∞ \ MLR) > δ.Let {S m } be a universal ML test. Without loss of generality, this test is of the form

	Definition 11 (Bhojraj Random) A state Z is Bhojraj Random if for any computable measure-
	ment system B, µ B Z (MLR) = 1.
	Theorem 41 ([Bho21]) All NS Random states are Bhojraj Random states,

In[START_REF] Epstein | On the algorithmic information between probabilities[END_REF] probabilities over {0, 1} ∞ and T0 second countable topologies were also studied.

Note this definition can be generalized to arbitrary states, with I Prob (ETr2σ : F Tr1σ), where σ = ε(|ψ ), for quantum operation ε.

Thus for the diagonal 2 n-r × 2 n-r matrix σ with entries {v i } 2 n-r i=1 , z = U (σ ⊗ |0 r 0 r |)U * . By Proposition 3, since 1 -< Tr(p Z n) and z = Proj(z n ; p ), it must be that D(z , Z n) < √ . Thus using quantum operation η = (U, |0 r 0 r |, ∅) and input σ,

< + n -r + K(n, r) < + n -r + K(bb(r/2), r) < + n -r + r/2 + K(r)

Thus for every r there exists an n where Hoc (Z n) < n -r. This is because the additive constant of the above equation is not dependent on r.

Otherwise there is some R where for all r ≥ R, and q < bb(r/2), TrZ n(r,q) p r n(r,q) ≤ 1 -. Thus given R, L r , [Z], and a lower enumeration of , one can iterate through each r ≥ R and return an s such that TrZ n(r,s) p r n(r,s) > 1 -. This is because the set of rational numbers Q such that q > 1 -for all q ∈ Q can be enumerated and the set V = {v : TrZ n(r,v) p r n(r,v) > q, q ∈ Q} can be enumerated using the infinite encoding [Z] ∈ {0, 1} ∞ . The returned s is the first enumerated element of V . This number s has the property that s ≥ bb(r/2), and can be used to compute the prefix of the halting sequence over all programs of length ≤ r/2 as every such program that will halt will do so in less than s steps. Thus the halting sequence is computable relative to [Z] and thus Z ∈ QH.

Corollary 9 Let state Z ∈ QH. Then Z is NS random iff for all 0 < < 1, there is an r, where for all n, Hoc (Z n) > n -r.

Proof. Assume Z is NS random. Then for all 0 < < 1, Z passes each NS test at order 1 -. Then by Theorem 39 (1), for all 0 < < 1 there is an r where for all n, Hoc (Z n) > n-r. Assume Z is not NS random. Then there is some rational 0 < δ < 1 such that Z fails some NS test at order 1 -δ. Then by Theorem 39 (2), for = √ δ, for all r, there is an n where Hoc (Z n) < n -r.

Quantum Ergodic Sources

In [START_REF] Brudno | The Complexity of the trajectories of a Dynamical System[END_REF], Brudno proved that for ergodic measures η over bi-infinite sequences, for η-almost all sequences, the rate of the Kolmogorov complexity of their finite prefixes approaches the entropy rate of η. Therefore the average compression rate of sequences produced by η is not more than its entropy rate. In [BKM + 06], a quantum version of Brudno's theorem was introduced relating, in a similar fashion, Von Neumann entropy and BVL complexity (using the fidelity measure). The results provide two bounds with respect to two variants of Hbvl: approximate-scheme complexity and finite accuracy complexity.

In this subsection we provide a quantum variant of Brudno's theorem with respect to quantum communication complexity R . Differently from the Hbvl results, the bounds provided below are for almost all n, invariant to the accuracy term .

We define the quasilocal C * algebra A ∞ , which differs only from M ∞ in that it is a doubly infinite product space over Z. In particular, A is the C * algebra of qbits, i.e. 2 × 2 matrices acting on C 2 . For finite Λ ⊂ Z, A Λ = z∈Λ A z . part of the wavefunction over another, the decoherence of one part from the other. The result is a branching structure of the wavefunction and a collapse only in the phenomenological sense.

Branching Worlds

An example of a branching of universes can be seen in an idealized experiment with a single electron with spin |φ ↑ and |φ ↓ . This description can be found in [START_REF] Saunders | Many Worlds?: Everett, Quantum Theory, & Reality[END_REF]. There is a measuring apparatus A, which is in an initial state of |ψ A ready . After A reads spin-up or spin-down then it is in state |ψ A reads spin ↑ or |ψ A reads spin ↓ , respectively. The evolution for when the electron is solely spin-up or spin-down is

Furthermore, one can model the entire quantum state of an observer O of the apparatus, with

For the general case, the electron is in a state |φ = a |φ ↑ + b |φ ↓ , where |a| 2 + |b| 2 = 1. In this case, the final superposition would be of the form:

This is a superposition of two branches, each of which describes a perfectly reasonable physical story. This bifurcation is one method on how the quantum state of universe bifurcates into two branches.

Deriving the Born Rule

In my opinion, one of the main problems of MWT is its reconciliation of the Born rule, for which no proposed solution has universal consensus. Proof.

(