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 at: yikailiu00 |at| gmail |dot| com

This page was last updated on: Dec. 8, 2017.

Some Recent Talks

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

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].


CS138 Computer Algorithms, Spring 2009 (a course on approximation algorithms for combinatorial optimization, at Caltech).

Papers (or try the handy Arxiv listing)

Quantum Cryptography

Z. Ji, Y.-K. Liu, F. Song, "Pseudorandom States, Non-Cloning Theorems and Quantum Money," arXiv:1711.00385.

P. Bierhorst, E. Knill, S. Glancy, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, L. K. Shalm, "Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling," Arxiv:1702.05178.

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.

Y.-K. Liu, "Building One-Time Memories from Isolated Qubits," Innovations in Theoretical Computer Science (ITCS) 2014, pp.269-286; Arxiv:1304.5007.

Quantum State Tomography, and Machine Learning

V. Dunjko, Y.-K. Liu, X. Wu, J. M. Taylor, "Super-polynomial separations for quantum-enhanced reinforcement learning," arXiv:1710.11160.

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.

S. Kimmel and Y.-K. Liu, "Phase Retrieval Using Unitary 2-Designs," SampTA 2017, pp.345-349, [doi]; Arxiv:1510.08887.

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

  • 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].

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].

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]. Conference version: Advances in Neural Information Processing Systems (NIPS), pp.926-934 (2012) [link]. ArXiv:1204.6703.

M. Ohliger, V. Nesme, D. Gross, Y.-K. Liu and J. Eisert, "Continuous-variable quantum compressed sensing," ArXiv:1111.0853.

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.

O. Landon-Cardinal, Y.-K. Liu and D. Poulin, "Efficient Direct Tomography for Matrix Product States," ArXiv:1002.4632.

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.

Quantum Algorithms and Complexity

R. Perlner, Y.-K. Liu, "Thermodynamic Analysis of Classical and Quantum Search Algorithms," arXiv:1709.10510.

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.

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.

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, "The Local Consistency Problem for Stoquastic and 1-D Quantum Systems," submitted. ArXiv:0712.1388.

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.

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.

Other Topics

Y.-K. Liu, V. Lyubashevsky and D. Micciancio, "On Bounded Distance Decoding for General Lattices," Proc. RANDOM 2006, pp.450-461.

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.

K. Levchenko and Y.-K. Liu, "Counting Solutions of Polynomial Equations" [pdf].
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].
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 seminarMath 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)

Tips on writing papers using LaTeX