Overview
Syllabus
High-dimensional linear algebra in quantum algorith from quantum walks to matrix inversion
High-level explanation of quadratic speed-ups Quantum fast-forwarding (Apers & Sarlette 2018) We can implement a unitary V such that
Szegedy quantum walk based search Suppose we have some unknown marked vertices MCV. Quadratically faster hitting Hitting time: expected time to hit a marked verlax Starting from the stationary distr. Starting from the quantum states we can
k-distinctness Are there k distinct elements mapped to the same image?
Block-encoding A way to represent large matrices on a quantum computer efficiently
Quantum Singular Value Transformation (QSVT) Main theorem about OSVT (G, Su, Low, Wiebe 2018)
Amplitude amplification and estimation Fixed-point amplitude ampl. (Yoder, Low, Chuang 2014) Amplitude amplification problem: Given U such that
Detecting a bias in a quantum sampler Suppose we are given such that
Speeding up Monte Carlo methods Montanaro 2015 Sampling algorithm Suppose we have a sampling algorithm sampling from a random variable X.
Direct implementation of the pseudoinverse (HHL)
Application for Boolean equations - Chen & Gao 201
Continuous optimization Convex optimization
Taught by
Fields Institute