Yi-Kai Liu

I am a staff scientist at NIST, in the Applied and Computational Mathematics Division, and affiliated with the UMD Center for Quantum Information and Computer Science (QuICS). I am working on quantum computation, in particular, quantum algorithms and complexity, quantum state tomography, and 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 at UC San Diego, and a BA in mathematics at 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: July 17, 2015.

Some Recent Talks

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

Teaching

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

Papers (or try the handy Arxiv listing)

Quantum Cryptography

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

F. Krahmer and Y.-K. Liu, "Phase Retrieval Without Small-Ball Probability Assumptions," in preparation.

  • 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

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