Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

Watch this conference talk from TQC 2023 exploring innovative randomized quantum algorithms for linear algebra tasks that minimize qubit usage. Learn about a novel approach to sampling from matrix functions without quantum block encodings or coherent oracle access, requiring only log(N)+1 qubits for N×N Hermitian matrices. Discover how these space-efficient methods achieve comparable gate complexity to state-of-the-art approaches while eliminating the need for large quantum data structures. Explore practical applications including quantum linear system solving, sampling from ground and Gibbs states of Hamiltonians, and calculating Green's functions in quantum many-body systems. Presented by Samson Wang at the 18th Conference on the Theory of Quantum Computation, Communication and Cryptography at the University of Aveiro, this technical presentation demonstrates significant advances in making quantum algorithms more resource-efficient.