62 citations · 151 across the 25 of their papers we have counts for
33 papers
Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
Ruizhe Zhang
Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\math…
Hit-and-Run Mixes as Fast as the Ball Walk
Ruizhe Zhang
Let be an isotropic convex body. We prove that the hit-and-run walk, started from any -warm distribution, reaches total-variation distance f…
Optimal Extrapolation Bounds for Sparse Fourier Sums
Ruizhe Zhang
We prove a sharp extrapolation bound for -sparse Fourier sums with arbitrary real frequencies and no separation assumption. For every with $λ_j\…
Overcoming the Lamb Shift in System-Bath Interaction Models via KMS Detailed Balance: High-Accuracy Thermalization with Time-Bounded Interactions
Hongrui Chen, Zhiyan Ding, Ruizhe Zhang
We investigate quantum thermal state preparation algorithms based on system-bath interactions and uncover a surprising phenomenon in the weak-coupling regime. We rigorously prove t…
Polynomial-Time Preparation of Low-Temperature Gibbs States for 2D Toric Code
Zhiyan Ding, Zeph Landau, Bowen Li +2
We propose a polynomial-time algorithm for preparing the Gibbs state of the two-dimensional toric code Hamiltonian at any temperature, starting from any initial condition, signific…
Quantum Speedup for Spectral Approximation of Kronecker Products
Yeqi Gao, Zhao Song, Ruizhe Zhang
Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render…
Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters
Zhao Song, Junze Yin, Ruizhe Zhang
Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix and a vector , the goal is to find such that…
Beyond Classical Attention: Quantum Attention for Scalable Computation
Xuyang Guo, Zhao Song, Xin Yang +1
As large language models (LLMs) demonstrate outstanding performance across various tasks, attention-driven models have profoundly transformed the field of machine learning. Since a…
Efficient Algorithm for Solving Hyperbolic Programs
Yichuan Deng, Zhao Song, Lichen Zhang +1
Hyperbolic polynomials is a class of real-roots polynomials that has wide range of applications in theoretical computer science. Each hyperbolic polynomial also induces a hyperboli…
A Hyperbolic Extension of Kadison-Singer Type Results
Ruizhe Zhang, Xinzhi Zhang
In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Singer conjecture. It states that for independent random vectors that have expected squa…
A General Algorithm for Solving Rank-one Matrix Sensing
Lianke Qin, Zhao Song, Ruizhe Zhang
Matrix sensing has many real-world applications in science and engineering, such as system control, distance embedding, and computer vision. The goal of matrix sensing is to recove…
Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK
Hongru Yang, Ziyu Jiang, Ruizhe Zhang +2
We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime, where the networks' biases are initialized to some constant rather than zero. We prove t…
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
Josh Alman, Jiehao Liang, Zhao Song +2
Over the last decade, deep neural networks have transformed our society, and they are already widely applied in various machine learning applications. State-of-art deep neural netw…
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Andrew M. Childs, Tongyang Li, Jin-Peng Liu +2
Given a convex function , the problem of sampling from a distribution is called log-concave sampling. This task has wide app…
Quartic Samples Suffice for Fourier Interpolation
Zhao Song, Baocheng Sun, Omri Weinstein +1
We study the problem of interpolating a noisy Fourier-sparse signal in the time duration from noisy samples in the same range, where the ground truth signal can be any …
Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
Tongyang Li, Ruizhe Zhang
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set and a function $F\colon\mathbb{R}^{n…
Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
Guoming Wang, Daniel Stilck França, Ruizhe Zhang +2
A milestone in the field of quantum computing will be solving problems in quantum chemistry and materials faster than state-of-the-art classical methods. The current understanding…
A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework
Baihe Huang, Shunhua Jiang, Zhao Song +2
This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SD…
Fast Distance Oracles for Any Symmetric Norm
Yichuan Deng, Zhao Song, Omri Weinstein +1
In the Distance Oracle problem, the goal is to preprocess vectors in a -dimensional metric space into a cheap data st…
Improved Reconstruction for Fourier-Sparse Signals
Yeqi Gao, Zhao Song, Baocheng Sun +2
We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the \emph{Set Query} problem -- which asks to efficiently reconstruct (a subset of) a -d…
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Jason Gaitonde, Max Hopkins, Tali Kaufman +2
We study the relationship between the underlying structure of posets and the spectral and combinatorial properties of their higher-order random walks. While fast mixing of random w…
A Dynamic Low-Rank Fast Gaussian Transform
Baihe Huang, Zhao Song, Omri Weinstein +3
The \emph{Fast Gaussian Transform} (FGT) enables subquadratic-time multiplication of an Gaussian kernel matrix with…
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
Zhao Song, Lichen Zhang, Ruizhe Zhang
We consider the problem of training a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-paramet…
Does Preprocessing Help Training Over-parameterized Neural Networks?
Zhao Song, Shuo Yang, Ruizhe Zhang
Deep neural networks have achieved impressive performance in many areas. Designing a fast and provable method for training neural networks is a fundamental question in machine lear…