About Me
I am a Simons Quantum Postdoctoral Fellow at Simons Institute for the Theory of Computing at UC Berkeley, hosted by Umesh Vazirani. I got my Ph.D. from UT Austin in 2023, where I was very fortunate to be advised by Dana Moshkovitz.
My research interests mainly lie in theoretical computer science. Currently I’m working on quantum algorithms, optimization, and deep learning theory. I am always open to new topics.
I was visiting the Institute for Pure and Applied Mathematics (IPAM), UCLA for the long program Mathematical and Computational Challenges in Quantum Computing in 2023.
Publications
- Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
-
Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK
- Hongru Yang, Ziyu Jiang, Ruizhe Zhang, Zhangyang Wang, Yingbin Liang
- In Journal of Machine Learning Research (JMLR), (2024)
- [arXiv]
-
The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
- Zhiyan Ding, Ethan N. Epperly, Lin Lin, Ruizhe Zhang
- To appear in the 65th IEEE Symposium on the Foundations of Computer Science (FOCS'2024)
- [arXiv]
-
A General Algorithm for Solving Rank-one Matrix Sensing
- Lianke Qin, Zhao Song, Ruizhe Zhang
- In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS'2024)
- [arXiv] [Conference]
-
Fast Dynamic Sampling for Determinantal Point Processes
- Zhao Song, Junze Yin, Lichen Zhang, Ruizhe Zhang
- In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS'2024)
- [Conference]
-
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
- Zhao Song, Lichen Zhang, Ruizhe Zhang
- In Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS'2024)
- [arXiv] [Conference]
-
Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing
- Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
- In Proceedings of the Advances in Neural Information Processing Systems 36 (NeurIPS'2023)
- [arXiv] [Conference]
-
Quartic Samples Suffice for Fourier Interpolation
- Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
- In Proceedings of the 64th IEEE Symposium on the Foundations of Computer Science (FOCS'2023)
- [arXiv] [Conference]
-
Hyperbolic Extension of Kadison-Singer Type Results
- Ruizhe Zhang, Xinzhi Zhang
- In Proceedings of the 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP'2023)
- [arXiv] [Conference]
- Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
-
Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
- Tongyang Li, Ruizhe Zhang
- In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
- [arXiv] [Conference]
-
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
- Andrew Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
- In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
- Contributed talk at the 26-th Conference on Quantum Information Processing (QIP'2023)
- [arXiv] [Conference]
-
Fast Distance Oracles for Any Symmetric Norm
- Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
- In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
- [arXiv] [Conference]
-
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
- Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
- In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
- [arXiv] [Conference]
-
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
- Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang
- In Proceedings of the 26th International Conference on Randomization and Computation (RANDOM'2022)
- [arXiv] [Conference]
-
Hyperbolic Concentration, Anti-concentration, and
Discrepancy
- Zhao Song, Ruizhe Zhang
- In Proceedings of the 26th International Conference on Randomization and Computation (RANDOM'2022)
- [arXiv] [Conference]
-
Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
- Ruizhe Zhang, Guoming Wang, Peter Johnson
- In Quantum, Volume 6, Number 761 (2022)
- [arXiv] [Journal] [Quantum View]
-
Quantum Meets Minimum Circuit Size Problem
- Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
- In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS'2022)
- [arXiv] [eccc] [Conference]
-
Symmetric Sparse Boolean Matrix Factorization and Applications
- Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
- In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS'2022)
- [arXiv] [Conference]
-
Does Preprocessing Help Training Over-parameterized Neural Networks?
- Zhao Song, Shuo Yang, Ruizhe Zhang
- In Proceedings of the Advances in Neural Information Processing Systems 34 (NeurIPS'2021)
- [arXiv] [Conference]
-
New Approaches for Quantum Copy-Protection
- Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
- In Proceedings of the 41st Annual International Cryptology Conference (Crypto'2021)
- Contributed talk at the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'2021)
- [arXiv] [Conference]
- QED driven QAOA for network-flow optimization
-
On the Quantum Complexity of Closest Pair and Related Problems
- Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
- In Proceedings of the 35th Computational Complexity Conference (CCC'2020)
- Contributed talk at the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'2020)
- [arXiv] [Conference]
Manuscripts
-
Polynomial-Time Preparation of Low-Temperature Gibbs States for 2D Toric Code
- Zhiyan Ding, Bowen Li, Lin Lin, Ruizhe Zhang
- [arXiv]
-
Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters
- Zhao Song, Junze Yin, Ruizhe Zhang
- [arXiv]
-
Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction
- Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
- [arXiv]
-
A Dynamic Fast Gaussian Transform
- Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang
- [arXiv]
-
InstaHide's Sample Complexity When Mixing Two Private Images
- Baihe Huang, Zhao Song, Runzhou Tao, Ruizhe Zhang, Danyang Zhuo
- [arXiv]