Yi-Kai Liu
I am a staff 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 and theoretical computer science, in particular, quantum algorithms and complexity, quantum state tomography, machine learning, and quantum cryptography.
Previously I was a postdoc in Computer Science at UC Berkeley, and a postdoc at the Institute for Quantum Information at Caltech. I received a PhD in computer science from UC San Diego, and a BA in mathematics from 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
Apply here for postdoc jobs at QuICS, at the University of Maryland. This includes the Hartree Postdoctoral Fellowship, which covers all areas of quantum information, as well as other postdoctoral positions, which may focus on specific topics. Applications are due on Dec. 1, 2019.
Apply here for NRC postdoc jobs at NIST. (My research group is listed here.) Applications are due on Feb. 1 and Aug. 1 each year.
For graduate admissions, please apply to the Computer Science and Physics Departments at the University of Maryland.
Some Recent Talks
Compressed Sensing Measurement of Long-Range Correlated Noise, short talk by Alireza Seif, June 2021.
Lectures on quantum algorithms (part 1, exercises 1, part 2, exercises 2, part 3, exercises 3) at the 2019 Illinois Quantum Computing Summer School.
Quantum System Tomography, ARO/LPS Workshop on Quantum Characterization, Verification and Validation (QCVV), July 2017.
QuICS is hosting QCrypt 2016, the 6th International Conference on Quantum Cryptography, Sept. 12-16, 2016, in Washington, DC!
Tamper-Resistant Cryptographic Hardware in the Isolated Qubits Model, QCrypt 2014.
Universal Low-rank Matrix Recovery using Pauli Measurements, 2012.
Low-rank Methods for Learning Quantum States (joint work with S. Becker, B. Brown, J. Eisert, S. T. Flammia and D. Gross), Workshop on Low-rank Methods for Large-scale Machine Learning, NIPS 2010.
Preparing Lattice Superpositions on a Quantum Computer, Workshop on Post-Quantum Information Security, Joint Quantum Institute, Oct. 2010.
N-representability is QMA-complete (joint work with M. Christandl and F. Verstraete), Workshop on Quantum Marginals and Density Matrices, Fields Institute, July 2009.
Quantum Algorithms Using the Curvelet Transform, STOC 2009.
News Articles
S. P. Jordan and Y.-K. Liu, "Quantum Cryptanalysis: Shor, Grover, and Beyond," IEEE Security & Privacy 16(5), pp.14-21, September/October 2018, [doi].
Y.-K. Liu, "Quantum information: Show, don't tell," Nature Physics (2014) [doi] ("news and views" article about quantum PCA).
C. Boutin, "Quantum Physics Could Make Secure, Single-Use Computer Memories Possible," NIST Tech Beat, Jan. 14, 2014 [link].
Joint Research Projects
NIST Quantum Information Program
NIST Standards for Post-Quantum Cryptography
Research projects at UMD:
Scalable Certification of Quantum Computing Devices and Networks (coming soon)
Quantum Optimization, Machine Learning and Simulation (coming soon)
Optimal Measurements for Scalable Quantum Technologies (2014-present)
Teaching
CS138 Computer Algorithms, Spring 2009 (a course on approximation algorithms for combinatorial optimization, at Caltech).
Papers (or try the handy Arxiv listing)
A. Seif, M. Hafezi, Y.-K. Liu, "Compressed Sensing Measurement of Long-Range Correlated Noise," arXiv:2105.12589.
T. L. Scholten, Y.-K. Liu, K. Young, R. Blume-Kohout, "Classifying single-qubit noise using machine learning," arXiv:1908.11762.
I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, M. Kliesch, "Recovering quantum gates from few average gate fidelities," Phys. Rev. Lett. 121, 170502 (2018) [doi], arXiv:1803.00572. (Keywords: quantum process tomography, phase retrieval, compressed sensing.)
Z. Ji, Y.-K. Liu, F. Song, "Pseudorandom Quantum States," CRYPTO 2018, part 3, pp.126-152 [doi], arXiv:1711.00385. (Keywords: quantum cryptography, quantum money.)
V. Dunjko, Y.-K. Liu, X. Wu, J. M. Taylor, "Super-polynomial separations for quantum-enhanced reinforcement learning," arXiv:1710.11160. (Keywords: quantum machine learning, quantum algorithms.)
R. Perlner, Y.-K. Liu, "Thermodynamic Analysis of Classical and Quantum Search Algorithms," arXiv:1709.10510. (Keywords: quantum algorithms, classical reversible computation, post-quantum cryptography.)
P. Bierhorst, E. Knill, S. Glancy, Y. Zhang, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, M. J. Stevens, L. K. Shalm, "Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals," Nature 556:223-226 (2018) [doi], Arxiv:1803.06219, Arxiv:1702.05178. (Keywords: quantum cryptography, trusted hardware.)
C. Shen, R. W. Heeres, P. Reinhold, L. Jiang, Y.-K. Liu, R. J. Schoelkopf, and L. Jiang, "Optimized Tomography of Continuous Variable Systems Using Excitation Counting," Phys. Rev. A 94, 052327 [doi]. ArXiv:1606.07554. (Keywords: quantum state tomography.)
~ ~ ~ ~ ~ ~ ~
S. Kimmel and Y.-K. Liu, "Phase Retrieval Using Unitary 2-Designs," SampTA 2017, pp.345-349, [doi]; Arxiv:1510.08887. (Keywords: Phase retrieval, quantum process tomography, compressed sensing.)
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. (Keywords: Phase retrieval, PhaseLift.)
F. Krahmer and Y.-K. Liu, "Phase Retrieval Without Small-Ball Probability Assumptions: Stability and Uniqueness," SampTA 2015, pp.411-414, [link].
F. Krahmer and Y.-K. Liu, "Phase Retrieval Without Small-Ball Probability Assumptions: Recovery Guarantees for PhaseLift," SampTA 2015, pp.622-626, [link].
Y.-K. Liu, "Privacy amplification in the isolated qubits model," Eurocrypt 2015, pp.785-814 [doi]; Arxiv:1410.3918. (Keywords: quantum cryptography, trusted hardware.)
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. (Keywords: quantum cryptography, trusted hardware.)
Y.-K. Liu, "Building One-Time Memories from Isolated Qubits," Innovations in Theoretical Computer Science (ITCS) 2014, pp.269-286; Arxiv:1304.5007. (Keywords: quantum cryptography, trusted hardware.)
~ ~ ~ ~ ~ ~ ~
J. Conroy, S. T. Davis, J. Kubina, Y.-K. Liu, D. P. O’Leary and J. D Schlesinger, "Multilingual Summarization: Dimensionality Reduction and a Step Towards Optimal Term Coverage," MultiLing 2013 (Workshop on Multilingual Multi-document Summarization), pp.55-63 [link]. (Keywords: document topic modeling, matrix factorization.)
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. (Keywords: quantum state and process tomography, compressed sensing.)
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]. Conference version: Advances in Neural Information Processing Systems (NIPS), pp.926-934 (2012) [link]. ArXiv:1204.6703. (Keywords: document topic modeling, tensor decompositions.)
M. Ohliger, V. Nesme, D. Gross, Y.-K. Liu and J. Eisert, "Continuous-variable quantum compressed sensing," ArXiv:1111.0853. (Keywords: quantum state tomography, compressed sensing.)
~ ~ ~ ~ ~ ~ ~
A. D. Bookatz, S. P. Jordan, Y.-K. Liu and P. Wocjan, "Quantum nonexpander problem is quantum-Merlin-Arthur-complete," Phys. Rev. A 87, 042317 (2013) [link]; ArXiv:1210.0787. (Keywords: quantum complexity theory, quantum expanders.)
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. (Keywords: quantum algorithms, graph theory.)
S. T. Flammia and Y.-K. Liu, "Direct Fidelity Estimation from Few Pauli Measurements," Phys. Rev. Lett. 106, 230501 (2011) [link]. Arxiv:1104.4695. (Keywords: quantum state certification.)
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. (Keywords: matrix completion, quantum state tomography, compressed sensing.)
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. (Keywords: quantum state tomography, matrix product states.)
O. Landon-Cardinal, Y.-K. Liu and D. Poulin, "Efficient Direct Tomography for Matrix Product States," ArXiv:1002.4632. (Keywords: quantum state tomography, matrix product states.)
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. (Keywords: quantum state tomography, matrix completion, compressed sensing.)
~ ~ ~ ~ ~ ~ ~
Y.-K. Liu, "Quantum Algorithms Using the Curvelet Transform," Proc. ACM Symposium on Theory of Computing (STOC), pp.391-400, 2009. ArXiv:0810.4968. (Keywords: quantum algorithms, wavelet transforms.)
Y.-K. Liu, "The Local Consistency Problem for Stoquastic and 1-D Quantum Systems," submitted. ArXiv:0712.1388. (Keywords: quantum complexity theory, quantum marginals.)
Y.-K. Liu, "The Complexity of the Consistency and N-representability Problems for Quantum States," PhD thesis, Univ. of California, San Diego, 2007. ArXiv:0712.3041. (Keywords: quantum complexity theory, quantum chemistry.)
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. (Keywords: quantum complexity theory, quantum chemistry.)
Y.-K. Liu, "Consistency of Local Density Matrices is QMA-complete," Proc. RANDOM 2006, pp.438-449; Arxiv preprint: quant-ph/0604166. (Keywords: quantum complexity theory, quantum marginals.)
~ ~ ~ ~ ~ ~ ~
Y.-K. Liu, V. Lyubashevsky and D. Micciancio, "On Bounded Distance Decoding for General Lattices," Proc. RANDOM 2006, pp.450-461. (Keywords: algorithms for lattice problems.)
Y.-K. Liu, "Gibbs States and the Consistency of Local Density Matrices," Arxiv preprint: quant-ph/0603012.
Previously presented as a poster at the SQuInT workshop, Albuquerque, NM, Feb. 17-19, 2006. (Keywords: quantum marginals, Jaynes' principle.)
K. Levchenko and Y.-K. Liu, "Counting Solutions of Polynomial Equations" [pdf]. (Keywords: complexity theory, #P.)
A note, pointing out an error in the paper: "Improved Range-Summable Random Variable Construction Algorithms," by A. R. Calderbank et al, SODA 2005.
A. Blanc, Y.-K. Liu and A. Vahdat, "Designing Incentives for Peer-to-Peer Routing," Proc. INFOCOM 2005, pp.374-385 [pdf]. (Keywords: peer-to-peer networks, reputation systems, game theory.)
A preliminary version appeared in P2PEcon 2004 [link] (but we recommend the INFOCOM paper, which has more results and a better discussion section).
My undergraduate senior thesis: original version or revised version (Aug. 26, 2002).
Useful Links
NIST: QuICS seminar / Math Division seminar / Crypto reading group
Berkeley: EECS Department Calendar / Theory seminars / Quantum reading group
Caltech: IQI Seminars / Physics Research Conference / CS Theory Seminar / IST Seminars / Technique (campus guide)
