# EXCLUDE

Key: mat4430.uio.c
Title: MAT4430 -- Quantum Information Theory

[Macros]:

<Math>: <R> | <mathbb>:R
<Math>: <Z> | <mathbb>:Z
<Math>: <Q> | <mathbb>:Q

<Math>: <Sq>:Math | <raw!>:<#>\left[#1\right]<#>
<Math>: <Cr>:Math | <raw!>:<#>\left\{#1\right\}<#>
<Math>: <Pa>:Math | <raw!>:<#>\left(#1\right)<#>
<Math>: <Br>:Math | <raw!>:<#>\{#1\}<#>
<Math>: <Vb>:Math | <lvert><1><rvert>

<Math>: <Op>:Math | <operatorname>:{#1}

<Math>: <Pr>:Math | <operatorname>:<mathbb>:P <1>
<Math>: <Ex>:Math | <operatorname>:<mathbb>:E <1>
<Math>: <E>:Math | <operatorname>:<mathbb>:E <1>
<Math>: <Var>:Math | <operatorname>:Var <1>
<Math>: <Min>:Math | <operatorname>:Min <1>
<Math>: <Max>:Math | <operatorname>:Max <1>

<Math>: <Lim>:Math | <underset>:{#1}:{<operatorname>:Lim}
<Math>: <LimSup> | <operatorname>:LimSup
<Math>: <LimInf> | <operatorname>:LimSup

<Math>: <Log0> | <operatorname>:Log
<Math>: <Log>:Math | <operatorname>:Log <1>
<Math>: <Exp>:Math | <operatorname>:Exp <1>

<Math>: <Tr>:Math | <operatorname>:Tr <1>
<Math>: <Bra>:Math | << <1> <vert>
<Math>: <Ket>:Math | <vert> <1> >>
<Math>: <Dim>:Math | <operatorname>:Dim <1>

<Math>: <hash> | <#>\#<#>

<Math>: <PowsP> | <operatorname>:<mathcal>:P

# Measurable space over #1 with sigma algebra #2
<Math>: <MeasurableSpace>:Math:Math | {<mathcal>:M}_{#1, #2}
# Measure space over #1 with sigma algebra #2 and measure #3
<Math>: <MeasureSpace>:Math:Math:Math | { {<mathcal>:M}_{#1, #2, #3} }

{Alias}:

glm: generalized-linear-model
vs: vector-space
mat: matrix

[Content]:

###################
<H2>: Lecture notes

######################################## C
<H3>: 1 | Elements of probability theory

# <Definition>: def-1.4 | Definition | :Defines [
#   > statistical-distance | [Statistical distance; Total variation distance]
# ]
# <Statement>: thm-1.6 | Theorem 1.6 | [
#   > Markov's inequality
#   > Chebychev's inequality
# ]

###################################### C
<H3>: 2 | Source coding and typicality
<Statement>: theorem-2.1 | Perfect compression impossible | [
  > (At least {<$>: n <Log> \#\Σ} bits are needed to encode all words in {<$>: Σ^n})
]
<Proof>: theorem-2.1-proof | Proof
<Notion>: information-source | Information source | [Random variable {<$>: X :: Ω <to> Σ^n}]
<Notion>: lossy-compression-scheme | Lossy compression scheme
<Notion>: lossless-compression-scheme | Lossless compression scheme

<Notion>: delta-sufficient | δ-sufficient subset for <$>:X | [
  > ...
  > (Given a selection of words, there is only probability of δ of choosing a non-selected word.)
]
<Notion>: delta-essential-bit-content | δ-essential bit content of <$>:X | [
  > {<$>: H_<delta> (X) = {<Min>: \{\ {<Log>: \|\ S \|\ \}\}}} where <$>:S is δ-sufficient for {<$>:X}.
  > (The number of bits needed to encode the smallest δ-sufficient set. This is a
    lower bound on the number of bits;; can also be thought of as the number in the
    best case compression.)
]
<Notion>: raw-bit-content | Raw bit content of <$>:X | [
  > {<$>: H_0 (X) = {<Log>: <Vb>: {Σ^n}} = n{<Log>: <Vb>: Σ} },
  > (Number of bits needed to encode any value of {<$>: X}.)
]
<Notion>: lossy-compression-scheme | Lossy compression scheme | [
  > Functions {<$>: E :: Σ^n <to> {<Br>: 0, 1}^m} and {<$>: D :: {<Br>: 0, 1} <to> Σ^n}
    where {<$>: P(D <circ> E(x) = x) <ge> 1 - δ}.
]
<Notion>: compression-rate | Compression rate of a compression scheme | [
  > {<$>: <frac>:m:n}, # Must have comma todo remove
  > (Bits per word)
]
<Statement>: theorem-2.5 | Theorem | [
  > For any source <$>:X and any δ, there is a compression scheme with m bits iff
    {<$>: m <ge> H_δ (X)}.
  > (Obviously, since {<$>: H_δ (X)} bits encodes the smallest δ-sufficient subset of {<$>: X} )
]
<Notion>: discrete-memoryless-source | Discrete memoryless information source | [
# <Notion> discrete-memoryless-source | [Discrete memoryless information source; DMS] | [
  > A sequence of iid random variables {<$>: X_i :: Ω <to> Σ}.
    {<$>: X^n = (X_1, X_2, <dots>, X_n)}.
  > (A data source where the word distribution is derived from a distribution on the alphabet.)
  > (Monkey on a typewriter)
]
<Notion>: shannon-entropy | Shannon entropy of distribution {<$>: p} | [
  > {<$>: H(p) = -<sum>_x p(x) {<Log>: p(x)} }, ###########
]
<Statement>: theorem-2.7 | Theorem | [
  > Given <$>:{ϵ, δ} there exists an <$>:N where {<$>: {<Vb>: <frac>:1:n H_δ (X^n) - H(p) } <le> ϵ }
  > (As the length of words increase, the Shannon entropy is the limiting compression rate.)
]
<Proof>: theorem-2.7-proof | Proof | [
  > ...
]
<Statement>: theorem-2.8 | Shannon's source coding theorem | [
  > ...
  > (For a DMS, rates are close to the Shannon entropy when n is big.)
  > (Any sequence of schemes with better compression than Shannon by ϵ must always fail.)
]
<Proof>: theorem-2.8-proof | Proof
<Note>: note-2.1 | Note | [
#  <Li>: [
#    > {<$>: 2^{-nH(p)}} - probability of an average string.
#    > {<$>: nH(p)} - expected number of bits to encode a string / number of bits to encode an average string. (bits / word)
#    > {<$>: H(p)} - compression rate of an average string. (bits / character)
#  ]
]
<Statement>: lemma-2.10 | Lemma | [
  > {<$>: {<Vb>: {<mathcal>:T}_{n, <epsilon>} (p)} << 2^{n(H(p)+<epsilon>)}},
  > (...)
  > (As {<$>: n <to> <infty>}, <$>:X^n will almost surely be a typical string.)
]
<Proof>: theorem-2.10-proof | Proof | [
  > TODO
]
<Example>: binary-entropy-example | Binary entropy example

# <Definition>: def-2.2 | Definition 2.2 | [
#   > (δ being an acceptable probability of losing information in a lossy compression scheme.)
# ]
# <Definition>: def-2.3 | Definition 2.3 | :Defines [
#   > delta-essential-bit-content | δ-essential bit content of X
#   > raw-bit-content | Raw bit content of X
# ]
# <Definition>: def-2.4 | Definition 2.4 | :Defines [
#   > lossy-compression-scheme | Lossy compression scheme
#   > compression-scheme-rate | Rate of compression scheme
# ]
# <Statement>: thm-2.5 | Theorem 2.5 | [
#   > ...
# ]
# <Statement>: thm-2.7 | Theorem 2.7 | [
#   > 1) There is a
# ]
# <Definition>: def-2.7 | Definition | :Defines [
#   > shannon-entropy | Entropy of p
# ]
# <Statement>: thm-2.8 | Theorem 2.8 (Shannon's source coding theorem) | [
#   > 1) There is a
# ]
#
# <Definition>: def-2.9 | Definition 2.9 | :Defines [
#   > typical-string | ϵ-typical string
# ]
# <Statement>: lemma-2.10 | Lemma 2.10 (Properties of typical strings) | [
#   > ...
# ]


########################
<H3>: 3 | The relative entropy


<Statement>: chernoff-stein-lemma | Chernoff--Stein lemma | [
  > ...
  > (?)
]
<Statement>: corollary-3.3 | Corollary | [
  > ...
  > ( )
]



############################################
<H3>: 4 | Noisy classical channels and codes


#############################################
<H3>: 5 | The capacity of a classical channel


<Notion>: channel-mutual-information | Channel mutual information
<Statement>: theorem-5.6 | Shannon's channel coding theorem

<Statement>: theorem-5.8 | Theorem | [
  > (The capacity of a channel is 0 iff there exists a degenerate distribution)
]




########################
<H3>: 6 | Quantum states

<Note>: postulate-1 | Postulate I | [
  > For a (finite-dimensional) quantum system there is an associated complex Euclidean
    space {<$>: <mathcal>:H}, a Hilbert space, called the state space.
]
<Note>: postulate-2 | Postulate II | [
  > A state of a quantum system is described by a positive semidefinite operator
    {<$>: <rho> <in> B(<mathcal>:H )^+} where {<$>: <Tr>:<rho> = 1}.
]
<Notion>: quantum-states | Quantum states on <$>:<mathcal>:H | [
  > {<$>: <mathcal>:D ( <mathcal>:H ) },
]
<Statement>: theorem-6.1 | Theorem | [
  > Any quantum state can be written as
    {<$>: <rho> = <sum>_i^{Dim H} p_i <Ket>:x_i <Bra>:x_i }
    for an orthonormal basis.
]
<Notion>: pure-state | Pure state

##############################
<H3>: 7 | Measurements
<Notion>: povm | [POVM; Positive operator valued measure]
<Notion>: pvm | [PVM; Projection valued measure]
<Notion>: von-neumann-measurement | von-Neumann measurement
<Notion>: measurement-wrt-basis | Measurement wrt. a basis
<Notion>: observable | Observable | [
  > A Hermitian operator.
]
<Statement>: theorem-7.3 | Theorem | [
  > ...
]

###########################
<H3>: 8 | Composite systems and entanglement
<Note>: postulate-4 | Postulate IV (Composite quantum systems)
<Notion>: separable-state | Separable state {<$>: H_A <otimes> H_B}
<Notion>: entangled-state | Entangled state of {<$>: H_A <otimes> H_B}
<Notion>: maximally-entangled-state | Maximally entangled state {<$>: H_A <otimes> H_B}

<>:


##################
<H3>: 11 | Open systems and quantum channels
<Notion>: purification | Purification of a state
<Statement>: theorem-11.4 | Theorem (Existence of purifications)
<Notion>: ad-map | Ad map
<Notion>: quantum-channel | Quantum channel
<Notion>: depolarizing-channel | Depolarizing channel
<Notion>: identity-channel | Identity quantum channel
<Notion>: unitary-quantum-channel | Unitary quantum channel
<Notion>: replacement-quantum-channel | Replacement quantum channel
<Notion>: choi-operator | Choi operator of T
<Notion>: choi-matrix | Choi matrix of T
<Statement>: theorem-11.5 | Theorem (Positivity of T, Choi T)

##############
<H3>: Appendix A

<H3>: Appendix B
<Notion>: tensor-product | Tensor product
<Notion>: kronecker-product | Kronecker product of A and B
<Statement>: theorem-b.4 | Theorem (Schmidt decomposition)
<Proof>: theorem-b.4-proof | Proof
<Notion>: schmidt-decomposition | Schmidt decomposition of a tensor
<Notion>: schmidt-rank | Schmidt rank of a decomposition