Yi-Kai Liu

I am a computer scientist at the National Institute of Standards and Technology (NIST), in the Applied and Computational Mathematics Division. I am also a Fellow and adjunct professor at the NIST-UMD Joint Center for Quantum Information and Computer Science (QuICS). 

I do research on quantum computation, including quantum algorithms and complexity, quantum and post-quantum cryptography, and characterization of experimental quantum devices (QCVV). 

I have also contributed to NIST standards for post-quantum cryptography, and served as the NIST-side QuICS co-director from 2020 to 2025.

Finally, I have (less expert) interests in machine learning, software-defined radio, and formal verification of software and hardware.

My academic history: postdoc (UC Berkeley), postdoc (Institute for Quantum Information, Caltech), PhD in computer science (UC San Diego), BA in mathematics (Princeton). 

You can reach me via e-mail at: yi-kai.liu [at] nist [dot] gov

or: yikailiu [at] umd [dot] edu

or: yikailiu00 [at] gmail [dot] com

Announcements

Information about graduate study, postdocs and faculty jobs at QuICS

Selected Publications (for a complete list, see Google Scholar and the Arxiv)

J. Rajakumar, J. D. Watson and Y.-K. Liu, "Polynomial-time Classical Simulation of Noisy IQP Circuits with Constant Depth," Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1037-1056, [link].

Y.-K. Liu and D. Moody, "Post-quantum cryptography and the quantum future of cybersecurity," Phys. Rev. Applied 21 (4), 040501 (2024), [link]. 

Y.-K. Liu, "An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors," arXiv:2310.03735.

K. Huang, D. Farfurnik, A. Seif, M. Hafezi, Y.-K. Liu, "Random Pulse Sequences for Qubit Noise Spectroscopy," arXiv:2303.00909.

G. Alagic et al, "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process," NIST Interagency/Internal Report (NISTIR) 8413 (2022) [doi].

A. Seif, M. Hafezi, Y.-K. Liu, "Compressed Sensing Measurement of Long-Range Correlated Noise," arXiv:2105.12589. US Patent 2023/0058207.

Z. Ji, Y.-K. Liu, F. Song, "Pseudorandom Quantum States," CRYPTO 2018, part 3, pp.126-152 [doi], arXiv:1711.00385. 

F. Krahmer and Y.-K. Liu, "Phase Retrieval Without Small-Ball Probability Assumptions," IEEE Trans. Info. Theory 64(1), pp.485-500 (January 2018) [doi]; arXiv:1604.07281. 

Y.-K. Liu, "Privacy amplification in the isolated qubits model," Eurocrypt 2015, pp.785-814 [doi]; Arxiv:1410.3918. 

Y.-K. Liu, "Single-shot security for one-time memories in the isolated qubits model," CRYPTO 2014, Part II, pp.19-36 [doi]; Arxiv:1402.0049. 

S. T. Flammia, D. Gross, Y.-K. Liu and J. Eisert, "Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators," New J. Phys. 14, 095022 (2012) [link]. ArXiv:1205.2300. 

A. Anandkumar, D. P. Foster, D. Hsu, S. M. Kakade and Y.-K. Liu, "A Spectral Algorithm for Latent Dirichlet Allocation," Algorithmica 72 (1), pp.193-214 (2015) [doi]. Earlier version: Advances in Neural Information Processing Systems (NIPS), pp.926-934 (2012) [link]. ArXiv:1204.6703. 

A. Ambainis, A. M. Childs and Y.-K. Liu, "Quantum property testing for bounded-degree graphs," Proc. RANDOM 2011, Lecture Notes in Computer Science 6845, pp.365-376. ArXiv:1012.3174. 

S. T. Flammia and Y.-K. Liu, "Direct Fidelity Estimation from Few Pauli Measurements," Phys. Rev. Lett. 106, 230501 (2011) [link]. Arxiv:1104.4695. 

Y.-K. Liu, "Universal low-rank matrix recovery from Pauli measurements," Advances in Neural Information Processing Systems (NIPS), pp.1638-1646 (2011) [link]. Arxiv:1103.2816. 

M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin and Y.-K. Liu, "Efficient Quantum State Tomography," Nature Commun. 1, 149 (2010) [link]. ArXiv:1101.4366. 

D. Gross, Y.-K. Liu, S.T. Flammia, S. Becker and J. Eisert, "Quantum state tomography via compressed sensing," Phys. Rev. Lett. 105, 150401 (2010) [link]. ArXiv:0909.3304. 

Y.-K. Liu, "Quantum Algorithms Using the Curvelet Transform," Proc. ACM Symposium on Theory of Computing (STOC), pp.391-400, 2009. ArXiv:0810.4968.

Y.-K. Liu, M. Christandl and F. Verstraete, "N-representability is QMA-complete," Phys. Rev. Lett. 98, 110503 (2007) [link]; Arxiv preprint: quant-ph/0609125. 

Y.-K. Liu, "Consistency of Local Density Matrices is QMA-complete," Proc. RANDOM 2006, pp.438-449; Arxiv preprint: quant-ph/0604166.