Ruizhe Zhang

Office: DSAI 3087

Email: rzzhang purdue dot edu

© 2025. All rights reserved.

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 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 scientific computing and engineering.

Please feel free to get in touch if we share interests.

Teaching

Publications

  • Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
    • Zhiyan Ding, Haoya Li, Lin Lin, HongKang Ni, Lexing Ying, Ruizhe Zhang
    • In Quantum, Volume 8, Number 1487 (2024)
    • [arXiv] [Journal]
  • 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
    • Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, Peter D. Johnson
    • Contributed talk at the third Quantum Computing Theory in Practice (QCTIP'2023)
    • In Quantum, Volume 7, Number 1167 (2023)
    • [arXiv] [Journal]
  • 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
  • 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
    • Yuxuan Zhang, Ruizhe Zhang, Andrew C. Potter
    • In Quantum, Volume 5, Number 510 (2021)
    • [arXiv] [Journal]
  • 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]