NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

PUBLICATIONS

Universal Low-rank Matrix Recovery from Pauli Measurements

Published

Author(s)

Yi-Kai Liu

Abstract

We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non- commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered using nuclear norm minimization (e.g., the matrix Lasso), using a fixed ("universal") set of Pauli measurements, and with nearly-optimal bounds on the error. Our proof uses Dudley’s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
Proceedings Title
Advances in Neural Information Processing Systems (NIPS)
Volume
24
Conference Dates
December 12-17, 2011
Conference Location
La Jolla, CA
Conference Title
Neural Information Processing Systems (NIPS)
Pub Type
Conferences

Keywords

Quantum state tomography, matrix completion, compressed sensing
Information technology, Statistical analysis and Quantum information science

Citation

Liu, Y. (2011), Universal Low-rank Matrix Recovery from Pauli Measurements, Advances in Neural Information Processing Systems (NIPS), La Jolla, CA (Accessed October 2, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created December 12, 2011, Updated February 19, 2017
Was this page helpful?