Yi-Kai Liu

I am now at NIST, in the Applied and Computational Mathematics Division. I am working on quantum computation, in particular, quantum algorithms and complexity, quantum state tomography, and cryptography. Previously I was a postdoc at UC Berkeley, a postdoc at Caltech, and a graduate student at UC San Diego. 

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. 5, 2012.

Some Recent Talks

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.

Teaching

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

Papers

Quantum State Tomography, and Machine Learning

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," Advances in Neural Information Processing Systems (NIPS), to appear (2012). 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

A. Bookatz, S. Jordan, Y.-K. Liu and P. Wocjan, "Testing quantum expanders is co-QMA-complete," 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: Math Division seminar 

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