Quantum Information Science II, Part 3 - Advanced quantum algorithms and information theory

A quick application of Fourier transform: quantum phase estimation

Abelian groups: decomposition into group of characters

Abelian groups: isomorphism to products of cyclic groups

Amplitude amplification

Amplitude amplification – comments

Application – rejection sampling and Gibbs sampling

Models of quantum algorithms

Mutual information – definition and examples

Application of the dihedral group HSP – the hidden shift problem

Application to lattice problems – quantum dihedral HSP

Mutual information – in terms of conditional entropy

Mutual information – the binary symmetric channel

Conditional entropy

Conditional mutual information

Mutual information example – the binary symmetric channel

Noisy coding theorem – achievability proof

Converse of the noiseless coding theorem

Noisy coding theorem – achievability proof – joint typicality claim

Quantum entropies: conditional entropy issues

Data processing inequality

Quantum entropies: von Neumann entropy and relative entropy

Noisy coding theorem – proof of joint typicality

Efficient algorithm for Fourier transform over any decomposable Abelian group

Quantum entropy inequalities that still hold

Overview of known quantum algorithms