6 papers
Exact Coset Sampling for Quantum Lattice Algorithms
Yifan Zhang
We revisit the post-processing phase of Chen's Karst-wave quantum lattice algorithm (Chen, 2024) in the Learning with Errors (LWE) parameter regime. Conditioned on a transcript …
Algorithmic Locality via Provable Convergence in Quantum Tensor Networks
Siddhant Midha, Yifan F. Zhang, Daniel Malz +2
Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical gua…
Local Diffusion Models and Phases of Data Distributions
Fangjun Hu, Guangkuo Liu, Yifan F. Zhang +1
As a class of generative artificial intelligence frameworks inspired by statistical physics, diffusion models have shown extraordinary performance in synthesizing complicated data…
Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence
Siddhant Midha, Yifan F. Zhang
Tensor network contraction on arbitrary graphs is a fundamental computational challenge with applications ranging from quantum simulation to error correction. While belief propagat…
Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications
Yifan Zhang, Joe Kileel
Covering numbers are a powerful tool used in the development of approximation algorithms, randomized dimension reduction methods, smoothed complexity analysis, and others. In this…
Norming Sets for Tensor and Polynomial Sketching
Yifan Zhang, Joe Kileel
This paper develops the sketching (i.e., randomized dimension reduction) theory for real algebraic varieties and images of polynomial maps, including, e.g., the set of low rank ten…