High-Dimensional Linear Algebra in Quantum Algorithms - From Quantum Walks to Matrix Inversion

Explore high-dimensional linear algebra in quantum algorithms through this comprehensive lecture. Delve into topics ranging from quantum walks to matrix inversion, covering quadratic speed-ups, quantum fast-forwarding, and Szegedy quantum walk-based search. Learn about k-distinctness, block-encoding, and Quantum Singular Value Transformation (QSVT). Examine amplitude amplification and estimation techniques, including fixed-point amplitude amplification. Discover methods for detecting bias in quantum samplers and speeding up Monte Carlo methods. Investigate the direct implementation of pseudoinverse (HHL) and its application to Boolean equations. Conclude with insights into continuous optimization and convex optimization in the quantum realm.

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