About Me
I am an assistant professor in the Department of Computer Science at Purdue University. Prior to joining Purdue, I was a Simons Quantum Postdoctoral Fellow at Simons Institute for the Theory of Computing at University of California, Berkeley (hosted by Prof. Umesh Vazirani and Prof. Lin Lin) and a Visiting Scholar at the Institute for Pure and Applied Mathematics (IPAM), UCLA for the long program Mathematical and Computational Challenges in Quantum Computing. I received my Ph.D. in Computer Science from the University of Texas at Austin in 2023, where I was very fortunate to be advised by Dana Moshkovitz. I currently serve as an editor of the journal Quantum.
I am broadly interested in theoretical computer science. My current research focuses on algorithmic problems in quantum computing, optimization, and machine learning theory, with applications to real-world problems.
Please feel free to get in touch if we share interests.
Teaching
- CS58500 - Theoretical Computer Science Toolkit (Spring 2026)
- CS59300 - Algorithms for Data Science (Fall 2025)
Publications
- Polynomial-Time Preparation of Low-Temperature Gibbs States for 2D Toric Code
- Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra
- 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
-
Overcoming the Lamb Shift in System-Bath Models via KMS Detailed Balance: High-Accuracy Thermalization with Time-Bounded Interactions
- Hongrui Chen, Zhiyan Ding, 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]