Appears in collection : 2024 - PC2 - Random tensors and related topics

Given a vector v, what is the closest k-sparse vector? The answer to this question is usually that we should take the largest k entries of v. It turns out that we can do better with randomized approximations. When approximating pure bipartite entangled states with states of low Schmidt rank, this means that mixed approximations outperform pure approximations. This fact has application to classical algorithms for matrix product states by improving the truncation step, and to quantum algorithms for Hamiltonian simulation.