Han-Hsuan Lin

I am an assistant professor of the CS department of National Tsing Hua University, Taiwan. My research areas include quantum algorithms, quantum query complexities, post-quantum cryptography, and quantum machine learning.


  • Undergraduate (2006-2009): California Institute of Technology

  • Graduate (2009-2015): Massachusetts Institute of Technology under Edward Farhi

Previous Job


Conference Papers

  • Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin. On relating one-way classical and quantum communication complexities. arXiv preprint arXiv:2107.11623 [cs.CC] (2021). Accepted talk at AQIS 2021, 21th Asian Quantum Information Science Conference .

  • Chung, Kai-Min, and Han-Hsuan Lin. ”On the Sample Complexity of PAC Learning Quantum Process.” arXiv preprint arXiv:1810.10938 (2018). Accepted talk at TQC 2021, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography

  • Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang. ”On the Quantum Complexity of Closest Pair and Related Problems”. arXiv preprint arXiv:1911.01973 (2019). Accepted talk at CCC 2020, the 35th Computational Complexity Conference.

  • Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang. ”Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quan- tum machine learning”. arXiv preprint arXiv:1910.06151 (2019). Accepted talk at QIP 2020, the 23rd Annual Conference on Quantum Information Processing.

  • Chia, Nai-Hui, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. ”Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches.” arXiv preprint arXiv:1901.03254 (2019). Accepted talk at MFCS 2020, the 45th International Symposium onMathematical Foundations of Computer Science.

  • Chia, Nai-Hui, Han-Hsuan Lin, and Chunhao Wang. ”Quantum-inspired sublinear classical algorithms for solving low-rank linear systems.” arXiv preprint arXiv:1811.04852 (2018). Accepted talk at ISAAC 2020, The 31st International Symposium on Algorithms and Computation.

  • D. Aggarwal, K.-M. Chung, H.-H. Lin, and T. Vidick. A Quantum-Proof Non-malleable Extractor. In Annual International Conference on the Theory and Applications of Cryp- tographic Techniques, pp. 442-469. Springer, Cham, 2019. Available as e-print at arXiv:1710.00557 [quant-ph]. Accepted talk at Eurocrypt 2019, the 38th Annual Inter- national Conference on the Theory and Applications of Cryptographic Techniques.

  • C. Y.-Y. Lin and H.-H. Lin. Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. Theory of Computing 12(18), 2016, 1-35. Available as e-print at arXiv:1410.0932 [quant-ph], 2014. Accepted talk at CCC 2015, the 30th Computational Complexity Conference, and QIP 2015, the 18th Conference on Quantum Information Processing.

  • S. Kimmel, C. Y.-Y. Lin, and H.-H. Lin. Oracles with costs. Available as e-print at arXiv:1502.02174 [quant-ph], 2015. Accepted talk at TQC 2015, the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography.


  • Kai-Min Chung, Yi Lee, Han-Hsuan Lin, and Xiaodi Wu. Constant-round Blind Classical Verification of Quantum Sampling. Available as e-print at arXiv:2012.04848 [quant-ph], 2020.

  • E. Crosson, E. Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor. Different strategies for opti- mization using the quantum adiabatic algorithm. Available as e-print at arXiv:1401.7320 [quant-ph], 2014.


email: linhh at cs.nthu.edu.tw

Office: 台達(delta) 610